Obiettivi Formativi

Il corso si propone di introdurre le basi della teoria della calcolabilità e della complessità, presentando opportunamente i necessari strumenti teorici utili anche per affrontare in maniera rigorosa numerose altre problematiche in ambito informatico. Viene affrontato rigorosamente il concetto di problema risolubile per via algoritmica ed esplorata la classe dei problemi non risolubili. Vengono poi presentate la classificazione e la suddivisione dei problemi in classi di complessità, definite in termini di limiti alla quantità di risorse computazionali a disposizione per la loro soluzione automatica.

Competenze acquisite

Al termine del corso studente sarà in grado di applicare gli approcci e gli strumenti formali presentati nell’insegnamento all’analisi di problemi di varia natura. Sarà anzitutto in grado di formulare e modellare correttamente il problema, quindi di analizzare formalmente soluzioni algoritmiche proposte non solo in riferimento a problematiche di efficiente calcolabilità ma considerando e valutando qualunque altro aspetto rilevante al problema in oggetto. Lo studente inoltre acquisirà conoscenze specifiche di calcolabilità e complessità fondamentali in qualunque percorso di ricerca informatica.

Programma

– Prerequisiti matematici
– Funzione coppia
– Linguaggi di programmazione RAM e while
– Sintassi e semantica operazionale
– Compilatori
– Aritmetizzazione di programmi
– Interprete e funzione universale
– Eliminazione del “goto”
– Funzioni ricorsive parziali
– Tesi di Church
– Esistenza di problemi non decidibili
– Passaggio automatico di parametri
– Sistemi di programmazione accettabili
– Teorema di ricorsione
– Insiemi ricorsivi e ricorsivamente numerabili
– Proprietà di chiusura
– Teorema di Rice
– Introduzione alla complessità sequenziale
– Prerequisiti matematici: la notazione “O grande”
– Macchine di Turing deterministiche
– Risorse computazionali: tempo e spazio
– Classi di complessità in tempo e spazio
– Le classi L, P, PSPACE
– Tesi di Church ristretta
– Macchine di Turing nondeterministiche: tempo e spazio
– Le classi NL, NP, NPSPACE
– Teorema di Savitch
– Riduzioni tra problemi e completezza
– Problemi NP-completi, P-completi, PSPACE-completi
– Teorema di Cook ed esempi di riduzione

Testi Consigliati

Dispense reperibili al sito dell’insegnamento (vedi sotto)
· Teoria della calcolabilità:
– A.J. Kfoury, R.N. Mall, M.A. Arbib. Programmazione e computabilità. Etas libri, 1986.
· Teoria della Complessità:
– M.R. Garey, D.S. Johnson. Computers and intractability. A guide to the theory of NP-completeness. W.H. Freeman, 1979.

Modalità di Verifica

–         Prova scritta con domande aperte e scelta multipla

–         La durata della prova e di massimo 1,5 ore

–         La valutazione viene espressa in trentesimi