21/10/04 (2h).
Le TM non-deterministiche (NDTM), definizione di linguaggio
accettato/deciso e tempo/spazio di lavoro.
Automa deterministico A' corrispondente ad un automa
non-deterministico A per accettare/decidere un linguaggio.
Le classi di complessita' non-deterministiche NTIME(f) e NSPACE(f), e
la classe NP. Risultati di riduzione ad un nastro, speed-up e tape
compression per le classi non-deterministiche.
Esempio: problema della reachability (formulazione finitaria),
algoritmo enumerativo esponenziale, algoritmo di visita polinomiale,
algoritmo non deterministico.
Simulazione di una TM non-deterministica mediante una TM
deterministica mediante visita BFS dell'albero/grafo delle possibili
computazioni
26/10/04 (3h) - docente assente GPCE
28/10/04 (2h) - docente assente GPCE
02/11/04 (3h) - docente assente FMCO
04/11/04 (2h) - docente assente FMCO
09/11/04 (3h) - sospensione per compitini
11/11/04 (2h) - sospensione per compitini