IN410 - Informatica 2 - Modelli di Calcolo

Le lezioni si tengono al II semestre con il seguente orario:

• [-] lunedì ore 9.00-11.00 (lezione, Aula 211);
• [-] lunedì ore 11.00-13.00 (lezione pratica, Laboratorio Informatico/Aula 211);
• [-] giovedì ore 9.00-11.00 (lezione, Aula 211)

Lezione n. 1 - Monday 22 February 2016

Presentazione del corso. Modalita` di esame. Orario delle lezioni. Cenni storici intorno al concetto di calcolabilita`, Macchine di Turing. Automi. Lambda-calcolo. Funzioni ricorsive. Introduzione del concetto di Sistema di Transizione. Definizione di Algoritmo Formale. Rappresentabilita`. Alfabeto finito. Monoide delle parole di un certo alfabeto. Definizione di problema decidibile. Definizione di problema semidecidibile.

Lezione n. 2 - Thursday 25 February 2016

Computazione associata ad un algoritmo formale. Esempio di Algoritmo Formale. Descrizione del modello di computazione a stati finiti. Definizione di automa a stati finiti. Definizione dell'algoritmo associato. Insiemi decidibili per automa. Esercizio sulla decidibilita` per automa finito. Rappresentazione come grafo degli automi. Rappresentazione come matrice di adiacenza. Semianello delle serie formali sul monoide libero delle parole di alfabeto A. Matrice sul semianello delle serie formali associata ad un automa finito. Formula dell'esecuzione dell'automa. Estrazione del linguaggio deciso dall'automa a partire dalla formula dell'esecuzione.

Lezione n. 3 - Monday 29 February 2016

Algebra di Kleene. Le matrici a elementi in un algebra di Kleene Formano un'algebra di Kleene. Formula dell'Esecuzione di un automa. Calcolo dell'insieme deciso da un automa a partire dalla sua formula dell'esecuzione. Insiemi regolari. Algebra di Kleene delle Matrici. Formula dell'esecuzione di un automa. Insiemi regolari. Concetto di programmazione object oriented. Compilatore e esecutore. La java virtual machine. Confronto tra la compilazione in C e in Java. Definizione di classe. Il metodo main(). L'overloading di metodi.

Lezione n. 4 - Thursday 3 March 2016

Automa Finito Non-deterministico. Insiemi regolari. Proprieta` di chiusura degli insiemi regolari. Automi Non-deterministici. Automi con transizioni epsilon.

Lezione n. 5 - Monday 7 March 2016

Il concetto di costruttore di classe in java. Definizione della classe delle liste. Il concetto di ereditarieta`' tra classi. La definizione di una classe IntegerList derivata dalla classe Liste.

Lezione n. 6 - Thursday 10 March 2016

Equivalenza tra la DFA-decidibilita` e NDFA-decidibilta`. Definizione di espressione regolare. Interpretazione di un'espressione regolare con un insieme. Proposizione: ogni insieme regolare e' interpretazione di un'espressione regolare. Proposizione: ogni insieme regolare e' interpretazione di una qualche espressione regolare. Definizione di automa non deterministico generalizzato. Procedura per costrui`re l'espressione regolare associata ad un automa.

Lezione n. 7 - Monday 14 March 2016

Lezione n. 8 - Thursday 17 March 2016

Lezione n. 9 - Monday 21 March 2016

Lezione n. 10 - Thursday 24 March 2016

Lezione n. 11 - Thursday 31 March 2016

Lezione n. 12 - Monday 4 April 2016

Lezione n. 13 - Thursday 7 April 2016

Lezione n. 14 - Monday 18 April 2016

Lezione n. 15 - Thursday 21 April 2016

Lezione n. 16 - Thursday 28 April 2016

Proprieta' di chiusura delle funzioni Turing Computabili: le funzioni definite per composizione seriale, composizione parallela, ricorsione primitiva, minimalizzazione di funzioni Turing computabili sono a loro volta Turing coputabili. Funzioni base che sono Turing computabili: successore, predecessore, funzioni costanti, funzioni proiezione. La classe delle funzioni ricorsive: ogni funzione che si ottiene a partire dalle funzioni base applicando un numero finito di volte le costruzioni rispetto alle quali le funzioni Turing computabili sono chiuse, fornisce una funzione Turing computabile.

Lezione n. 17 - Monday 2 May 2016

Funzioni Ricorsive: alcune funzioni aritmetiche che appartengono alla classe delle funzioni ricorsive. Insiemi ricorsivi: singleton, unione finita, intersezione finita, complemento di insiemi ricorsivi sono ricorsivi. Somme limitate di funzioni ricorsive sono ricorsive. Schema di Ricorsione primitiva generalizzata alle funzioni a piu' valori. Teorema di ricorsione delle funzioni Turing computabili: ogni funzione calcolabile con una macchina di Turing appartiene alla classe delle funzioni ricorsive.

Lezione n. 18 - Thursday 5 May 2016

Lezione n. 19 - Monday 9 May 2016

Alcune proprieta' della sostituzione semplice. Definizione di relazione alpha tlambda termini. Proprieta' elementari della relazione alpha tra lambda termini. Fine implementazione del verificatore per la congettura di Goldbach. Discussione sull'utilizzo del criterio delle ruote per ottimizzare la generazione dei numeri primi.

Lezione n. 20 - Thursday 12 May 2016

Definizione dell'insieme dei lambda-termini. Corrispondenza con la deduzione naturale (del sistema implicativo minimale). Nozione di sostituzione di variabile.

Lezione n. 21 - Monday 16 May 2016

Lezione n. 22 - Thursday 19 May 2016

Esempio di rappresentazione di una funzione tramile i lambda termni. Legame tra sostituzione e valutazione.

Lezione n. 23 - Monday 30 May 2016