Laurea in
Informatica
Informatica Teorica (III anno, NO) - a.a. 2002/03
Il corso e' mutuato dal secondo semestre di Algoritmi e Strutture Dati: Algoritmi, Calcolabilita'
e Complessita' (III anno, VO)
Matematica Discreta (Logica Matematica), Programmazione, Algoritmi e
Strutture Dati.
Fornire nozioni e risultati fondamentali di calcolabilita' e
complessita' computazionale.
L'esame si suddivide in una prova scritta ed una orale. Per la prova
scritta si danno in genere 2 ore. Durante lo scritto e' possibile
consultare dispense e libri. E' possibile conservare il voto dello
scritto negli appelli successivi, basta non ritentarlo (o non
cosegnare quella parte). Tuttavia, alla fine di ogni anno accademico
viene fatto un reset dei voti (per maggiori dettagli vedi ESAMI).
- modelli di calcolo:
TM, RAM, funzioni calcolabili, complessita' tempo e spazio, relazione
tra i due modelli di calcolo, Tesi di Church e Tesi di Church estesa.
- calcolabilita':
funzioni calcolabili, problemi/sottoinsiemi decidibili e
semidecidibili, riducibilita' tra problemi, codifica delle TM, TM
universale, esempi di problemi non (semi)decidibili, proprieta' di
chiusura dei sottoinsiemi (semi)decidibili.
- complessita':
classi di complessita', relazioni tra classi di complessita' ed
O-notazione, classi naturali di complessita' (P, NP), teorema di Cook,
esempi di problemi NP-completi.
- panoramica su altri argomenti di complessita':
accenni ad altri modelli di calcolo (per algoritmi probabilistici e
paralleli), e relative classi di complessita'.
- [P94] C.Papadimitriou. Computational Complexity.
Addision-Wesley, 1994.
(CH 1-3, 7-9)