12/10/2006 (2h). La tesi di Church (invarianza di R ed RE al variare del modello di calcolo). Dimostrazione di equivalenza tra TM ad 1 nastro e TM a piu' nastri mediante simulazione di una TM a m-nastri con una TM ad 1 nastro a 2*m tracce. Le classi di complessita' tempo TIME_m(f) e TIME(f). Richiami su O-notazione. La classe P dei problemi trattabili. La tesi di Church estesa (invarianza di P al variare del modello di calcolo). Inclusione di TIME(f) in TIME_1(O(f^2)) con f almeno lineare, mediante analisi di complessita' della simulazione di una TM a m-nastri con una TM ad 1 nastro a 2*m tracce. Rappresentazione di dati mediante stringhe. Esempi: rappresentazione binaria di numeri, rappresentazion di matrici booleane (bit vector a liste).
30/10/2006 DOCENTE ASSENTE
16/11/2006 (2h). DOCENTE ASSENTE