Prof. Simone Martini

Approfondire gli aspetti tecnici dei risultati già trattati nel corso di Fondamenti dell'Informatica I. Dopo aver superato l'esame si ritiene che lo studente: sia in grado di discutere la decidibilità o meno (la polinomialità o meno) di alcuni problemi rilevanti, anche utilizzando tecniche raffinate di riduzione, conosca gli aspetti rilevanti della teoria dei linguaggi formali, con particolare rilievo al ruolo del non-determinismo.

1. Calcolabilità
Modelli di calcolo: URM e sua equivalenza con la MdT. Riduzione tra problemi e sue proprietà. Teoremi di Rice e Rice-Shapiro. Teorema di ricorsione.
2. Complessità
Simulazione polinomiale tra modelli di calcolo. Le classi logaritmiche nello spazio. Log n-spazio riduzioni. P-completezza.
3. Linguaggi formali
Automi finiti deterministici e non-deterministici. Pumping lemma per linguaggi regolari.
Linguaggi liberi dal contesto deterministici. Pumping lemma per linguaggi liberi.

Appunti delle lezioni.
N. J. Cutland, Computability: An introduction to recursive function theory, Cambridge Univ. Press, Cambridge 1980.
J.E. Hopcroft e J.D. Ullman, Introduction to automata, languages and computation, Addison-Wesley, Reading 1979.