Corso di Informatica 2 (IN2 - Modelli di Calcolo)

Le lezioni

Diario delle lezioni dell'anno accademico 2009-2010

• Presentazione del corso Presentazione del corso

• (Laboratorio 1) Richiami di architettura del calcolatore. Gestione dinamica della memoria. Classificazione degli errori di accesso alla memoria. Motivazioni per disciplinare gli accessi alla memoria. Java. Interpreti e compilatori. Portabilita' del codice. Opzioni del compilatore C. Introduzione alle classi nella programmazione object oriented.

• Algoritmo formale che decide un problema. Problemi di decisione, Concetto di Semidicidibilita'. Monoide libero delle parole di un certo alfabeto. Automa a stati finiti. Algoritmo associato ad un automa astati finiti. Insiemi Regolari. Automa che riconosce li insieme delle parole esteso con un carattere.

• Proprieta' di chiusura degli automi finiti. Concatenazione. Unione. Complemento. Espressioni Regolari Definizione di automa finito non-deterministico. Algoritmo associato ad un automa non-determiistico. Automi con epsilon-mosse. Equivalenza tra NFA e DFA. Espressioni regolari.

• (Laboratorio 2) Definizioni di classi. Metodi costruttori. Definizione di tipi di dato astratti. Costruttori di liste: emptylist, append. Implementazione di una classe. Compilazione di classi. Esecuzione di Java bytecode. Metodo main.

• Automi Non deterministici. Traduzione di un NFA in DFA. Equivalenza tra insiemi decidibili con NFA e con espressioni regolari. Macchine RAM. Algoritmo formale associato ad una macchina RAM.

• (Laboratorio 3) Attributi e metodi con qualificatore static e final. Incaplsulamento di classi. Chiamate ricorsive a metodi. Terminato l'esempio delle liste.

• Definizione di Macchina di Turing. Definizione di algoritmo associato ad una macchina di Turing. Decidibilita` per macchina di Turing. Semidicibilita' per macchina di Turing. Funzioni computabili per macchina di Turing. Concetto di Computazione associata ad un input. Considerazioni sulla cardinalita' di insiemi decidibili per macchina di Turing.

• Definizione del tempo di arresto di una macchina di Turing. Definizione di spazio di arresto. Definizione di complessita'. Classe di complessita' polinomiale. Caso della complessita' lineare. Separazione tra le classi DTIME(n^2) e DTIME(c n). Pumping-lemma per le macchine con tempo di arresto lineare.

• (Laboratorio 4) Metodi e classi astratte. Definizione dei costruttori. Derivazione di classi. Concetto della inheritance. Creazione di istanze di classe.

• Esempi di applicazione del Pumping-lemma. Decidibilita' dell'insieme 0^p 1^p in tempo c n log(n)

• Definizione ed esempi di simulazioni tra algoritmi. Equivalenza tra macchine a seminastro e macchine mononastro. Costo della simulazione.

• (Laboratorio 5) Classi astratte; esempio di liste di oggetti eterogenei. Implementazione del crivello di Eratostene ad oggetti.

• Definizione di macchina multinastro. Algoritmo associato ad una macchina multinastro. Vantaggi nell'esecuzione. Teorema di simulazione di una macchina multinastro con una mononastro. Valutazione del costo computazionale nella simulazione.

• Cambiamenti di alfabeto. Proprieta' prelimiari al Teorema di Speedup. Cambiamenti di alfabeto nelle macchine di Turing. Complessita'.

• Automi Finiti, applicazioni ed esercizi. Macchine di Turing e complessita': applicazioni ed esercizi.

• Classi di complessita' indipendenti dall'alfabeto e dal numero di nastri. Macchine di Turing speciali (alfabeto A={1}, autoconfinate nel seminastro positivo). Equvalenza tra macchine di Turing e macchine di Turing speciali. Costo della complessita' della simulazione.

• (Laboratorio 6)Implementazione OOP del crivello di Eratostene. Classi astratte. Derivazione di classi astratte. Overloading di costruttori.

• Rappresentazione dei numeri naturali in base 1 e in base >1. Decidibilita' di un insieme numerico. Indipendenza della decidibilita' dalla base scelta. Complessita` di un insieme numerico, relazione di complessita' in funzione della base.

• Definizione della classe delle funzioni ricorsive. Definizione di computabilita'. Equivalenza tra computabilita' e decidibilita' della funzione caratteristica del grafico della funzione (nel caso delle funzioni totali). Equivalenza tra funzioni parziali Turing computabili e semidecidibilita' del grafico della funzione. Funzioni ricorsive; funzioni base: successore, predecessore, funzione costante e funzione proiezione; schema di ricorsione, composizione, concatenazione e minimalizzazione.

• Ogni funzione computabile e' anche ricorsiva. Codifica delle macchine di Turing nelle funzioni ricorsive: la funzione di transizione associata ad un macchina di Turing e' una funzione ricorsiva.

• Teorema di equivalenza tra funzioni computabili e funzioni ricorsive: codifica della configurazione di input a partire dall'n-upla di interi rappresentata. Aritmetizzazione dello spazio delle configurazioni di una macchina di Turing.

• Teorema di equivalenza tra funzioni computabili e funzioni ricorsive. Funzioni ricorsive primitive. Funzioni ricorsive totali. Funzione di Ackermann.

• Funzioni ricorsive. Applicazioni. Funzioni definite per casi su domini ricorsivi. Caso delle funzioni parziali. Lambda Calcolo: funzioni sulle variabili: variabli libere, variabili legate, lunghezza di un lambda-termine. Induzione strutturale. Grafo sintattico di un lambda-termine.

• (Laboratorio 7) Attributi e metodi di classe (static). Implementazione del crivello di Eratostene (versione distribuita). Definizione di array di oggetti. Ancora sulla visibilita' di metodi (public/private).

• Definizione di lambda termini. Lemmi preliminari sulla sostituzione. Alfa equivalenza. Relazioni che passano al contesto. 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.

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

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