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

Le lezioni

Diario delle lezioni dell'anno accademico 2011-2012

• Presentazione del corso. Problemi di decisione. Formalizzazione del concetto di sistema di transizione (algoritmo formale). Problema di decisione associato ad un insieme. Definizione di Automa a stati finiti. Algoritmo formale associato ad un automa.

• Formalizzazione della definizione di automa finito. Rappresentazione grafica. Rappresentazione Matriciale. Esempi di automa finito. Nozione di problema di decisione. Decidibilità e semidecidibilità.

• Laboratorio: introduzione alla programmazione object oriented. Motivazioni storiche. Le caratteristiche del linguaggio Java. Contronto tra le strutture dati implementate in C e in Java. Definizione dei tipi di dato astratto. Esempio di ADT: le liste; i costruttori (emptylist, cons). La specifica equazionale di head e tail sul tipo lista. Panoramica sulla teoria della calcolabilita'. La questione P=NP. Introduzione ai problemi di decisione. Algoritmi formali come sistemi dinamici discreti. Esempio preliminare di automa a stati finiti.

• Definizione di lunghezza della computazione. Rappresentazione di un automa come grafo. Monoide libero delle parole su un certo alfabeto. Somme Formali di parole. Rappresentazione di un automa come matrice di adiacenza del grafo. Calcolo dell'insieme delle parole accettate dall'automa come serie delle potenze successive della matrice.

• (laboratorio) (laboratorio) Valutazione dell'esecuzione di un automa finito deterministico. Algebra delle parole (concatenazione e serie formali di parole). Matrici e prodotto di matrici. Linguaggio riconosciuto da un automa. Automi non deterministici.

• Espressioni regolari. Equivalenza tra insiemi descritti da espressioni regolari e insiemi decidibili per automa a stati finiti. Algoritmo per il calcolo dell'espressione regolare associata ad un automa. Pumping Lemma per gli automi. Esempio di linguaggio non decidibile per automa.

• (laboratorio) (laboratorio) Automi finiti non deterministici con transizioni epsilon. Algoritmo formale associato ad un automa non deterministico. Equivalenza tra linguaggi decidibili per automa ed espressioni regolari. Esempio di conversione di un automa a stati non deterministico in uno deterministico equivalente. Teorema di Equivalenza tra espressioni regolari e automi.Trasformazione di un automa in espressione regolare.

• Definizione di Macchina di Turing. Algoritmo Formale associato ad una macchina di Turing. Problema decidibile per macchina di Turing. Definizione di tempo e spazio di arresto di una macchina di Turing a partire da un dato input. Definizione di complessita' di un problema decidibile per macchina di Turing. Definizione delle classi di complessita'. Ogni problema decidibile per macchina di Turing con complessita' T(n), per ogni $N$ e' decidibile in tempo $T'(n)$ dove$T'(n)=n$ se $n

• (laboratorio) 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. Dimostrazione del Pumping Lemma per gli insiemi decidibili per macchina di Turing con tempo di arresto lineare. Esempio di utilizzo su un esempio particolare. Separazione della classe di complessita` quadratica dalla classe a complessita` lineare.

• Definizione di Simulazione di un algoritmo formale tramite un altro algoritmo formale. Distinzione tra semantica operazionale e semantica denotazionale. Definizione di Macchina di Turing a seminastro. Simulazione della macchina di Turing tramite la macchina a seminastro.

• (laboratorio) (laboratorio) Definizione di macchine di Turing multinastro. Algoritmo associato ad una macchina multinastro. Teorema di simulazione delle macchine multinastro con le macchine a nastro singolo. Dimostrazione del teorema di speedup. Introduzione al concetto di computabilita'. Macchine di Turing non-deterministiche. P vs NP. Problemi NP-completi.

• Funzioni Ricorsive di Base Operazioni di chiusura per le funzioni Turing Computabili: composizione, concatenazione, ricorsione, minimalizzazione. Chiusura della classe delle funzioni Turing computabili rispetto allo schema di ricorsione. Chiusura della classe delle funzioni Turing computabili rispetto allo schema di minimalizzazione.

• Definizione della classe delle funzioni ricorsive. Esempi di funzioni ricorsive.

• prima prova di esonero

• Terminata l'implementazione del verificatore della congettura di Goldbach. Introdotto il concetto di esecuzione distribuita per l'esecuzione distribuita. Classe RMI. Correzione della prova in itinere: costruzione dell'automa deterministico dall'automa non deterministico, applicazioni del Pumping Lemma. Costruzione della Macchina di Turing per la conversione da unario a binario.

• (laboratorio) Attributi e metodi con qualificatore static e final. Incaplsulamento di classi. (laboratorio) Chiamate ricorsive a metodi. Terminato l'esempio delle liste. Dimostrazione che ogni funzione Turing computabile e' anche ricorsiva. Definizione di funzioni ricorsive primitive e relazione con il concetto di funzione ricorsiva totale. Funzione di Ackermann. Equivalenza tra funzioni ricorsive e macchine di Turing (continua la dimostrazione). Ogni funzione calcolabile e' ricorsiva. Definizione di macchina di Turing universale.

• Macchine di Turing Universali. Il problema dell'arresto. Indecidibilita' del problema dell'arresto. Introduzione e prime definizioni sul lambda calcolo. Induzione strutturale sui lambda termini. Variabili libere e varibili legate.

• (laboratorio) Metodi e classi astratte. Definizione dei costruttori. (laboratorio) Derivazione di classi. Concetto della inheritance. Creazione di istanze di classe. Introduzione al lambda calcolo. Definizione dell'insieme dei lambda termini. Lambda termini come funzioni. Lambda termini come dati. Astrazione e Applicazione. Variabili libere e variabili legate. Definizioni per induzione strutturale. Definizione della sostituzione semplice. Proprieta' di invarianza per permutazione della sostituzione. Lemma di non dipendenza dalle sostituzioni su variabili che non sono variabili libere del termine.

• Proprieta' della sostituzione. Relazioni sui lambda termini. Definizione di alpha equivalenza. Definizione di relazione che passa al contesto.

• (laboratorio) Classi astratte; esempio di liste di oggetti eterogenei. (laboratorio) Implementazione del crivello di Eratostene ad oggetti. Sostituzione e sostituzione a meno di alpha-equivalenza, Beta riduzione, Terminazione e Confluenza nel lambda calcolo. Programmazione nel lambda calcolo. Interi, Coppie, Triple, Proiezioni, Liste, Induzione sugli interi, Induzione sulle liste.

• Grafo sintattico di un lambda-termine. L'alpha equivalenza passa al contesto. Proprieta' di Church-Rosser. La chiusura transitiva di una relazione Church-Rosser e' Church-Rosser. Definizione di sostituzione. Definizione di beta-riduzione. Proprieta' della beta riduzione.

• (laboratorio) Implementazione OOP del crivello di Eratostene. Classi astratte. (laboratorio) Derivazione di classi astratte. Overloading di costruttori. Confluenza dell beta conversione. Proprieta' di Church-Rosser. Unicita' della Forma Normale. Esempi di riduzione.

• Beta equivalenza. Forma normale dei lambda termini. Utilizzo del lambda calcolo come dispositivo computazionale astratto Strategie di riduzione. Riduzione di testa. Riduzione sinistra. Strategie normalizzanti. Alberi di Bohm. Forma normale di testa. Risolubilita' di lambda termini.

• (laboratorio) Attributi e metodi di classe (static). Implementazione del crivello di Eratostene (versione distribuita). (laboratorio) Definizione di array di oggetti. Ancora sulla visibilita' di metodi (public/private). Codifica dei booleani; rappresentazione delle funzioni ricorsive di base; rappresentazione della composizione; Rappresentazione della minimalizzazione. Operatori di punto fisso nel lambda calcolo; teoremi di esistenza.

• Rappresentazione di altri tipi di dato nel lambda calcolo: booleani, coppie, liste. Risoluzione di equazioni ricorsive mediante uso di operatori di punto fisso. Il lambda calcolo come linguaggio di programmazione.