IN410 - Calcolabilità e Complessità - AA 2021-2022

Lezioni

Diario delle lezioni dell'AA 2021-2022


Le lezioni si tengono al I semestre con il seguente orario:
  • [-] lunedì ore 10.00-12.00 (lezione, Aula M3, nuovo blocco aule);
  • [-] mercoledì ore 10.00-12.00 (lezione, Aula 009, edificio C Aula A, Edificio di Fisica, Via della Vasca Navale 84);
  • [-] venerdì ore 10.00-12.00 (lezione/esercitazione, Laboratorio di Informatica, nuovo blocco aule)

Lezione n. 1 - Monday 20 September 2021

  • Presentazione del corso. Cenni storici intorno al concetto di calcolabilita`. Algoritmi Formali.

Lezione n. 2 - Wednesday 29 September 2021

  • Automi a stati finiti. Descrizione del modello di computazione a stati finiti. Decidibilità per automa a stati finiti. Insiemi Decidibili e Insiemi Semidecidibili. Algoritmo Formale associato ad un automa a stati finiti. Rappresentazione Grafica degli Automi a stati finiti. Semianello delle serie formali sul monoide libero delle parole di alfabeto A. Matrice sul semianello delle serie formali associata ad un automa finito. Formula del l'esecuzione del l'automa. Estrazione del linguaggio deciso dal l'automa a partire dal la formula dell'esecuzione.

Lezione n. 3 - Friday 1 October 2021

  • Esercitazione con Wolfram Mathematica.

Lezione n. 4 - Monday 4 October 2021

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

Lezione n. 5 - Wednesday 6 October 2021

  • Equivalenza tra la DFA-decidibilita` e NDFA-decidibilta`. Proposizione: ogni insieme regolare e` interpretazione di una qualche espressione regolare. Definizione di espressione regolare. Interpretazione di un'espressione regolare con un insieme. Costruzione dell'epsilon-NDFA che decide l'insieme interpretazione di una qualsiasi espressione regolare. Dimostrazione ed esempi.

Lezione n. 6 - Friday 8 October 2021

  • Esercitazione Automi e Macchine di Turing

Lezione n. 7 - Monday 11 October 2021

  • Definizione di Macchina di Turing. Spazio delle configurazioni per una Macchina di Turing. Algoritmo associato ad una macchina di Turing. Insiemi decidibili per macchina di Turing. Turing-decidibile implica Turing-semi-decidibile. Macchina di Turing che decide l'insieme $0^n1^n$.

Lezione n. 8 - Wednesday 13 October 2021

  • 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 pu\`o essere deciso in tempo lineare. Dimostrazione del Pumping Lemma. Discussione di una macchina di Turing che decide lo stesso problema in tempo n Log(n).

Lezione n. 9 - Friday 15 October 2021

  • Esercitazione Automi e Macchine di Turing

Lezione n. 10 - Monday 18 October 2021

  • Simulazione di algoritmi. Definizione di macchina di Turing a seminastro.

Lezione n. 11 - Wednesday 20 October 2021

  • Esempio Macchina multinastro. Simulazione di una macchina multinastro tremite una macchina di Turing.

Lezione n. 12 - Friday 22 October 2021

  • Traduzione di un automa $\eps$-NDFA in automa DFA.

Lezione n. 13 - Monday 25 October 2021

  • Macchine di Turing speciali. Teorema di simulazione. Rappresentazione degli interi. Decidibilità di insiemi numerici. Turing calcolabilità.

Lezione n. 14 - Wednesday 27 October 2021

  • La classe delle funzioni Turing calcolabili è chiusa per composizione, coppia, ricorsione primitiva e minimalizzazione.

Lezione n. 15 - Friday 29 October 2021

  • Dimostrazione che la classe delle funzioni ricorsive è Turing computabile. Esempi di funzioni ricorsive. Funzioni Ricorsive: equivalenza tra Turing computabilità e funzioni ricorsive. Definizione di funzione ricorsiva primitiva. Ogni funzione ricorsiva primitiva è totale. Funzioni ricorsive totali e funzioni ricorsive totali non ricorsive primitive.

Lezione n. 16 - Wednesday 3 November 2021

  • Dimostrazione che la classe delle funzioni ricorsive \`e Turing computabile. Esempi di funzioni ricorsive.

Lezione n. 17 - Friday 5 November 2021

  • Esercizi su automi a stati finiti, macchine di Turing e Funzioni ricorsive.

Lezione n. 18 - Wednesday 10 November 2021

  • *** esonero ***

Lezione n. 19 - Monday 15 November 2021

  • Equivalenza tra Turing computabili e ricorsive. Funzioni Ricorsive: funzione caratteristica dell'insieme dei numeri pari, codifica ricorsiva del prodotto cartesiano di interi, schema di ricorsione generalizzato.

Lezione n. 20 - Wednesday 17 November 2021

  • Turing computabile implica ricorsiva. Ricorsivita` delle funzioni Turing-computabili.

Lezione n. 21 - Monday 22 November 2021

  • Semidecidibilita` del Problema dell'arresto

Lezione n. 22 - Wednesday 24 November 2021

  • Funzioni Costruibili in Tempo

Lezione n. 23 - Friday 26 November 2021

  • Esercizi sulle funzioni ricorsive.

Lezione n. 24 - Monday 29 November 2021

  • Macchine non-deterministiche

Lezione n. 25 - Wednesday 1 December 2021

  • Macchine di Turing Non-deterministiche. Equivalenza tra semidecidibilita` deterministica e decidibilita` del prodotto cartesiano. Macchine deterministiche con oracolo, witness di una proiezione. Definizione dell'insieme dei lambda-termini. Interpretazione di alcuni lambda-termini come funzioni.

Lezione n. 26 - Friday 3 December 2021

  • Esercizi sulle funzioni costruibili in tempo

Lezione n. 27 - Monday 6 December 2021

Lezione n. 28 - Wednesday 8 December 2021

  • Lambda Calcolo. Definizione di sostituzione semplice. Proprieta` della sostituzione semplice.

Lezione n. 29 - Friday 10 December 2021

  • Lambda Calcolo.

Lezione n. 30 - Monday 13 December 2021

  • La beta-riduzione. Definizione della beta-riduzione e della beta-equivalenza. Principali proprieta` della beta-riduzione. Terminazione e confluenza. Strategia di riduzione di testa e relative proprieta`.

Lezione n. 31 - Wednesday 15 December 2021

  • Riduzione di Testa. Proprieta` di Church-Rosser. Dimostrazione che la \[Beta]-riduzione ha la proprieta` di Church-Rosser. Unicita` della forma normale. Riduzione di testa. Termini Risolubili. Equivalenza tra termini e risolubilita`. Risolubilita` di lambda-termini. Caratterizzazione della risolubilita`.

Lezione n. 32 - Friday 17 December 2021

  • Esercizi su beta-riduzione. Numerali di Church. Principio di Induzione. Esempi di funzioni rappresentate mediante l'induzione.

Lezione n. 33 - Monday 20 December 2021

  • Teorema di Lambda-definibilita` Rappresentazione dei Booleani nel lambda-calcolo. Operazioni logiche: congiunzione, disgiunzione, negazione, implicazione. Presentazione delle funzioni ricorsive.

Lezione n. 34 - Wednesday 22 December 2021

  • Rappresentazione di altri tipi di dato. Liste e Alberi.

Lezione n. 35 - Friday 7 January 2022

  • Grafi di condivisione. Esercizi sulle riduzioni mediante i grafi di condivisione.