Corso di Informatica 2 (IN2 - Modelli di Calcolo)

Le lezioni

Diario delle lezioni dell'anno accademico 2007-2008

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.pdfScarica il documento in formato 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.


Per informazioni e commenti: pedicini@mat.uniroma3.it - Torna alla Home page - Ultima modifica: Mon Jul 7 11:37:47 CEST 2008