Le lezioni

Le lezioni si tengono nel primo semestre con il seguente orario:

• martedì ore 11.00-13.00 (lezione o esercitazione a settimane alterne).
• mercoledì ore 14.00-16.00 (lezione);
• venerdì ore 16.00-18.00 (lezione).

Lezione n. 1 - martedì 18 settembre 2007

Presentazione del corso: argomenti che tratteremo, orario delle lezioni, orario delle esercitazioni, orario di ricevimento, propedeuticità con TIB, modalità di esame, validità degli esami scritti (scarica il documento: 01_presentazione.pdf). Introduzione ai problemi di decisione: procedure algoritmiche e non algoritmiche, computazioni deterministiche, processi discreti, rappresentazioni discrete, nozione di alfabeto, di parola, definizione formale di algoritmo: configurazioni, funzioni di input, di transizione e di output, esecuzione di un algoritmo. Decidibilità e semidecidibilità di un insieme.

Lezione n. 2 - venerdì 22 settembre 2006

OOP.: Introduzione alla programmazione object oriented.

Lezione n. 3 - martedì 26 settembre 2006

Algoritmi: computazioni deterministiche finitarie e discrete. Esempio di formalizzazione di un algoritmo: divisibilità di un intero per 9. Automi Finiti.: decidibilità per automa finito. Macchine RAM: definizione della RAM.

Lezione n. 4 - mercoledì 27 settembre 2006

Machine RAM: esempi, modello di costo uniforme e logaritmico. Macchine di Turing: definizioni, algoritmo associato ad una macchina di Turing, decidibilità e semidecidibilità rispetto ad una macchina di Turing.

Lezione n. 5 - venerdì 29 settembre 2006

Macchina di Turing tempo di arresto di una macchina, spazio di arresto di una macchina. Costo di una computazione. Indipendenza del tempo di decisione da un numero finito di elementi di input.

Lezione n. 7 - venerdì 29 settembre 2006

OOP Ereditarietà tra classi, classi astratte.

Lezione n. 8 - martedì 3 ottobre 2006

Complessità indipendenza della complessità da un numero finito di casi.

Lezione n. 9 - martedì 4 ottobre 2006

Complessità Algoritmi indecidibili in tempo lineare, il pumping lemma.

Lezione saltata (per sciopero) - venerdì 6 ottobre 2006

Sospensione Lezioni le lezioni dal 10 al 13 ottobre 2006 sono sospese.

Lezione n. 10 - martedì 17 ottobre 2006

Simulazioni Macchina di Turing a seminastro, simulazione di algoritmi.

Lezione n. 11 - mercoledì 18 ottobre 2006

Simulazioni Equivalenza computazionale tra: macchina di Turing a seminastro, standard e multinastro.

Lezione n. 12 - venerdì 20 ottobre 2006

Simulazioni Equivalenza della macchina standard e multinastro.

Lezione n. 13 - venerdì 20 ottobre 2006

Esercitazione Automi a stati finiti, macchine di Turing, macchine RAM.

Lezione n. 14 - martedì 24 ottobre 2006

Inclusione di alfabeto: Teorema di Speedup lineare per macchine con alfabeto esteso. Valutazione dell'accelerazione.