Corso di Informatica 2 (IN410 - Modelli di Calcolo)

Le lezioni

Diario delle lezioni dell'anno accademico 2010-2011

• Presentazione del corso: orari, libri di testo, modalita' d'esame. 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 coputazione. Definizione di Automa Finito. Algoritmo Formale associato ad un automa finito. 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.

• 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. Proprieta' di chiusura degli insiemi decidibili per automa (somma, prodotto e star). Linguaggi regolari.

• Automi finiti non deterministici con transizioni epsilon. Algoritmo formale associato ad un automa non deterministico. Equivalenza tra linguaggi decidibili per automa ed espressioni regolari.

• Introduzione alla programmazione object oriented. Confronto tra i tipi definiti dall'utente in C (struct) e le classi. Introduzione del linguaggio Java. Bytecode Java e Java Virtual Machine. Primi passi di programmazione di una classe per le liste. Compilazione di una classe.

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

• Algoritmo formale associato ad una RAM. Esempio di programmazione di una RAM. Ogni insieme decidibile per automa a stati finiti puo' essere descritto da un'espressione regolare. Modello RAM. Linguaggio di programmazione delle RAM.

• Algoritmo Formale associato ad una macchina RAM. 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

• Pumping Lemma per i problemi decidibili in tempo lineare. Separazione tra la classe di complessita' lineare e quella quadratica. Simulazione di algoritmi.

• Macchine di Turing a seminastro. Equivalenza tra macchine di Turing a seminastro e macchine di Turing. Simulazione di algoritmi.

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

• Generalizzazione dello schema di ricorsione alle funzioni a piu' valori. Codifica ricorsiva delle coppie e piu' in generale di n-uple di naturali. Equivalenza tra funzioni Turing computabili e funzioni ricorsive.

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

• Equivalena tra funzioni ricorsive e macchine di Turing (continua la dimostrazione). Ogni funzione calcolabile e' ricorsiva. Definizione di macchina di Turing universale.

• Implementazione del crivello di Eratostene in Java. Costrutti tipici della programmazione object oriented: classi astratte, pubbliche, private. Overloading di metodi, overriding, ereditarieta', costruttori di classe.

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

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

• Derivazione delle classi del crivello di Eratostene per la gestione di interi a precisione arbitraria. Metodi ed attributi di classe (static). Attributi costanti (final). Conversione da intero a stringa.

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

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