Il corso necessita delle conoscenze e capacità concrete di programmazione  e di analisi e sviluppo di algoritmi acquisite durante la triennale. Inoltre è richiesta la conoscenza di nozioni di matematica discreta (algebra lineare, analisi asintotica, funzioni, insiemi) e di calcolo delle probabilità (spazi di probabilità, variabili aleatoree continue e discrete, leggi di convergenza).

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

L’esame consiste di una prova scritta e di una prova orale. La prova scritta verifica l’abilità si produrre dimostrazioni rigorose di semplici affermazioni matematiche correlate con gli argomenti del corso. La prova orale verifica l’abilità di esporre in modo chiaro e rigoroso alcuni contenuti del corso.

Gli studenti che ottengono la sufficienza alla prova scritta in un appello possono presentarsi alla prova orale non più tardi dell’appello successivo. Se lo studente non supera la prova orale è tenuto a rifare la prova scritta.

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

Logica e Calcolabilità: Sintassi e Semantica del calcolo proposizionale: operatori, formule ben formate, tavole di verità, tautologie vs contraddizioni, formule soddisfacibili, SAT. ‘conseguenze logiche’, ‘dimostrazioni formali’ vs ‘dimostrabilità’. Correttezza e Completezza della logica proposizionale. Cenni di logiche del primo ordine. (3 lezioni). Calcolabilità: definizioni di funzione calcolabile, modelli di calcolo: schemi primitivi ricorsivi, totalità, aritmetizzazione, teorema di Cantor, insiemi transfiniti e loro cardinalità, Tecnica di dimostrazione Diagonale. Funzione di Ackerman e Schemi pienamente Ricorsivi. Funzioni parziali. Macchine di Turing, linguaggi, riconoscimento vs calcolo di funzione. Problema della Fermata, linguaggi R, RE, co-RE. Riduzioni tra linguaggi. Linguaggi funzionali vs imperativi vs object-oriented. (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)

Complex Networks: Grafi e Reti. Stutture dati e algoritmi di base. Visite, Componenti Connesse, Alberi di copertura di costo minimo, strutture dati Union-Find, e loro analisi e implementazione in Python. Reti Complesse come modelli di reti per il Web: da Erdos-Renyi to Power-law graphs. Crawling su Web e schema di costruzione di un motore di ricerca. (5 lezioni).

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.