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

Le lezioni

Diario delle lezioni dell'anno accademico 2011-2012

Le lezioni si tengono nel secondo semestre con il seguente orario:

  • giovedì ore 11.00-14.00 - Aula 16 (lezione);
  • giovedì ore 14.00-16.00 9.00 - 11.00 - Aula computer (5) in Largo San Leonardo Murialdo 1 (laboratorio di programmazione per studenti IN410);
  • venerdì ore 8.00-11.00 - Aula 2 (lezione);
Lezione n. 1 - Thursday 23 February 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.
Lezione n. 2 - Friday 24 February 2012

  • Formalizzazione della definizione di automa finito. Rappresentazione grafica. Rappresentazione Matriciale. Esempi di automa finito. Nozione di problema di decisione. Decidibilità e semidecidibilità.
Lezione n. 3 - Thursday 1 March 2012

  • 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.
Lezione n. 4 - Friday 2 March 2012

  • 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.
Lezione n. 5 - Thursday 8 March 2012

  • (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.
Lezione n. 6 - Friday 9 March 2012

  • 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.
Lezione n. 7 - Thursday 15 March 2012

  • (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.
Lezione n. 8 - Friday 16 March 2012

  • 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
Lezione n. 9 - Thursday 22 March 2012

  • (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.
Lezione n. 10 - Friday 23 March 2012

  • 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.
Lezione n. 11 - Thursday 29 March 2012

  • (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.
Lezione n. 12 - Friday 30 March 2012

  • 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.
Lezione n. 13 - Thursday 5 April 2012

  • Definizione della classe delle funzioni ricorsive. Esempi di funzioni ricorsive.
Lezione n. 14 - Thursday 12 April 2012

  • prima prova di esonero
Lezione n. 15 - Thursday 19 April 2012

  • 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.
Lezione n. 16 - Thursday 26 April 2012

  • (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.
Lezione n. 17 - Friday 27 April 2012

  • 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.
Lezione n. 18 - Thursday 3 May 2012

  • (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.
Lezione n. 19 - Friday 4 May 2012

  • Proprieta' della sostituzione. Relazioni sui lambda termini. Definizione di alpha equivalenza. Definizione di relazione che passa al contesto.
Lezione n. 20 - Thursday 10 May 2012

  • (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.
Lezione n. 21 - Friday 11 May 2012

  • 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.
Lezione n. 22 - Thursday 17 May 2012

  • (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.
Lezione n. 23 - Friday 18 May 2012

  • 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.
Lezione n. 24 - Thursday 24 May 2012

  • (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.
Lezione n. 25 - Friday 25 May 2012

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

Per informazioni e commenti: pedicini@mat.uniroma3.it - Torna alla Home page - Ultima modifica: Mon Nov 26 15:29:24 CET 2012