Teacher:
Lessons schedule:
Students Office hours:
D1 - CONOSCENZA E CAPACITÀ DI COMPRENSIONE Risultati attesi: Al termine di questa attività formativa, lo studente dovrà dimostrare di essere in grado di:
D2 - CAPACITÀ DI APPLICARE CONOSCENZA E COMPRENSIONE Risultati attesi: Al termine di questa attività formativa, lo studente dovrà dimostrare di essere in grado di:
D3 - AUTONOMIA DI GIUDIZIO Risultati attesi: Al termine di questa attività formativa, lo studente dovrà dimostrare di essere in grado di:
D4 - ABILITÀ COMUNICATIVE Al termine di questa attività formativa, lo studente dovrà dimostrare di essere in grado di:
D5 - CAPACITÀ DI APPRENDIMENTO
Verso una definizione astratta del concetto di algoritmo. Macchine di Turing. Tesi di Church e Turing. Cenni sul problema dell’arresto, sul decimo problema di Hilbert e su altri problemi insolubili in matematica e in informatica.
Il problema della complessità. Complessità di una macchina di Turing.
Il parametro tempo: la tesi di Cook-Karp, le classi P e NP, il problema P=NP. Linguaggi NP-completi. Teorema di Cook-Levin. Linguaggi NP-intermedi. La gerarchia polinomiale.
Il parametro spazio: le classi L, NL, PSPACE. Teorema di Savitch. Linguaggi NL-completi. Linguaggi PSPACE-completi. Teorema di Baker-Gill-Solovay.
Complessità probabilistica: le classi PP, BPP, RP e ZPP.
Complessità interattiva: le classi AM, MA, AM[Poly] e IP. Cenni sul teorema di Shamir.
Cenni su complessità e circuiti.
Course Slides
Reference books
Exam Dates A.Y. 2016/2017
Exam rules:
Il raggiungimento dei risultati di apprendimento D1, D2, D3 e D4 sarà verificato attraverso una prova orale finale con semplici esercizi e da discussioni durante il corso. Altre informazioni potranno essere reperite nello spazio web del docente sul portale docenti.
Exam Results