Contacts

Community

Search

IT | EN | FR | عربي | GR

Corso Vittorio Emanuele II, 39 - Roma 0669207671

Contacts

Community

IT | EN | FR | عربي | GR

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

Informatica teorica

Lesson n. 1: Introduzione al corso Obiettivi e programma del corso Alfabeti, stringhe, linguaggi Operazioni sui linguaggi Espressioni regolari		Giorgio Ausiello
Lesson n. 2: Grammatiche di Chomsky Definizione di grammatica di Chomsky Derivazione di stringhe e generazione di linguaggi Classi di grammatiche e di linguaggi Linguaggi di Tipo 0, 1, 2, 3		Giorgio Ausiello
Lesson n. 3: Linguaggi regolari e automi a stati finiti Linguaggi regolari e automi a stati finiti Automi a stati finiti non deterministici Relazione tra automi deterministici e non deterministici		Giorgio Ausiello
Lesson n. 4: Proprietà dei linguaggi regolari Relazione tra automi, grammatiche ed espressioni regolari "Pumping lemma" per I linguaggi regolari Equivalenza di automi a stati finiti		Giorgio Ausiello
Lesson n. 5: Proprietà dei linguaggi non contestuali "Pumping lemma" per I linguaggi non contestuali Proprietà di chiusura Grammatiche non contestuali in forma ridotta Forme normali		Giorgio Ausiello
Lesson n. 6: Riconoscimento di linguaggi non contestuali e analisi sintattica Automi a pila Relazione tra automi a pila e grammatiche non centestuali Analisi sintattica di linguaggi Il problema dell'ambiguità		Giorgio Ausiello
Lesson n. 7: Macchine di Turing Definizione della macchina di Turing Riconoscimento e accettazione di linguaggi Macchine a più nastri		Giorgio Ausiello
Lesson n. 8: Calcolabilità secondo Turing Macchine non deterministiche Macchine di Turing e linguaggi di tipo 0 Funzioni calcolabili secondo Turing La tesi di Church-Turing		Giorgio Ausiello
Lesson n. 9: Limiti di calcolabilità Macchine di Turing in forma ridotta Macchina di Turing universale Il problema della terminazione Altri problemi indecidibili		Giorgio Ausiello
Lesson n. 10: Macchine a registri Macchine a registri (RAM) Costi di calcolo RAM e macchine di Turing Macchine a registri elementari		Giorgio Ausiello
Lesson n. 11: Funzioni ricorsive e linguaggi funzionali Le funzioni ricorsive primitive Il formalismo di Mc Carthy		Giorgio Ausiello
Lesson n. 12: Introduzione al Lisp Un semplice linguaggio funzionale: Lisp		Giorgio Ausiello
Lesson n. 13: Analisi di algoritmi e complessità di problemi Analisi di algoritmi Complessità di problemi Classi di complessità		Giorgio Ausiello
Lesson n. 14: Le classi, P, NP, PSPACE Classi di complessità notevoli I teoremi di gerarchia Il teorema di Savitch Problemi aperti		Giorgio Ausiello
Lesson n. 15: I problemi NP - completi La classe NP Riduzioni tra problemi e problemi completi Il teorema di Cook Altre dimostrazioni di NP-completezza		Giorgio Ausiello