UNIVERSITA’ DI ROMA "LA SAPIENZA"

FACOLTA’ DI INGEGNERIA – SEDE DI LATINA

PROGRAMMA DEL CORSO DI

INFORMATICA TEORICA A.A. 2010-2011




Docente

Giorgio Ausiello

Crediti

5

Testo

(AdG) G. Ausiello, F. d’Amore, G. Gambosi, Linguaggi, Modelli, Complessità, F. Angeli Editore




1.Concetti matematici di base

Linguaggi. Operazioni su linguaggi. Espressioni regolari.

(AdG - Cap. 1 – Sez. 1.4)

2.Linguaggi formali

Generazione e riconoscimento di linguaggi formali. Grammatiche di Chomsky. Linguaggi di Tipo 0, Tipo 1, Tipo 2 e Tipo 3. Metodi di definizione sintattica dei linguaggi di programmazione: BNF, diagrammi sintattici.

(AdG – Cap. 2 – Sez. 2.1, 2.4, 2.5)

3.Linguaggi regolari

Automi a stati finiti deterministici e non deterministici. Costruzione di un ASF equivalente ad un ASFND dato. Costruzione di una grammatica di tipo 3 che genera il linguaggio riconosciuto da un ASF dato. Costruzione di un ASFND corrispondente ad una espressione regolare data. "Pumping" lemma. Proprietà di chiusura con dimostrazione. Problemi decidibili. Decidibilità dell’equivalenza di ASF.

(AdG - Cap. 3 – Sez. 3.1, 3.2, 3.3, 3.4, 3.5, 3.6 (tranne dimostrazioni dei Teoremi 3.12 e 3.13), Sez. 3.7)

4.Linguaggi non contestuali

Forma Normale di Chomsky. Forma Normale di Greibach. "Pumping" lemma. Proprietà di chiusura dei linguaggi non contestuali. Problemi decidibili. Non chiusura rispetto all’intersezione. Automi a pila deterministici e non deterministici. Costruzione di un APND corrispondente ad una grammatica data in GNF. Accenno all’analisi sintattica. Accenno al problema della ambiguità.

(AdG – Cap. 4 – Sez. 4.1 (tranne dimostrazioni dei teoremi 4.1, 4.2, 4.3, 4.7), Sez. 4.2, 4.3, 4.4, 4.5 (tranne dimostrazioni dei teoremi 4.15, 4.16 e 4.18), Sez. 4.7, 4.8 (tranne sottosezione 4.8.1))

5.Macchine di Turing

Concetto di calcolabilita' secondo Turing. Tesi di Church Turing. Funzioni calcolabili parziali e totali. Insiemi (o linguaggi) decidibili, indecidibili e semidecidibili. Equivalenza tra linguaggi semidecidibili e linguaggi di tipo 0. Macchina di Turing Universale. Indecidibilita' del problema della terminazione.

(AdG - Cap. 5 - Sez. 5.1, 5.2, 5.3, 5.4, 5.5, 5.6, 5.8, 5.9, 5.10)

6.Modelli di calcolo imperativi e funzionali

Macchine e Registri (RAM). Modello a costi uniformi e modello a costi logaritmici. Discussione ed esempi. Costruzione della RAM equivalente a una MT data e viceversa. Enunciato della equivalenza tra RAM ed MT. Funzioni ricorsive primitive. La funzione di Ackermann. Funzioni ricorsive generali. Esempi. Calcolabilita' delle funzioni ricorsive generali. Enunciato della equivalenza tra funzioni calcolabili e funzioni ricorsive generali. Il formalismo di Mc Carthy. Il linguaggio LISP.

(AdG - Cap. 6 - Sez. 6.1, 6.2, 6.3, 6.4, 6.6 - Cap. 7- solo Sez. 7.4)

7.Complessità di calcolo e classi di complessità di problemi

Analisi di complessita'. Complessita' temporale e spaziale e relative classi di complessita'. Relazioni tra classi deterministiche e non deterministiche. Relazioni tra classi spaziali e classi temporali. Enunciato dei risultati di contenimento tra classi di complessita'. Teorema di Savitch. Gerarchie di classi di complessita'. Riducibilita' tra problemi diversi. Concetto di completezza. Le classi P ed NP. I problemi NP-completi. Dimostrazioni di riducibilita' tra problemi. Dimostrazione del Teorema di Cook.

(AdG - Cap. 8 - Sez. 8.1, 8.2, 8.3, 8.5, 8.6 (tranne dimostrazioni di Lemma 8.3 e dei Teoremi 8.5 e 8.6), Sez. 8.7 (tranne dimostrazione del Teorema 8.26), Sez. 8.8 - Cap. 9 - Sez. 9.1, 9.3, 9.4 (tranne dimostrazioni dei Teoremi 9.4 e 9.7))


[Back]