IN410 - Calcolabilità e Complessità - AA 2019-2020

Lezioni

Diario delle lezioni dell'AA 2019-2020


Le lezioni si tengono al I semestre con il seguente orario:
  • [-] lunedì ore 11.00-13.00 (lezione, Aula M4);
  • [-] mercoledì ore 11.00-13.00 (lezione, Aula 009);
  • [-] venerdì ore 9.00-11.00 ore 11.00-13.00 (lezione/esercitazione, C - Edificio Fisica a Vasca Navale Laboratorio di Informatica)

Lezione n. 1 - Monday 23 September 2019

  • Presentazione del corso. Modalita` di esame. Orario delle lezioni. Cenni storici intorno al concetto di calcolabilita`, Macchine di Turing. Automi. Lambda-calcolo. Rappresentabilita`. Alfabeto finito. 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.

Lezione n. 2 - Wednesday 25 September 2019

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

Lezione n. 3 - Friday 27 September 2019

  • Introduzione a Wolfram Mathematica

Lezione n. 4 - Monday 30 September 2019

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

Lezione n. 5 - Wednesday 2 October 2019

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

Lezione n. 6 - Friday 4 October 2019

  • 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. 7 - Monday 7 October 2019

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

Lezione n. 8 - Wednesday 9 October 2019

  • DFA-decidibile implica Turing decidibile. Esempio di insieme decidibile per macchina di Turing. Turing-decidibile implica Turing-semi-decidibile. Macchina di Turing che decide l'insieme $0^n1^n$ in tempo quadratico.

Lezione n. 9 - Friday 11 October 2019

  • Esercitazione Automi e Macchine di Turing.

Lezione n. 10 - Monday 14 October 2019

  • Pumping Lemma. Dimostrazione del Pumping Lemma. Discussione di una macchina di Turing che decide lo stesso problema in tempo n Log(n). Definizione di simulazione tra algoritmi.

Lezione n. 11 - Friday 18 October 2019

  • Definizione di macchina di Turing a seminastro. Simulazione di macchine mono-nastro con macchine a semi-nastro. Macchine di Turing multi-nastro. Teorema di simulazione di una macchina multinastro con una macchina mononastro. Considerazioni sul costo della simulazione.

Lezione n. 12 - Monday 21 October 2019

  • Cambiamenti di alfabeto. Invarianza della decidibilita` per cambiamento di alfabeto. Teorema di speed-up. Dimostrazione del teorema di speed-up.

Lezione n. 13 - Wednesday 23 October 2019

  • Rappresentazione degli interi. Decidibilità di insiemi numerici. Costo computazionale della conversione da una base ad un'altra.

Lezione n. 14 - Friday 25 October 2019

  • Espressione regolare associata ad un automa non deterministico. Composizione Parallela di Macchine di Turing. Relazione tra Semidecidibilità e decidibilità.

Lezione n. 15 - Monday 28 October 2019

  • La classe delle funzioni Turing calcolabili è chiusa per composizione, coppia, ricorsione primitiva e minimalizzazione. Turing computabilità delle funzioni aritmetiche di base: somma, predecessore, costanti e proiezioni. Dimostrazione che la classe delle funzioni ricorsive è Turing computabile. Esempi di funzioni ricorsive.

Lezione n. 16 - Wednesday 30 October 2019

  • Funzioni Ricorsive: equivalenza tra Turing computabilità e funzioni ricorsive. Definizione di funzione ricor- siva primitiva. Ogni funzione ricorsiva primitiva è totale.

Lezione n. 17 - Monday 4 November 2019

  • Ricorsività delle funzioni Turing-computabili

Lezione n. 18 - Wednesday 6 November 2019

  • Esempi di funzioni ricorsive parziali definite per casi. Simulazione di Automi per macchine di Turing. Esempi di insiemi DFA-decidibili.

Lezione n. 19 - Friday 8 November 2019

  • Esempi di insiemi semi-decidibili. Esempio di trasformazione di un automa non-deterministico in uno deterministico.

Lezione n. 20 - Monday 18 November 2019

  • Semidecidibilità del Problema dell'arresto. Macchina di Turing universale. Esistenza (per ogni alfabeto) di un insieme che è semi-decidibile ma non è decidibile.

Lezione n. 21 - Wednesday 20 November 2019

  • Definizione di T-timer. Definizione di Funzione Costruibile in Tempo. Primi esempi di funzioni costruibili in tempo. Proprietà di chiusura. Ogni funzione costruibile in tempo è anche Turing computabile. Ogni funzione Turing computabile è maggiorata da una funzione costruibile in tempo.

Lezione n. 22 - Friday 22 November 2019

  • Costruzione della Gerarchia di Classi di complessità in Tempo

Lezione n. 23 - Monday 25 November 2019

  • Macchine di Turing non deterministiche. Esistenza di insiemi decidibili la cui proiezione è semidecidibile ma non decidibile. Definizione di classe di complessità non-deterministica basata sulla decidibilità degli insiemi proiezione.

Lezione n. 24 - Wednesday 27 November 2019

  • Macchine di Turing con oracolo. Relazione tra macchine di Turing con oracolo e macchine di Turing non-deterministiche. Confronto tra le classi di complessità deterministiche e le due non-deterministiche (proiezioni e oracolo). Teorema di equivalenza. Equivalenza delle classi di complessità derivanti dalle diverse nozioni di calcolo non-deterministico. Classi di complessità P ed NP.

Lezione n. 25 - Friday 29 November 2019

  • Definizione dell'insieme dei lambda-termini. Interpretazione di alcuni lambda-termini come funzioni. Definizione di sostituzione semplice. Proprietà della sostituzione semplice.

Lezione n. 26 - Monday 2 December 2019

Lezione n. 27 - Wednesday 4 December 2019

Lezione n. 28 - Friday 6 December 2019

Lezione n. 29 - Monday 9 December 2019

Lezione n. 30 - Wednesday 11 December 2019

Lezione n. 31 - Friday 13 December 2019

Lezione n. 32 - Monday 16 December 2019

Lezione n. 33 - Wednesday 18 December 2019

Lezione n. 34 - Friday 20 December 2019

Lezione n. 35 - Monday 23 December 2019