Corso di laurea in Informatica

Fondamenti dell'Informatica I (laurea base - nuovo ordinamento)

Fondamenti dell'Informatica: Calcolabilità e Complessità (laurea quinquennale - vecchio ordinamento)

A.A. 2002/03

DURATA: Trimestrale (31 Marzo 2003 - 13 Giugno 2003)
DOCENTE: Luca Forlizzi, Ph.D.
ORARIO: Martedì 15.00-17.00, Giovedì 11.30-13.30, Venerdì 11.30-13.30 Aula Magna
RICEVIMENTO: Martedì 17.00-19.00
OBIETTIVI: Il corso fornisce un'introduzione alla Logica Matematica, alla Teoria della Calcolabilità e alla Teoria della Complessità Computazionale

Sillabo del Corso

- Elementi di logica: calcolo delle proposizioni, calcolo dei predicati, sistemi formali.
- Elementi di teoria della calcolabilita': numerabilita', modelli di calcolo e tesi di Church, macchina di Turing e macchina a registri.
- Funzioni calcolabili e non calcolabili, problema della fermata, insiemi ricorsivi e ricorsivamente enumerabili
- Linguaggi e problemi, accettabilita' e decidibilita' di linguaggi, calcolo non deterministico.
- Elementi di Teoria della complessita': misure statiche e dinamiche, classi di complessita' spaziali e temporali, le classi di problemi P ed NP.
- La congettura P=NP? NP-completezza. Schema di dimostrazione di NP-completezza. Enunciato del teorema di Cook.

Testi di Riferimento

-"Artificial Intelligence: a modern approach", S.Russell, P.Norvig, Prentice-Hall
-"Automata Theory: Machines and Languages", R.Y.Kain, McGraw-Hill
-"Computability and Complexity Theory", S.Homer, A.L.Selman, Springer Verlag, ISBN 0-387-95055-9
-"Computational Complexity", C.H.Papadimitriou, Addison-Wesley
-"Elements of the theory of computation", H.R.Lewis, C.H.Papadimitriou, Prentice-Hall
-"Fondamenti di Informatica", A.V.Aho, J.D.Ullman, Zanichelli
-"Goedel, Escher, Bach, un'eterna ghirlanda brillante, D.R. Hofstadter, Adelphi
-"Informatica Teorica", C.Ghezzi, D.Mandrioli, Cittàstudi
-"Introduction to automata theory, languages and computation", J.E.Hopcroft, J.D.Ullman, Addison-Wesley
-"Mathematical logic for computer science", M.Ben-Ari, Prentice-Hall
-"Logica a Informatica", A.Asperti, A.Ciabattoni, Mc Graw Hill
-"Teoria della Complessità Computazionale", D.P.Bovet, P.Crescenzi, Franco Angeli
-"Teoria della Computabilità, Logica, Teoria dei Linguaggi Formali", Aiello, Albano, Attardi, Montanari, Materiali Didattici ETS

Dispense del corso:

Versione 1.3.1

Bacheca (informazioni a carattere temporaneo):

consultare gli avvisi sul portale del corso di laurea e/o il forum.

Risultati esami

Risultati Prova Intermedia
Risultati Prova Conclusiva per studenti con particolari esigenze di urgenza
Risultati Prova Conclusiva
Risultati Prima Prova Recupero
Risultati Seconda Prova Recupero
Risultati Prova del 15/12/03
Risultati Prova del 24/03/04

Testi prove scritte

Testi Prova Intermedia
Testi Prova Conclusiva
Testi Prova del 10/07/03 (solo Fondamenti Informatica Calcolabilità e Complessità)
Testi Prima Prova Recupero
Testi Prova del 01/09/03 (solo Fondamenti Informatica Calcolabilità e Complessità)
Testi Seconda Prova Recupero
Testi Prova del 15/12/03
Testi Prova del 24/03/04

Ultimo aggiornamento pagina web: 29/03/2004