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

MAR 10.30 TEAMS, GIO 8:30 TEAMS, VEN 10.30 TEAMS

Argomenti trattati a lezione

  1. 02/03/2021. Presentazione del corso (materiale, modalità di esame, 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. 04/03/2021.
    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. 06/03/2021. 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. 09/03/2021. 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. 11/03/2021. Calcolo delle espressioni regolari associate ad un DFA. Soluzione di sistemi di equazioni per espressioni regolari. Esempi. Pumping Lemma per i linguaggi regolari.
  6. 12/03/2021. Applicazioni del pumping lemma ed esempi. Proprietà di chiusura dei linguaggi regolari. Applicazioni ed esempi. Risultati di decidibilità.
  7. 16/03/2021. Relazioni di equivalenza e partizioni. Le relazioni RM e RL. Il teorema di Myhill-Nerode. Esistenza ed Unicità dell'automa minimo.
  8. 18/03/2021. Algoritmi di minimizzazione di automi. Esempi. Cenni alla complessità degli algoritmi e alle idee principali dietro l'algoritmo di Hopcroft. Esercizi sui linguaggi regolari.
  9. 19/03/2021. 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.
  10. 23/03/2021. 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.
  11. 25/03/2021. 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. Esercizio sulla applicazione del pumping lemma.
  12. 26/03/2021. Proprietà di chiusura dei linguaggi liberi. Proprietà di decidibilità dei linguaggi liberi. Grammatiche di tipo tipo 1. Generazione del linguaggio 0n1n2n.
  13. 30/03/2021. 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
  14. 08/04/2021. 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 nel testo) e gratuiti.
  15. 09/04/2021. 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).
  16. 13/04/2021 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.
  17. 15/04/2021. 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.
  18. 16/04/2021 Teorema di equivalenza tra le funzioni ricorsive parziali e le funzioni Turing-calcolabili.
  19. 20/04/2021. 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.
  20. 22/04/2021. Enumerazione di MdT. MdT Universale. Indecidibilità dell'Halting Problem e conseguenze. Dimostrazione tradizionale e senza enumerazione sui linguaggi di programmazione.
  21. 23/04/2021. 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.
  22. 27/04/2021. Teorema di Caratterizzazione degli insiemi ricorsivamente enumerabili. Riducibilità funzionale. Definizione. Studio della relazione di riducibilità. Indipendenza tra K ed il suo complementare.
  23. 29/04/2021. 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.
  24. 30/04/2021. Esercitazione sulle riduzioni e sulla completezza.
  25. 06/05/2021. 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.
  26. 07/05/2021. Il Teorema di Rice-Shapiro (con dim). Applicazioni. Insiemi produttivi. Proprietà dei produttivi rispetto alle riduzioni.
  27. 11/05/2021. [10.30 Video Streaming] Esercitazione sugli insiemi produttivi. Riduzioni dal complementare di K.
  28. 13/05/2021. 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.
  29. 14/05/2021. Parte III: Complessità Computazionale
    Problemi e linguaggi. Istanze. Rappresentazione degli interi. Problemi decisionali, funzionali, e di minimizzazione.
  30. 18/05/2021. Macchine di Turing a k nastri. Classi di Complessità in tempo deterministiche. Il problema PAL. Cenni allo speed-up theorem e alla tesi di Church computazionale. La classe P. La classe EXPTIME. Classi in spazio. La classi L e PSPACE.
  31. 20/05/2021. Principali relazioni tra classi in tempo ed in spazio.
    Il non determinismo. La MdT non deterministica. Le classi NP e NEXPTIME. Collocazione di NP tra P, PSPACE e EXPTIME.
  32. 21/05/2021. Riduzioni. Osservazioni e definizioni principali. Completezza per una classe. CIRCUIT VALUE e CIRCUIT SAT Teoremi di Cook-Levin
  33. 25/05/2020. SAT NP completezza di SAT. NP come guess and verify. NP completezza di 3SAT, NAESAT, Polinomialita' di 2 SAT
  34. 27/05/2020. SAT SOLVING. Breve storia degli approcci al SAT solving. SAT solving e il problema P vs NP. Risoluzione concreta di problemi NP via riduzione a SAT. Esempio (Sudoku). Codici C per risolvere il sudoku usando un SAT solver.
  35. 28/05/2020. NP completezza di INDEPENDENT SET (e altri problemi su grafi), e del 3-COLORING. Polinomialita' del 2 coloring.
  36. 01/06/2020. Esercitazione in vista dell'esame.