IN410 - Informatica 2 - Modelli di Calcolo - AA 2016-2017

Lezioni

Diario delle lezioni dell'AA 2016-2017


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/esercitazione, Laboratorio Informatico/Aula 211);
  • [-] giovedì ore 9.00-11.00 (lezione, Aula 211)

Lezione n. 1 - Monday 27 February 2017

  • 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. Modello di esecuzione di Java. Definizione dei tipi di dato astratto. Specifica equazionale di funzioni su ADT. Esempio delle liste di interi. Implementazione in C dell'esempio.

Lezione n. 2 - Thursday 2 March 2017

  • 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 6 March 2017

  • Insiemi regolari. Proprieta` di chiusura degli insiemi regolari. Automi Non-deterministici. Automi con transizioni epsilon. Equivalenza tra la DFA-decidibilita` e NDFA-decidibilta`. Proprieta` di chiusura degli insiemi regolari. Automi Non-deterministici. Automi con transizioni epsilon. Equivalenza tra la DFA-decidibilita` e NDFA-decidibilta`.

Lezione n. 4 - Thursday 9 March 2017

  • Proposizione: ogni insieme regolare e' interpretazione di una qualche espressione regolare. Definizione di espressione regolare. Interpretazione di un'espressione regolare con un insieme. Proposizione: ogni insieme regolare e' interpretazione di un'espressione regolare.

Lezione n. 5 - Monday 13 March 2017

  • Costruzione dell'Automa NDF-epsilon che decide l'insieme interpretazione di una qualsiasi espressione regolare. Dimostrazione ed esempi. Introduzione alla Macchina di Turing. 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 16 March 2017

  • Esampio di insieme decidibile per macchina di Turing. Turing-decidibile implica Turing-semi-decidibile.

Lezione n. 7 - Monday 20 March 2017

  • Pumping Lemma per le macchine di Turing che decidono in tempo lineare. Applicazione del Pumping Lemma per mostrare che l'insieme 0^n1^n non puo' essere deciso in tempo lineare. Discussione di una macchina di Turing che decide lo stesso problema in tempo n Log(n).

Lezione n. 8 - Monday 27 March 2017

  • Definizione di simulazione tra algoritmi. Definizione di macchina di Turing a seminastro. Teorema di Simulazione tra macchine di Turing e macchine a seminastro. Costo di simulazione per le macchine di Turing con macchine a semi nastro. Illustrazione del crivello di Eratostene: studio comparativo tra versione ad allocazione statica e la versione object oriented. Implementazione del crivello di Eratostene. Crivello di Eratostene a oggetti: allocazione dinamica. Implementazione delle classi: Item, Sieve, Filter, Counter.

Lezione n. 9 - Thursday 30 March 2017

  • Macchina di Turing multi nastro. Equivalenza con la macchina di Turing.

Lezione n. 10 - Monday 3 April 2017

Lezione n. 11 - Thursday 6 April 2017

Lezione n. 12 - Thursday 13 April 2017

  • Prima Prova in Itinere

Lezione n. 13 - Thursday 20 April 2017

Lezione n. 14 - Monday 24 April 2017

Lezione n. 15 - Thursday 27 April 2017

Lezione n. 16 - Thursday 4 May 2017

  • Macchina di Turing Universale. Indecibilità del problema dell'arresto.

Lezione n. 17 - Monday 8 May 2017

  • Motivazione e inquadramento storico per l'introduzione del lambda calcolo come sistema intermedio per la rappresentazione formale dell'aritmetica. Definizione dei lambda termini. Discussione informale sulla valutazione del lambda calcolo come processo di calcolo. Definizione della sostituzione semplice per i lambda termini. Dimostrazione di alcune proprieta` della sostituzione semplice. Definizione di relazioni che passano al contesto. Implementazione del crivello di Eratostene utilizzando la classe BigInteger per la precisione arbitraria. Disegno e implementazione di una classe wrapper contenente più attributi utili per il trasporto di informazioni durante l'esecuzione dell'algoritmo (Token.java)

Lezione n. 18 - Thursday 11 May 2017

  • Rappresentazione di alcune funzioni booleane con i lambda termini. Corrispondenza di Curry-Howard tra le dimostrazioni del frammento implicativo della logica minimale e il lambda calcolo semplicemente tipato. Equazione di Scott e lambda calcolo puro. Lamba termini punto fisso per la valutazione: non terminazione.

Lezione n. 19 - Monday 15 May 2017

Lezione n. 20 - Thursday 18 May 2017

Lezione n. 21 - Monday 22 May 2017

Lezione n. 22 - Thursday 25 May 2017