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

LUN 10.30, MER 8:30 TEAMS, VEN 8.30

Argomenti trattati a lezione

  1. 28/02/2022. Presentazione del corso (materiale, modalità di esame, etc) 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. 02/03/2022.
    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. 04/03/2022. 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. 07/03/2022. 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. 09/03/2022. Calcolo delle espressioni regolari associate ad un DFA. Soluzione di sistemi di equazioni per espressioni regolari. Esempi. Pumping Lemma per i linguaggi regolari.
  6. 11/03/2022. Applicazioni del pumping lemma ed esempi. Proprietà di chiusura dei linguaggi regolari. Applicazioni ed esempi. Risultati di decidibilità.
  7. 14/03/2022. Relazioni di equivalenza e partizioni. Le relazioni RM e RL. Il teorema di Myhill-Nerode.
  8. 16/03/2022. 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. Esercizi.
  9. 18/03/2022. Grammatiche libere dal contesto (CF). Linguaggio generato. La nozione di linguaggio libero dal contesto. Grammatica (lineare destra) dedotta da un DFA. Il linguaggio 0n1n. Inclusione stretta tra l'insieme dei linguaggi regolari e quello dei linguaggi liberi dal contesto. Esempi di derivazioni e loro alberi. Ambiguità. Alberi di derivazione e derivazioni. Relazioni tra alberi e derivazioni.
  10. 21/03/2022. 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. 23/03/2022. Il pumping lemma per i linguaggi liberi dal contesto. Esercizi sulla applicazione del pumping lemma.
  12. 28/03/2022. Proprietà di chiusura dei linguaggi liberi. Proprietà di decidibilità dei linguaggi liberi. Grammatiche di tipo tipo 1. Generazione del linguaggio 0n1n2n.
  13. 04/04/2022. [Lezione da remoto]
    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.
  14. 06/04/2022. [Lezione da remoto] 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. 08/04/2022. [Lezione da remoto] 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. 11/04/2022. [Lezione da remoto] 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. 13/04/2022. [AULA AGAIN] 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. Cenni alla while calcolabilità, allo spaghetti-code e al Teorema di Bohm-Jacopini.
  18. 20/04/2022. Esercitazione. Pairing functions e loro inverse. Uso delle pairing functions: la funzione di Fibonacci. Esercizi su linguaggi regolari e liberi.
  19. 22/04/2022. Teorema di equivalenza tra le funzioni ricorsive parziali e le funzioni Turing-calcolabili. Tesi di Church.
  20. 27/04/2022. Enumerazione di MdT. MdT Universale. Indecidibilità dell'Halting Problem e conseguenze. Dimostrazione tradizionale e senza enumerazione sui linguaggi di programmazione.
  21. 29/04/2022. 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. 02/05/2022. Teorema di Caratterizzazione degli insiemi ricorsivamente enumerabili. Riducibilità funzionale. Definizione.
  23. 04/05/2022. Studio della relazione di riducibilità. Proprietà di quasi-ordine della relazione. Indipendenza tra K ed il suo complementare. Insiemi minimali per la relazione. Ruolo degli insiemi ricorsivi. Esempi di riduzione. Insiemi completi. Completezza di K. Impiego di K per dimostrare la completezza degli altri insiemi completi.
  24. 06/05/2022. Esercitazione sulle riduzioni e sulla completezza.
  25. 09/05/2022. 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. 11/05/2022. Il Teorema di Rice-Shapiro (con dim). Applicazioni. Produttivita' di K
  27. 13/05/2022. Insiemi produttivi. Proprietà dei produttivi rispetto alle riduzioni. Esercitazione sugli insiemi produttivi. Riduzioni dal complementare di K.
  28. 16/05/2022. Proprietà dei produttivi: sottoinsieme r.e. e infinito. Insiemi creativi. Teorema di Myhill. Definizione di insieme semplice e sue proprietà. Teorema di esistenza di un insieme semplice.
  29. 18/05/2022. Parte III: Complessità Computazionale
    Problemi e linguaggi. Istanze. Rappresentazione degli interi. Problemi decisionali, funzionali, e di minimizzazione.
  30. 19/05/2021 [Giovedi', II fascia] Parentesi: Alcuni risultati di indecidibilità dei linguaggi liberi.
    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.
  31. 23/05/2022. La classe P. La classe EXPTIME. Classi in spazio. Le classi L e PSPACE. Principali relazioni tra classi in tempo ed in spazio.
    Collocazione di L, P, PSPACE e EXPTIME.
  32. 25/05/2022. Il non determinismo. La MdT non deterministica. Collocazione di NP e NEXPTIME nel diagramma: L, P, PSPACE e EXPTIME. Riduzioni. Osservazioni e definizioni principali. Completezza per una classe.
  33. 27/05/2022. CIRCUIT VALUE e CIRCUIT SAT Teoremi di Cook-Levin
    SAT NP completezza di SAT. NP come guess and verify.
  34. 30/05/2022. NP completezza di 3SAT, NAESAT, Polinomialita' di 2 SAT 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. 01/06/2022. NP completezza di INDEPENDENT SET (e altri problemi su grafi), e del 3-COLORING. Polinomialita' del 2 coloring.
  36. 03/06/2022. Esercitazione in vista dell'esame.