Programmazione, Algoritmi.  

Il corso è tenuto per l'ultimo anno accademico, dal prossimo anno infatti la denominazione del corso cambia in 'Tecniche Algoritmiche' (ma in starebbe meglio 'Algorithmic Engineering'). 
I contenuti del corso quindi saranno diversi dagli ultimi anni accademici e saranno definitivi insieme agli studenti frequentanti a partire dai seguenti:

* Programmazione in Python, dalla programmazione procedurale alla programmazione ad oggetti e funzionale.

* Networks: modelli per reti: grafi, definizione, strutture dati, algoritmi di base, e problemi di ottimizzazione discreta su grafi, modelli probabilistici.

* Complessità Computazionale: definizione, classi P,  NP NP-C e loro relazioni. Problemi di Ottimizzazione e algoritmi di approssimazione.

* Modellazione Algoritmica, Machine Learning

Conoscenze e comprensione. Possedere una preparazione di base sui concetti teorici relativi alla calcolablità e alla complessità computazionale.

Capacità di applicare conoscenze e comprensione: # essere in grado di produrre semplici dimostrazioni rigorose di risultati matematici non identici a quelli già conosciuti, ma chiaramente correlati ad essi, # essere in grado di formalizzare matematicamente problemi relativi alla calcolabilità o complessità di funzioni/algoritmi di moderata difficoltà, in modo da facilitare la loro analisi e risoluzione, # essere capaci di leggere e comprendere, in modo autonomo, testi avanzati o articoli di rivista relativi a questi settori.

Autonomia di giudizio. L’esposizione dei contenuti e delle argomentazioni sarà svolta in modo da migliorare la capacità dello studente di riconoscere dimostrazioni rigorose e individuare ragionamenti fallaci.

Abilità comunicative. La presentazione degli argomenti sarà svolta in modo da consentire l’acquisizione di una buona capacità di comunicare problemi, idee e soluzioni riguardanti l’Informatica Teorica, sia in forma scritta che orale.

Capacità di apprendimento. Saranno indicati argomenti da approfondire, strettamente correlati con l’insegnamento, al fine di stimolare la capacità di apprendimento autonomo dello studente.

Lezioni frontali ed esercitazioni in aula

orale.

Pagina del Corso: http://bilbo.unisalento.it/antonio/didattica/algoritmi-e-complessita/

Calcolabilità: Macchine di Turing, Riconoscimento vs calcolo di funzione. Problema della Fermata, linguaggi R, RE, co-RE. Riduzioni. (2 lezioni)

Python: Introduzione, parte imperativa, parte funzionale, parte ad oggetti. (6 lezioni)
 

Complessità e Algoritmi: Classi di Complessità: DTIME, NDTIME, PSPACE, NPSPACE. P vs NP. Definizioni diverse per NP e loro relazioni. NPSPACE, EXP, etc. Problemi Np-Completi e NP-Ardui, Teorema di Cook-Levin, SAT e riduzioni polinomiali, esempi di varie riduzioni. Limiti e Utilità della teoria della complessità computazionale. Algoritmi di Approssimazione, esempi vari. Algoritmi Probabilistici, Max-SAT, Matching, etc. Effetto soglia sulle istanze di SAT. (7 lezioni)

Esempi in Python di soluzioni per problemi Np-Completi.

Quasi tutti i testi sotto sono reperibili liberamente come PDF su web. Usare un motore di ricerca per trovarli.

Italiano:

• Crescenzi, Informatica Teorica.
• Ausiello, D'Amore, Gambosi, Linguaggi, Modelli, Complessità.
• Asperti, Teoria della Calcolabilità.
• Vigna,  Dispense per il corso di informatica Teorica.
• Degano, Calcolabilità.
• Dovier, Giacobazzi, Linguaggi Formali, Calcolabilità e Complessità

Inglese:

• Stephen G. Simpson, Foundation of Mathematics.
• Rogers, Theory of Recursive Functions.
• Crescenzi, Bovet, Introduction to the theory of Complexity.
• Bjorn Poonen, Indecidable Problems: A Sampler.