| | | corso | | | | | |
Elementi di calcolabilità e complessità
Codice: | 246AA | Crediti: | 6 | Semestre: | 1 | Sigla: | ECC | |
|
Settore disciplinare: | INF/01 - Informatica |
Docente
Franco Turini
Tel. 0502212753Ultima versione disponibile: programma da confermare per l’a.a. 2012/2013
Obiettivi di apprendimento
Introduzione alle nozioni fondamentali della teoria della calcolabilità e della complessità.
Programma
Linguaggi Formali e Automi: grammatiche, linguaggi e operazioni su di essi, gerarchia di Chomsky; automi a stati finiti, grammatiche regolari, espressioni regolari; automi a pila, grammatiche libere da contesto
Calcolabilità: Idea intuitiva di algoritmo, Macchina di Turing per accettare e calcolare, funzioni ricorsive primitive, diagonalizzazione, funzioni ricorsive generali, Goedelizzazione, Padding Lemma, Forma Normale, Funzione Universale, teorema s-m-n, insiemi ricorsivi e r.e., problemi insolubili e riducibilità
Complessità: problemi risolubili in tempo polinomiale, teorema di speed-up, teorema del gap, teorema della gerarchia, problemi risolubili nondeterministicamente in tempo polinomiale, riduzioni in tempo polinomiale, problemi NP-completi (SAT).