INFORMAZIONI SU

Fondamenti dell'Informatica

Programma dell'insegnamento di Fondamenti dell'Informatica - Corso di laurea in Informatica (2013/14)

Docente

Prof. Agostino Dovier sito web

Crediti

9 CFU

Finalità

Il corso affronta le basi teoriche della scienza del calcolatore.
In particolare, dopo aver superato l'esame, si ritiene che lo studente sia in grado di discutere la decidibilità o meno, e la polinomialità o meno, di problemi, anche utilizzando tecniche raffinate di riduzione, e conosca gli aspetti rilevanti della teoria dei linguaggi formali.

Programma

Il corso si divide in tre parti: linguaggi formali, calcolabilità, e complessità.

Linguaggi formali.
Linguaggi regolari. Automi a stati finiti deterministici e non-deterministici e loro equivalenza.
Espressioni regolari. Pumping Lemma per i linguaggi regolari e sue applicazioni.
Proprietà di chiusura e di decidibilità dei linguaggi regolari.
Linguaggi liberi dal contesto. Grammatiche libere dal contesto e alberi di derivazione.
Grammatiche ambigue. Le forme normali di Chomsky e di Greibach.
Il pumping lemma per i linguaggi liberi e le sue applicazioni.
Proprietà di chiusura e di decidibilità dei linguaggi liberi.
Grammatiche lineari destre e sinistre, grammatiche di tipo 0 e 1 e gerarchia di Chomsky.

Calcolabilità.
Il concetto di algoritmo. Modelli di calcolo. La macchina di Turing.
Funzioni Turing-calcolabili. Enumerazione. Halting Problem e sua indecidibilita'.
Il teorema SMN. I formalismi delle funzioni primitive ricorsive e ricorsive parziali. La funzione di Ackermann.
Equivalenza tra le funzioni ricorsive parziali e le funzioni Turing-calcolabili.
Teoremi di Rice, Rice-Shapiro e i Teoremi di ricorsione.
Applicazioni alla programmazione. Riducibilità funzionale.
Studio della relazione. Insiemi ricorsivi e completi. Insiemi creativi e produttivi.
Teorema di Myhill. Insiemi semplici: esistenza di un insieme semplice.

Complessità.
Problemi e linguaggi. Problemi decisionali e funzionali.
Classi di complessità in tempo deterministiche e non deterministiche; classi in spazio: principali risultati. Riduzioni, completezza, ed esempi.
Teoremi di Cook. NP-completezza di alcuni problemi fondamentali mediante riduzione.

Bibliografia

- A. Dovier e R. Giacobazzi: Fondamenti dell'Informatica: Linguaggi Formali, Calcolabilità e Complessità. Disponibile on-line.
- 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.
- C. H. Papadimitriou. Computational Complexity. Addison Wesley, 1995.

Modalità d'esame

Prova scritta ed orale