|
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).
|
|
insegnamento di Informatica della laurea triennale |
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).
|
- Linguaggi formali e automi.
- Macchine di Turing e calcolabilità
- Macchine a registri
- Funzioni ricorsive e linguaggi funzionali
- Complessità di algoritmi e problemi.
|
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
|
|
Esercizi relativi alle varie parti del corso |