TCI - Teoria della Computazione e dell'Interazione

Le lezioni si tengono al II semestre con il seguente orario:

• [-] lunedì ore 9.00-11.00 (lezione, Aula 211);
• [-] lunedì ore 11.00-13.00 (lezione pratica, Laboratorio Informatico);
• [-] giovedì ore 11.00-13.00 (lezione, Aula 211) mercoledì ore 9.00-11.00 (lezione, Laboratorio Informatico Aula 211).

Lezione n. 1 - Monday 16 February 2015

Presentazione del corso. Modalita` di esame. Orario delle lezioni. Cenni 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.

Lezione n. 2 - Thursday 19 February 2015

Computazione associata ad un algoritmo formale. Esempio di Algoritmo Formale. Descrizione del modello di computazione a stati finiti. Definizione di automa a stati finiti. Definizione dell'algoritmo associato. Insiemi decidibili per automa. Esercizio sulla decidibilita` per automa finito. Rappresentazione come grafo degli automi. Rappresentazione come matrice di adiacenza. Semianello delle serie formali sul monoide libero delle parole di alfabeto A. Matrice sul semianello delle serie formali associata ad un automa finito. Formula dell'esecuzione dell'automa. Estrazione del linguaggio deciso dall'automa a partire dalla formula dell'esecuzione.

Lezione n. 3 - Monday 23 February 2015

Algebra di Kleene. Le matrici a elementi in un algebra di Kleene Formano un'algebra di Kleene. Formula dell'Esecuzione di un automa. Calcolo dell'insieme deciso da un automa a partire dalla sua formula dell'esecuzione. Insiemi regolari. Automa Finito Non-deterministico. Concetto di programmazione object oriented. Compilatore e esecutore. La java virtual machine. Confronto tra la compilazione in C e in Java. Definizione di classe. Il metodo main(). L'overloading di metodi.

Lezione n. 4 - Thursday 26 February 2015

Algebra di Kleene delle Matrici. Formula dell'esecuzione di un automa. Insiemi regolari. Proprieta` di chiusura degli insiemi regolari. Automi Non-deterministici. Automi con transizioni epsilon. Equivalenza tra la DFA-decidibilita` e NDFA-decidibilta`.

Lezione n. 5 - Monday 2 March 2015

Definizione di espressione regolare. Interpretazione di un'espressione regolare con un insieme. Proposizione: ogni insieme regolare e' interpretazione di un'espressione regolare. Proposizione: ogni insieme regolare e' interpretazione di una qualche espressione regolare. Definizione di automa non deterministico generalizzato. Procedura per costrui`re l'espressione regolare associata ad un automa. Il concetto di costruttore di classe in java. Definizione della classe delle liste. Il concetto di ereditarieta`' tra classi. La definizione di una classe IntegerList derivata dalla classe Liste.

Lezione n. 6 - Wednesday 4 March 2015

Definizione di Macchina RAM. Linguaggio della RAM, algoritmo formale associato ad un programma per RAM. Esempio di programma.

Lezione n. 7 - Monday 9 March 2015

Definizione di tempo e spazio di arresto per una Turing machine. Definiizione di funzione di complessita`. Decidibilta` in tempo di un insieme X. Definizione di una classe per le liste eterogenee. Illustrazione del crivello di Eratostene: studio comparativo tra versione ad allocazione statica e la versione object oriented. Implementazione del crivello di Eratostene.

Lezione n. 8 - Wednesday 11 March 2015

Esempio di insieme che separa la classe di complessita` lineare da quella quadratica. Pumping Lemma.

Lezione n. 9 - Monday 16 March 2015

Definizione di simulazione tra algoritmi. Definizione di macchina di Turing a seminastro. Teorema di Simulazione tra macchine di Turing e macchine a seminastro. Costo di simulazione per le macchine di Turing con macchine a semi nastro. Crivello di Eratostene a oggetti: allocazione dinamica. Implementazione delle classi: Item, Sieve, Filter, Counter. Qualificatori di accessibilita` public, private. Metodi di classe (static). Controllo in fase di esecuzione della dimensione dello stack. Versione iterativa della stampa della lista eterogenea di oggetti. Metodo toString() in Java.

Lezione n. 10 - Wednesday 18 March 2015

Macchina di Turing multi nastro. Equivalenza con la macchina di Turing.

Lezione n. 11 - Monday 23 March 2015

Cambiamenti di Alfabeto. Inclusioni di alfabeto. Teorema di Speedup (accelerazione lineare). Macchine di Turing Speciali. Simulazione delle macchine di Turing a semi-nastro con macchina di Turing speciali. Terminata l'implementazione a oggetti del crivello di Eratostene. Overriding di metodi e attributi. Accessibilta' di metodi ed attributi: private, package, public. Le classi Integer e BigInteger.

Lezione n. 12 - Wednesday 25 March 2015

Esercitazione su automi a stati finiti e linguaggi regolari.

Lezione n. 13 - Monday 30 March 2015

Prima Prova in Itinere

Lezione n. 14 - Monday 13 April 2015

Funzioni Turing Computabili. Proprieta' di chiusura delle funzioni Turing Computabili (composizione, concatenazione, ritorsione primitiva, mineralizzazione). Turing computabilita' di alcune funzioni aritmetiche elementari (costanti, proiezioni, addizione, predecessore) Classe Token, Creazione di una classe wrapper per BigInteger. Modifica delle classi Sieve, Filter e Counter per funzionare con la classe Token.

Lezione n. 15 - Wednesday 15 April 2015

Definizione della classe delle funzioni ricorsive. Dimostrazione della ricorsivita' di alcune funzioni aritmetiche.

Lezione n. 16 - Monday 20 April 2015

Insiemi Ricorsivi. Chiusura degli insiemi ricorsivi per unione finita, intersezione finita, complemento. Gli insiemi ricorsivi formano un'algebra di Boole. Ricorsivita` delle funzioni definite per casi. Ricorsivita' della somma limitata. Codifica ricorsiva delle coppie. Schema di Ricorsione Generalizzato a piu` variabili. Ricorsivita` di alcune funzioni aritmetiche. Implementazione ad oggetti del Crivello di Eratostene. Late Binding di metodi.

Lezione n. 17 - Wednesday 22 April 2015

Ricorsivita' delle funzioni Turing Computabili.

Lezione n. 18 - Monday 27 April 2015

Lezione n. 19 - Wednesday 29 April 2015

Lezione n. 20 - Monday 4 May 2015

Definizione di relazione binaria che passa al contesto Teorema di caratterizzazione della piu` piccola relazione binaria sui lambda termini che ne contiene un'altra e che passa al contesto.

Lezione n. 21 - Wednesday 6 May 2015

Definizione della relazione alpha tra lambda-termini. Dimostrazione che la relazione alpha e' di equivalenza. Dimostrazione che la relazione alpha passa al contesto.

Lezione n. 22 - Monday 11 May 2015

Definizione di chiusura transitiva di una relazione. Proprieta' di Church-Rosser preservata per chiusura transitiva. Definizione della relazione beta0 tra redesso e ridotto. Definizione di beta conversione.

Lezione n. 23 - Wednesday 13 May 2015

Grafo sintattico di un lambda termine. Beta Riduzione grafi sintattici. Condivisione di sottotermini. Riduzione tramite Grafi di Lamping. Riduzione ottimale.

Lezione n. 24 - Monday 18 May 2015

Sharing Graphs. Riduzione Ottimale del Lambda Calcolo.

Lezione n. 25 - Wednesday 20 May 2015

Lezione n. 26 - Monday 25 May 2015

Applicazioni della caratterizzazione della risolubilita`. Applicazione del Teorema di Bohm. Esercizi sulla rapprentabilita' di funzioni nel lambda calcolo.

Lezione n. 27 - Friday 29 May 2015

Seconda Prova in Itinere