Corso Vittorio Emanuele II, 39 - Roma 0669207671

Ingegneria Informatica (Anno Accademico 2020/2021) - Programmazione e sicurezza

Informatica teorica


CFU: 6
Lingua contenuti:Italiano
Descrizione dell'insegnamento
Insegnamento obbligatorio della Laurea Magistrale in Ingegneria Informatica indirizzo Programmazione e sicurezza, collocato al II anno. Il corso presenta i vari modelli formali adatti a descrivere linguaggi ed a rappresentare macchine e programmi e ne illustra i principali aspetti:
proprietà sintattiche dei linguaggi e verifiche di correttezza sintattica
potere computazionale dei vari modelli di calcolo
varianti deterministiche e non deterministiche
costi di computazione
Approfondisce il concetto di calcolabilità e comprensione dei limiti teorici dei calcolatori (problemi non decidibili, funzioni non calcolabili) e quello di costo di risoluzione di un problema (complessità computazionale) per comprendere i limiti pratici dei calcolatori (problemi computazionalmente intrattabili).
Prerequisiti
insegnamento di Informatica della laurea triennale
Scopi
Presentare vari modelli formali adatti a descrivere linguaggi ed a rappresentare macchine e programmi ed illustrarne i principali aspetti:
proprietà sintattiche dei linguaggi e verifiche di correttezza sintattica
potere computazionale dei vari modelli di calcolo
varianti deterministiche e non deterministiche
costi di computazione
Approfondire le proprietà del concetto di calcolabilità e comprendere i limiti teorici dei calcolatori (problemi non decidibili, funzioni non calcolabili) Approfondire il concetto di costo di risoluzione di un problema (complessità computazionale) e comprendere i limiti pratici dei calcolatori (problemi computazionalmente intrattabili).
Contenuti

- Linguaggi formali e automi.
- Macchine di Turing e calcolabilità
- Macchine a registri
- Funzioni ricorsive e linguaggi funzionali
- Complessità di algoritmi e problemi.

Testi
G. AUSIELLO, F. D’AMORE, G. GAMBOSI, L.LAURA - Linguaggi, Modelli, Complessità, FrancoAngeli Editore, Nuova edizione, 2014
Testi consigliati in alternativa o a completamento:
H. R. LEWIS, CH. PAPADIMITRIOU, Elements of the Theory of Computation, Prentice-Hall, 1981
J. E. HOPCROFT, R. MOTWANI, J. D. ULLMAN, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 2000
D. P. BOVET, P. CRESCENZI, Teoria della complessità computazionale, FrancoAngeli Editore, 1991
P. H. WINSTON, B. K. P. HORN, LISP, Addison-Wesley, 1984
Esercitazioni
Esercizi relativi alle varie parti del corso
Docente/Tutor Responsabile insegnamento
Luigi Laura
Docenti video
Elenco delle lezioni
Giorgio Ausiello
Giorgio Ausiello
Giorgio Ausiello
Giorgio Ausiello
Giorgio Ausiello
Giorgio Ausiello
Giorgio Ausiello
Giorgio Ausiello
Giorgio Ausiello
Giorgio Ausiello
Giorgio Ausiello
Giorgio Ausiello
Giorgio Ausiello
Giorgio Ausiello
Giorgio Ausiello