Calcolabilita' e Complessita' (Laurea Specialistica) - a.a. 2005/06

Prerequisiti

Matematica Discreta (Logica Matematica), Programmazione, Algoritmi e Strutture Dati.

Obiettivi

Fornire nozioni e risultati fondamentali di calcolabilita' e complessita' computazionale.

Modalita' degli esami

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 cosegnarlo). Tuttavia, alla fine di ogni anno accademico (dopo l'appello di Gennaio-Febbraio) viene fatto un reset dei voti.

Programma

Testi di Riferimento

Altri testi, (*) indica che puo' rimpiazzare [P94]