Calcolabilita' e Complessita' (LS in Informatica) - a.a. 2006/07

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 Settembre) viene fatto un reset dei voti.

Programma

Testi di Riferimento

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