Corso di Teoria della Computazione e dell'Interazione (TCI - Modelli di Calcolo)

Le lezioni

Diario delle lezioni dell'anno accademico 2013-2014

• Presentazione del corso. Modalita' di esame. Orario delle lezioni. Canni storici intorno al concetto di calcolabilita', Macchine di Turing. Automi. Lambda-calcolo. Funzioni ricorsive.

• Introduzione del concetto di Sistema di Transizione. Definizione di Algoritmo Formale. Rappresentabilita'. Alfabeto finito. Monoide delle parole di un certo alfabeto. Definizione di problema decidibile. Definizione di problema semidecidibile. Computazione associata ad un algoritmo formale.

• Introduzione alla programmazione object oriented. Classi e oggetti come disciplina modulare di programmazione.

• Esempio di Algoritmo Formale. Descrizione del modello di computazione a stati finiti. Definizione di automa a stati finiti. Definizione dell'algoritmo assiciato. Insiemi decidibili per automa.

• Esercizio sulla decidibilita' per automa finito. Proprieta' sulla decidibilta' di insiemi somma di insiemi decidibili.

• Definizione di una nuova classe. Classi che utilizzano la ricorsione a livello di metodo e a livello di classe. Adattamento del makefile ai programmi Java. L'architettura di esecuzione distribuita soggiacente Java. I costruttori di classe. Overloading di metodi costruttori.

• Definzione di automa finito non-deterministico. Algoritmo formale associato ad un automa non deterministico. Costruzione dell'automa finito che accetta l'unione di due insiemi decidibili.

• Decidibilita' per automa finito e' equivalente alla decidibilita' per automa finito non deterministico. Teorema sulle proprieta' di chiusura dell'insieme dei linguaggi regolari. Chiusura per concatenazione, unione ed iterazione. Definizione di espressione regolare. Interpretazione delle espressioni regolari come insiemi regolari.

• Definizione induttiva delle espressioni regolari. Insieme regolare associato ad una`espressione regolare. Teorema di equivalenza tra espressioni regolari e insiemi regolari. Esempi di calcolo di un'espressione regolare associata ad un insieme regolare.

• Automa a stati finiti non deterministici generalizzati (con transizioni etichettate con espressioni regolari). Procedura di costruzione dell'espressione regolare associata ad un automa. Macchina RAM. Istruzioni di una macchina RAM. Descrizione informale di algoritmo associato ad una macchina RAM.

• implementazione della classe Filter, terminata l'implementazione del Crivello di Eratostene Metodi per l'accessibilita' di attributi. Costruttori di classe. Metodi astratti. Classi astratte. Overriding di metodi. Liste di oggetti eterogenei.

• Definizione di Macchina di Turing. Definizione di algoritmo associato ad una macchina di Turing. Decidibilita' per macchina di Turing. Esempio di computazione. Rappresentazione grafica delle macchine di Turing.

• Costo in tempi di una computazione. Tempo (risp. Spazio) di arresto di una macchina a partire da una parola di input. Funzione di complessita' T(n). Definizione di macchina che si arresta in tempo (risp. spazio) T(n). roprieta' elementari soddisfatte dagli insiemi decidibili in tempo T(n). Pumping Lemma per la classe di complessita' lineare DTIME(cn).

• Esonero Esonero

• Indecidibilita' del problema dell'arresto. Prime definizioni sul lambda-calcolo.

• Definizione di sostituzione semplice. Definizione di variabili libere e variabili legate. La sostituzione e' invariante per permutazione. Lemma di indipendenza dalle variabili non-libere. Lemma di concatenazione tra sostituzioni. Proprieta' dimostrabili mediante induzione strutturale sulla costruzione dei lambda termini.

• Definizione dei grafi di condivisione per rappresentare i lambda termini. Procedura di beta-riduzione con i grafi di condivisione. Lemma di compatibilita' tra sostituzione semplice e cambiamento di variabile. Definizione di relazione sui lambda termini che passa al contesto. Compatibilita' tra relazioni che passano al contesto e sostituzione semplice.

• Quozientamento dell'insieme dei lambda-termini per alfa-equivalenza. Compatibilita' tra classi di equivalenza e i costrutti del lambda calcolo. Definizione di sostituzione sulle classi di equivalenza. Proprieta' di Church-Rosser. Chiusura transitiva di relazioni. Definizione di beta-riduzione. Redesso e ridotto. Definizione di beta-riduzione.