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

Le lezioni

Diario delle lezioni dell'anno accademico 2012-2013

• Presentazione del corso. Introduzione storica alla Teoria della calcolabilita'. Definizione di Algoritmo formale di alfabeto A. Spazio delle configurazioni di un algoritmo.

• Definizione di Automa a stati finiti. Algoritmo di decisione associato ad un automa. Rappresentazione grafica di un automa a stati finiti. Semianello delle serie formali sul monide libero delle parole di un certo alfabeto. Rappresentazione matriciale degli automi. Calcolo del linguaggio riconosciuto dall'automa utilizzando la rappresentazione matriciale.

• Definizione di disciplina di programmazione ad oggetti. Introduzione al concetto di classe come struttura dati costituita da attributi e metodi. Esempio pratico di programma java. Compilazione ed esecuzione. Utilizzo di un editor. Utilizzo dell'ausilio di compilazione makefile.

• Automi a stati finiti non-deterministici. Algoritmo formale associato ad un automa non deterministico. Insiemi decidibili per automa a stati finiti. Operazioni di chiusura degli insiemi regolari (somma, concatenazione, star).

• Costruttori di classe. Variabili di classe. Creazione di un'istanza di classe (operatore new). Overloading di metodi Tipi di base per il linguaggio Java. Confronto tra l'uso delle variabili in Java e nel linguaggio C. Ereditarieta' tra classi. Classi derivate. Automi non-deterministici con transizioni epsilon. Equivalenza tra automi non-deterministici ed automi deterministici. Un insieme e' regolare se e solo se esiste un automa a stati finiti non deterministico che lo decide. Chiusura della classe degli insiemi regolari per somma, concatenazione e star.

• 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.

• Esempio di ereditarieta'. La classe Item. Definizione della classe IntegerList (lista di interi) derivata da Item. Costruttori di classe. Metodi astratti. Classi astratte. Overriding di metodi. Liste di oggetti eterogenei. Introduzione al crivello di Eratostene. Allocazione di memoria statica e allocazione dinamica. Automa a stati finiti non deterministici generalizzati (con transizioni etichettate con espressioni regolari). Procedura di costruzione dell'espressione regolare associata ad un automa.

• 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). Proprieta' elementari soddisfatte dagli insiemi decidibili in tempo T(n). Pumping Lemma per la classe di complessita' lineare DTIME(cn).

• implementazione della classe Filter, terminata l'implementazione del Crivello di Eratostene Metodi per l'accessibilita' di attributi. Introduzione della classe BigInteger. Cenni sulla documentazione di classi java (javadoc). Attributi di classe (static). Dimostrazione ed esempi di applicazione del pumping lemma. Definizione di simulazione tra algoritmi formali.

• Esonero

• Tesi di Church e Tesi di Church-Turing. Definizione di equivalenza tra modelli di calcolo. Definizione di macchina di Turing a seminastro. Simulazione tra algoritmi. Costruzione della macchina di Turing a seminastro che simula la computazione di una Macchina di Turing.

• Macchine di Turing multinastro. Definizione dell'algoritmo associato. Dimostrazione di equivalenza tra macchine multinastro e macchine di Turing. Valutazione del costo di complessita` della simulazione di una macchina multinastro con una mononastro.

• Implementazione del crivello utilizzando la classe BigInteger. Definizione e implementazione di una classe Token da utilizzare nella implementazione di un verificatore della congettura di Goldbach. Cambio di rappresentazione. Utilizzo di un alfabeto esteso per accelerare la computazione. Teorema di accelerazione lineare (speed-up).

• Decidibilita' di insiemi di numeri naturali. Rappresentazione posizionale di interi. Indipendenza della decidibilita' dalla rappresentazione scelta. Definizione di funzione computabile per macchina di Turing. Configurazione iniziale e finale. Equivalenza tra decidibilita' e computabilita' della funzione caratteristica. Equivalenza tra semidicidibilta' e computabilita' di una funziona parziale.

• Utilizzo della classe BigInteger nella implementazione del crivello di Eratostene. Il concetto dell'incapsulamento nella OOP. Programmata la classe Token per l'incapsulamento dell'intero a precisione arbitraria da utilizzare nel Crivello. Definizione di funzione computabile per macchina di Turing. Chiusura dell'insieme delle funzioni computabili per le operazioni di composizione, concatenazione, ricorsione primitiva, minimalizzazione. Definizione delle funzioni ricorsive di base: addizione, predecessore, funzioni costanti, funzioni proiezione. Definizione del insieme delle funzioni ricorsive. Proposizione: ogni funzione ricorsiva e' computabile per macchina di Turing.

• Dimostrazione che le funzioni: differenza, sup, inf, e la funzione caratteristica della relazione < (minore di) sono funzioni ricorsive. Definizione di insieme ricorsivo. Gli insiemi ricorsivi con le operazioni insiemistiche di unione finita, intersezione finita e complemento formano un'algebra di Boole.

• Schema di ricorsione multipla. Funzione somma iterata. Funzione definita per casi. Funzione caratteristica dei numeri pari. Divisione intera per 2. Funzione logaritmo intero in base 2. Funzione ricorsiva di codifica delle coppie di interi (e relativa decodifica). Generalizzazione a n-uple.

• Dimostrazione che ogni funzione Turing computabile e' ricorsiva. Conseguenze del Teorema: ogni funzione ricorsiva si puo` scrivere utilizzando una sola volta il costrutto di minimalizzazione.

• Utilizzo dei packages. Esempio di compilazione di classi appartenenti ad un package. Utilizzo della classe di incapsulamento Token nell'implementazione di un verificatore della congettura di Goldbach. Definizione del problema: congettura di Goldbach. Soluzione dinamica utilizzando le classi gia` definite per il Crivello di Eratostene. Definizione della nuova classe Token. Chiarimenti sul modello di accessibilita` ad attributi e modelli definibili in Java. I modificatori private e public. Proprieta` della sostituzione semplice nel lambda calcolo. Relazioni binarie sui lambda termini. Relazioni che passano al contesto. Compatibilita` tra relazioni PAC e sostituzione. Definizione di alpha equivalenza. Prime proprieta`.

• Proprieta` di base dell'alpha equivalenza. Caratterizzazione della piu` piccola relazione che contiene la alpha equivalenza e passa al contesto. Definizione dell'insieme dei lambda termini come classi di equivalenza rispetto alla relazione alpha. Compatibilita` tra sostituzione e alpha equivalenza. Definizione di sostituzione a meno della rinomina delle variabili legate. Lemmi e prime proprieta` della nuova nozione di equivalenza.

• Esistenza delle macchine di Turing universali. Codice associato ad una macchina di Turing di alfabeto {0,1}. Indecidibilita' del problema dell'arresto. Definizione della sostituzione a meno di alpha equivalenza. Proprieta' di base della nuova nozione di sostituzione. Chiusura transitiva di una relazione. Proprieta' di Church-Rosser. Lemma sulla proprieta' di Church-Rosser per relazioni definite come chiusura transitiva di relazioni Church-Rosser.

• Definizione della relazione di beta riduzione (beta-0) e di beta conversione. Proprieta' della beta conversione. Compatibilita' tra beta-conversione e alpha equivalenza. Definizione dei termini in forma normale. Definizione di termine normalizzabile e fortemente normalizzabile. Teorema: la beta conversione ha la proprieta' di Church-Rosser.

• Proposizione: la beta conversione e' un arelazione che passa al contesto. Forma normale di testa, Risolubilita' di lambda termini. Funzioni rappresentabili. Rappresentazione degli interi. Rappresentazione delle funzioni di base: costante a zero, proiezioni, successore, addizione, prodotto. Rappresentazione delle funzioni composte. Teorema di punto fisso (esistenza dell'operatore di punto fisso per ogni termine). Rappresentazione dell'operatore di minimaliz