elenco     
        corso     

Elementi di calcolabilità e complessità

Codice: 246AACrediti: 6Semestre: 1Sigla: ECC 
 
Settore disciplinare: INF/01 - Informatica

Docente

Franco Turini   turini@di.unipi.it  Stanza 335  Tel. 0502212753

Ultima 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).
Ore lezione: 48    


home


email