Corso di Informatica 2 (IN2 - Modelli di Calcolo)

Le lezioni

Diario delle lezioni dell'anno accademico 2008-2009

• Presentazione del corso. Introduzione storica ai modelli di calcolo; relazione tra l'informatica teorica e lo sviluppo dell'informatica. Quadro italiano.

• Definizione di monoide libero definito su un insieme finito di generatori; nozione di alfabeto e di parole su quell'alfabeto; Definizione formale di algoritmo; definizione della lunghezza della computazione.

• Automi Finiti; Linguaggi Regolari: Espressioni Regolari; Esercizio: equivalenza. Esempio di problema decidibile per DFA.

• Macchine RAM; Definizione; Esempi; Ogni problema decidibile per automa finito, e' decidibile anche per macchina RAM.

• Passaggio da automa deterministico a macchina di Turing; Algoritmo associato a macchina di Turing; Decidibile per TM implica semidecidible per TM.

• Computabile per macchina di Turing; Rappresentazione grafica delle Macchine di Turing. Esercizi su algoritmi formali.

• Tempo di arresto; Classi di complessita'; Funzioni di Complessita'; Classi di complessita' sono definite su insiemi dati a meno di un numero finito di elementi. Esempio di valutazione del tempo di arresto di una macchina.

• Pumping Lemma per le Turing machines: applicazione per provare che un insieme non e' Turing decidibile in tempo lineare.

• Esercizi di utilizzo di Mathematica6 per sperimentare le macchine di Turing. Introduzione alla programmazione object oriented.

• Introdotto il concetto di simulazione di algoritmi; mostrato che modello TM simula modello DFA; introdotte macchine a seminastro.

• Teorema di simulazione e valutazione della complessita'.

• Classi, Oggetti, Linguaggi per l'esecuzione distribuita. Java: compilatore java, bytecode java.

• Simulazione di Algoritmi; Macchine di Turing a Seminastro.

• Macchine di Turing multinastro; teorema di equivalenza tra i modelli di calcolo; costo computazionale di simulazione.

• Macchine di Turing e cambiamenti di rappresentazione; Risultati sulla complessita'; Teorema di Speedup.

• Svolgimento di Esercizi sulle macchine di Turing e sulla complessita'.

• Cambiamenti di rappresentazione; complessita' e cambiamenti di alfabeto; Teorema di speedup per le macchine di Turing.

• Dimostrazione del Teorema di speedup;

• Funzioni computabili tramite macchine di Turing; Relazione tra Turing-decidibilita' e Turing-computabilita'.

• Funzioni ricorsive; equivalenza tra funzioni ricorsive e funzioni Turing computabili.

• Dimostrazione dell'implicazione Turing-computabile implica ricorsiva per una funzione sui naturali.

• Teorema di equivalenza tra funzioni Turing-computabili e funzioni ricorsive.

• codifiche ricorsive delle n-uple di naturali; schema di ricorsione multipla; indecidibilita' del problema dell'arresto.

• introduzione al lambda calcolo.

• {, December 9, 2008 from 9:00 AM to 11:00 AM}[[3]]<>

• Definizione della sostituzione semplice. Proprieta' della sostituzione semplice.

• Definizione della sostituzione. Definizione della alfa equivalenza. Relazioni che passano al contesto. Proprieta' della sostituzione.

• {, December 16, 2008 from 9:00 AM to 11:00 AM } Definizione della relazione di beta riduzione. Teorema di Church-Rosser (Confluenza del calcolo). [[3]]<>

• Beta Conversione. Strategie di Riduzione. Riduzione Sinistra. Riduzione di Testa. Risolubilita' di termini. Alberi di Bohm. Teorema di Bohm.

• Rappresentazione di Church per gli interi. Rappresentabilita' di funzioni nel lambda-calcolo. Teorema di lambda-definibilita'.

• Teorema di lambda-definibilita' per le funzioni ricorsive (composizione, concatenazione, minimalizzazione, ricorsione). Teoremi di punto fisso.

• Rappresentazione di altre strutture dati nel lambda calcolo. Coppie, Liste, Alberi.