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

MAR 8.30 I, MER 8:30 I, GIO 10.30 H

Argomenti trattati a lezione

  1. 05/03/2019. [8:30 I] Presentazione del corso.
    Parte 1: Linguaggi Formali
    Alfabeti e linguaggi. 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. 06/03/2019. [8:30 I] Automi a stati finiti deterministici: descrizione modellistica e matematica. Definizione di linguaggio regolare. Esempi. Crescita esponenziale del numero degli stati del DFA che accetta stringhe con n-ultimo simbolo 0.
  3. 07/03/2019. [10:30 H] 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. 12/03/2019. [8:30 I] Automi con ε-transizioni. Definizioni e esempi. Equivalenza tra formalismi NFA e ε-NFA. Operazioni tra linguaggi. Espressioni regolari. Alcune proprietà algebriche delle espressioni regolari.
  5. 13/03/2019. [8:30 I] Costruzione di ε-NFA per una e.r. Calcolo delle espressioni regolari associate ad un DFA. Soluzione di sistemi di equazioni per espressioni regolari. Esempi. Regolarità dei linguaggi finiti.
  6. 14/03/2019. [10:30 H] Pumping Lemma per i linguaggi regolari. Applicazioni ed esempi.
  7. 19/03/2019. [8:30 I] Proprietà di chiusura dei linguaggi regolari e applicazioni. Risultati di decidibilità.
  8. 20/03/2019. [8:30 I] Le relazioni RM e RL. Il teorema di Myhill-Nerode.
  9. 21/03/2019. 9.30. [10:30 H] Esistenza ed Unicità dell'automa minimo. Algoritmi di minimizzazione di automi. Esempi.
  10. 26/03/2019. [8:30 I] Grammatiche libere dal contesto (CF). Linguaggio generato. La nozione di linguaggio libero dal contesto. Il linguaggio 0n1n e la sua collocazione. Relazioni tra l'insieme dei linguaggi regolari e quello dei liberi dal contesto. Esempi di derivazioni e loro alberi. Ambiguità.
  11. 27/03/2019. [8:30 I] Alberi di derivazione e derivazioni. Relazioni tra alberi e derivazioni. Eliminazione di simboli inutili (e test del vuoto). Eliminazione di ε-produzioni. Eliminazione di produzioni unitarie.
  12. 02/04/2019. [8:30 I] La forma normale di Chomsky. Cenno alla forma normale di Greibach. Il pumping lemma per i linguaggi liberi dal contesto.
  13. 03/04/2019. [8:30 I] Applicazioni del pumping lemma ed esercizi. Proprietà di chiusura dei linguaggi liberi. Proprietà di decidibilità dei linguaggi liberi.
  14. 04/04/2019. [10:30H] Gerarchia di Chomsky. Grammatiche lineari destre e sinistre. Grammatiche di tipo 0 e di tipo 1. Equivalenza tra la definizione monotona e quella dipendente dal contesto per le grammatiche di tipo 1. Generazione del linguaggio 0n1n2n. Decidibilità del problema dell'appartenenza per le grammatiche di tipo 1.
  15. 09/04/2019. [8:30 I] Calcolare con le grammatiche. Funzioni di base, somma e prodotto. Esercizi sui linguaggi.
  16. 10/04/2019. [8:30 I] Parte II: Tesi di Church e Computabilità
    Breve inquadramento storico. La nozione di algoritmo. (LUCIDI) 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. "
  17. 10/04/2019. [10:30H] 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).
  18. 16/04/2019. [8.30 I] 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.
  19. 17/04/2019. [8.30 I] Definizione per casi, div, mod. Esistenza di una funzione calcolabile totale non primitiva ricorsiva per diagonalizzazione. La funzione di Ackermann (riferimento) e le sue principali proprietà. Sommatoria e produttoria limitata, mu-operatore limitato.
  20. 30/04/2019. [8.30 I] (Buon) ordine tra coppie e terminazione della funzione di Ackermann. Il mu-operatore e l'insieme delle funzioni (parziali) ricorsive. Teorema di equivalenza tra le funzioni ricorsive parziali e le funzioni Turing-calcolabili. (LUCIDI)
  21. 02/05/2019. [10.30 H] Conclusione della dimostrazione del Teorema. Cenni alla while calcolabilità, allo spaghetti-code e al Teorema di Bohm-Jacopini. Tesi di Church. Pairing functions e loro inverse. Uso delle pairing functions: la funzione di Fibonacci.
  22. 06/05/2019. [8.30 H] Enumerazione di MdT. MdT Universale. Indecidibilità dell'Halting Problem e conseguenze. L'articolo originale di Alan Turing. Dimostrazione tradizionale e senza enumerazione sui linguaggi di programmazione.
  23. 07/05/2019. [8.30 I] Teorema Smn. Uso semplificato del Teorema smn. Insiemi ricorsivi e ricorsivamente enumerabili. Definizioni e proprietà principali. L'insieme K.
  24. 08/05/2019. [8.30 I] Il complementare dell'insieme K. Proprietà decidibili e semi-decidibili. Caratterizzazione degli insiemi ricorsivamente enumerabili. Ricorsività degli insiemi finiti e co-finiti. Riducibilità funzionale. Definizione ed esempi. Studio della relazione di riducibilità. Insiemi minimali per la relazione.
  25. 09/05/2019. [10.30 H] 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. Esercizi.
  26. 14/05/2019. [8.30 I] Esercitazione sulle riduzioni e sulla completezza. Indipendenza tra K ed il suo complementare.
  27. 15/05/2019. [8.30 I] 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.
  28. 16/05/2019. [10.30 H] Il Teorema di Rice-Shapiro (con dim). Applicazioni. Insiemi produttivi. Proprietà dei produttivi.
  29. 21/05/2019. [8.30 I] Insiemi creativi. Teorema di Myhill (no dim). Definizione di insieme semplice e sue proprietà. Teorema di esistenza di un insieme semplice.
  30. 22/05/2019. [8.30 I] Esercitazione sugli insiemi completi, riduzioni dal complementare di K.
  31. 23/05/2019. [10.30 H] 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.
  32. 28/05/2019. [8.30 I] Il problema PAL. Demo con A-Machine. Cenni allo speed-up theorem e alla tesi di Church computazionale. La classe P. La classe EXPTIME.
  33. 29/05/2019. [8.30 I] La MdT non deterministica. La classe NP. Collocazione di NP tra P e EXPTIME.
  34. 30/05/2019 [8:30 - 4 ore H] NP come guess and verify. Classi in spazio e principali risultati. Seminario sul significato fondazionale e l'importanza applicativa del problema SAT. Riduzioni. NP completezza di SAT (breve cenno alla dim). SAT solvers: come sfruttarli.
    Lucidi del seminario e Codici C per risolvere il sudoku.
  35. 05/06/2019. [8.30 I] NP completezza di 3SAT, NAESAT, INDEPENDENT SET e 3-COLORING.
  36. 05/06/2019. [10.30 H] Esercitazione in vista dell'esame.