Università telematica internazionale UNINETTUNO

Computer Engineering (Academic Year 2018/2019) - Programming and security

Theoretical computer science

Credits: 6
Language: English
Course description
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).
Prerequisites
insegnamento di Informatica della laurea triennale
Objectives
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).
Program

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

Book
G. AUSIELLO, F. D’AMORE, G. GAMBOSI, Linguaggi, Modelli, Complessità, FrancoAngeli Editore, 2003 (vedere sitografia)
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
Exercises
Esercizi relativi alle varie parti del corso
Professor
Claudio Fornaro
Video professors
Prof. Giorgio Ausiello -
List of video lessons
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

Headquarter

Corso Vittorio Emanuele II, 39
00186 Roma - ITALIA
Tax code number: 97394340588
P.IVA: 13937651001

Certified mail

info@pec.uninettunouniversity.net

Student Secretariat

tel: +39 06 692076.70
tel: +39 06 692076.71
e-mail: info@uninettunouniversity.net

Videoconferencing

Library 1st floor: 90.147.90.157
Meeting Room 5th floor: 90.147.90.158

Do you need further information?

Give us your contact details


Ask for information