Università degli
Studi di Udine

 

FONDAMENTI DELL'INFORMATICA II
 
DOCENTE
Prof. Simone Martini
FINALITA' DEL CORSO

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.

ARGOMENTI

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.

MODALITA' D'ESAME
 
TESTI CONSIGLIATI

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.