1;95;0c Agostino Dovier-Teaching

Fondamenti dell'Informatica, A.A. 2019/2020

MAR 10.30 C2, GIO 8:30 C2, VEN 10.30 C3

Argomenti trattati a lezione

  1. 10/03/2020. [10:30 VIDEO-STREAMING] Presentazione del corso (materiale, modalità di esame, contatti moodle, streaming Microsoft Teams). Richiami su equicardinalità di N, Z, e Q e su non numerabilità di P(N) e R Ricaduta dei risultati di cardinalità nella (non) calcolabilità.
  2. 12/03/2020. [8:30 VIDEO-STREAMING]
    Parte 1: Linguaggi Formali
    Alfabeti, stringhe, linguaggi. Automi a stati finiti deterministici: descrizione modellistica e matematica. Definizione di linguaggio regolare. Esempi. Regolarità dei linguaggi finiti. Crescita esponenziale del numero degli stati del DFA che accetta stringhe con n-ultimo simbolo 0.
  3. 13/03/2020. [10.30 VIDEO-STREAMING] Discussione sul non determinismo. Automi a stati finiti non deterministici. Cenni alla loro implementazione. Teoremi di equivalenza tra formalismi DFA e NFA. Esempio di trasformazione da NFA e DFA evitando di analizzare troppi stati inutili.
  4. 17/03/2020. [10:30 VIDEO STREAMING] Automi con ε-transizioni. Definizioni e esempi. Equivalenza tra formalismi NFA e ε-NFA. Operazioni tra linguaggi. Espressioni regolari. Alcune proprietà algebriche delle espressioni regolari. Costruzione di ε-NFA per una e.r.
  5. 19/03/2020. [8:30 VIDEO STREAMING] Calcolo delle espressioni regolari associate ad un DFA. Soluzione di sistemi di equazioni per espressioni regolari. Esempi. Pumping Lemma per i linguaggi regolari.
  6. 20/03/2020. [10:30 VIDEO STREAMING] Applicazioni del pumping lemma ed esempi. Proprietà di chiusura dei linguaggi regolari. Applicazioni ed esempi. Risultati di decidibilità.
  7. 24/03/2020. [10:30 VIDEO STREAMING] Relazioni di equivalenza e partizioni. Le relazioni RM e RL. Il teorema di Myhill-Nerode.
  8. 26/03/2020. [8:30 VIDEO STREAMING] Esistenza ed Unicità dell'automa minimo. Algoritmi di minimizzazione di automi. Esempi. Cenni alla complessità degli algoritmi e alle idee principali dietro l'algoritmo di Hopcroft.
  9. 27/03/2020. [10:30 VIDEO STREAMING] Esercitazione sui linguaggi regolari.
  10. 31/03/2020. [10:30 VIDEO STREAMING] Grammatiche libere dal contesto (CF). Linguaggio generato. La nozione di linguaggio libero dal contesto. Il linguaggio 0n1n e la sua collocazione. Esempi di derivazioni e loro alberi. Ambiguità. Alberi di derivazione e derivazioni. Relazioni tra alberi e derivazioni.
  11. 02/04/2020. [8:30 VIDEO-STREAMING] Riduzione alle forme normali. Eliminazione di simboli inutili (e test del vuoto). Eliminazione di ε-produzioni. Eliminazione di produzioni unitarie. La forma normale di Chomsky. Cenno alla forma normale di Greibach.
  12. 03/04/2020. [10:30 VIDEO-STREAMING] Relazioni tra l'insieme dei linguaggi regolari e quello dei liberi dal contesto. Grammatiche lineari destre e sinistre. Il pumping lemma per i linguaggi liberi dal contesto. Esercitazione sulla applicazione del pumping lemma.
  13. 08/04/2020. [10:30 VIDEO-STREAMING] Proprietà di chiusura dei linguaggi liberi. Proprietà di decidibilità dei linguaggi liberi. Grammatiche di tipo tipo 1. Generazione del linguaggio 0n1n2n.
  14. 09/04/2019. [8:30 VIDEO-STREAMING] Equivalenza tra la definizione monotona e quella dipendente dal contesto per le grammatiche di tipo 1. Decidibilità del problema dell'appartenenza per le grammatiche di tipo 1. Grammatiche di tipo 0 e la gerarchia di Chomsky. Calcolare con le grammatiche. Funzioni di base, somma e prodotto.
    Brevi vacanze pasquali
  15. 14/04/2020. [10:30 Video Streaming] Parte II: Tesi di Church e Computabilità
    Breve inquadramento storico. La nozione di algoritmo. Il formalismo delle Macchine di Turing (Video). Esempi di semplici macchine di Turing. Tra i vari simulatori in rete, ne indico due con una sintassi basata su quintuple (come nell'articolo originale e le dispense) e gratuiti.
  16. 16/04/2020. [8:30 Video Streaming] Definizione formale di MdT. Descrizione istantanea e computazione. Relazioni con la nozione di algoritmo/programma. La nozione di funzione Turing calcolabile. Le tre funzioni di base e la loro implementazione con e senza ulteriori richieste (e cenni sulle possibili richieste aggiuntive).
  17. 17/04/2020. [10.30 Video Streaming] Il formalismo delle funzioni primitive ricorsive. Totalità delle funzioni primitive ricorsive ed esistenza di funzioni intuitivamente calcolabili e non primitive ricorsive. Esempi di funzioni primitive ricorsive: somma, prodotto, predecessore, differenza ed elevamento a potenza. Segno. Definizione per casi, div, mod. Sommatoria e produttoria limitata, mu-operatore limitato.
  18. 21/04/2020. [10.30 Video Streaming] Esistenza di una funzione calcolabile totale non primitiva ricorsiva per diagonalizzazione. La funzione di Ackermann (riferimento) e le sue principali proprietà. (Buon) ordine tra coppie e terminazione della funzione di Ackermann. Il mu-operatore e l'insieme delle funzioni (parziali) ricorsive.
  19. 23/04/2020. [8.30 Video Streaming] Teorema di equivalenza tra le funzioni ricorsive parziali e le funzioni Turing-calcolabili.
  20. 24/04/2020. [10.30 Video Streaming] Tesi di Church. Cenni alla while calcolabilità, allo spaghetti-code e al Teorema di Bohm-Jacopini. Pairing functions e loro inverse. Uso delle pairing functions: la funzione di Fibonacci.
  21. 28/04/2020. [10.30 Video-Streaming] Enumerazione di MdT. MdT Universale. Indecidibilità dell'Halting Problem e conseguenze. Dimostrazione tradizionale e senza enumerazione sui linguaggi di programmazione.
  22. 30/04/2020. [8.30 Video-Streaming] Proposizioni decidibili e semidecidibili. Teorema Smn. Uso semplificato del Teorema smn. Insiemi ricorsivi e ricorsivamente enumerabili. Definizioni e proprietà principali Esempi. L'insieme K e il suo complemento. Proprietà decidibili e semi-decidibili.
  23. 06/05/2020. [10.30 Video-Streaming] Teorema di Caratterizzazione degli insiemi ricorsivamente enumerabili. Riducibilità funzionale. Definizione. Studio della relazione di riducibilità. Indipendenza tra K ed il suo complementare.
  24. 07/05/2020. [8.30 Video Streaming] Insiemi minimali per la relazione. Ruolo degli insiemi ricorsivi. Esempi di riduzione. Proprietà di quasi-ordine della relazione. Insiemi completi. Completezza di K. Impiego di K per dimostrare la completezza degli altri insiemi completi.
  25. 08/05/2020. [10.30 Video Streaming] Esercitazione sulle riduzioni e sulla completezza.
  26. 12/05/2020. [10.30 Video Streaming] Il primo teorema di ricorsione (con dim). Conseguenze del primo teorema di ricorsione. Esempi. Il secondo Teorema di Ricorsione (senza dim). Proprietà dei programmi estensionali e non. Il Teorema di Rice (con dim) e le sue applicazioni.
  27. 14/05/2020. [8.30 Video Streaming] Il Teorema di Rice-Shapiro (con dim). Applicazioni. Insiemi produttivi. Proprietà dei produttivi rispetto alle riduzioni.
  28. 15/05/2020. [10.30 Video Streaming] Esercitazione sugli insiemi produttivi. Riduzioni dal complementare di K.
  29. 19/05/2020. [8.30 Video Streaming] Proprietà dei produttivi: sottoinsieme r.e. e infinito. Insiemi creativi. Teorema di Myhill (no dim). Definizione di insieme semplice e sue proprietà. Teorema di esistenza di un insieme semplice.
  30. 21/05/2020. [8.30 Video Streaming] Parte III: Complessità Computazionale
    Problemi e linguaggi. Rappresentazione degli interi. Problemi decisionali e funzionali. Macchine di Turing a k nastri. Classi di Complessità in tempo deterministiche. Il problema PAL.
  31. 26/05/2020. [10.30 Video Streaming] Cenni allo speed-up theorem e alla tesi di Church computazionale. La classe P. La classe EXPTIME. In non determinismo. La MdT non deterministica. Le classi NP e NEXPTIME.
  32. 28/05/2020. [8.30 Video Streaming] Collocazione di NP tra P e EXPTIME. Riduzioni.
  33. 29/05/2020. [10.30 Video Streaming] Classi in spazio e principali risultati. CIRCUIT VALUE e CIRCUIT SAT Teoremi di Cook-Levin
  34. 04/06/2020. [8.30 Video Streaming] SAT NP completezza di SAT. NP come guess and verify. SAT SOLVING. Codici C per risolvere il sudoku usando un SAT solver.
  35. 05/06/2020. [10.30 Video Streaming] NP completezza di 3SAT, NAESAT, INDEPENDENT SET e 3-COLORING.
  36. 09/06/2020. [10.30 Video Streaming] Esercitazione in vista dell'esame.