Fondamenti dell'Informatica, A.A. 2023/2024

LUN 8.30, MAR 13:30 (*), MER 8.30

(*) Io o il dr. Romanello saremo in aula dalle 12.45 per ricevimento.

Argomenti trattati a lezione

  1. 04/03/2024. 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. 05/03/2024.
    Parte 1: Linguaggi Formali
    Alfabeti, stringhe, linguaggi. Automi a stati finiti deterministici: descrizione modellistica e matematica. Definizione di linguaggio regolare. Esempi.
  3. 06/03/2024. Regolarità dei linguaggi finiti. Crescita esponenziale del numero degli stati del DFA che accetta stringhe con n-ultimo simbolo 0. Discussione sul non determinismo. Automi a stati finiti non deterministici. Teoremi di equivalenza tra formalismi DFA e NFA. Esempi.
  4. 12/03/2023. Ric in aula (1 ora) Poi (2 ore): Dimostrazione formale del teorema di Rabin Scott. Cenni alla loro implementazione. Esempio di trasformazione da NFA e DFA evitando di analizzare troppi stati inutili. Automi con ε-transizioni. Definizioni e esempi. Equivalenza tra formalismi NFA e ε-NFA. Operazioni tra linguaggi. Espressioni regolari.
  5. 13/03/2024. Alcune proprietà algebriche delle espressioni regolari. Costruzione di ε-NFA per una e.r. Calcolo delle espressioni regolari associate ad un DFA. Soluzione di sistemi di equazioni per espressioni regolari. Esempi.
  6. 18/03/2024. Pumping Lemma per i linguaggi regolari. Applicazioni del pumping lemma ed esempi.
  7. 19/03/2024. Ric in aula (1 ora) Poi (2 ore): Risultati di decidibilità (vuoto, finito, infinito). Proprietà di chiusura dei linguaggi regolari.
  8. 20/03/2024. Relazioni di equivalenza e partizioni. Le relazioni RM e RL. Il teorema di Myhill-Nerode.
  9. 25/03/2024. 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.
  10. 26/03/2024. Ric in aula (2 ore) a cura del dr Riccardo Romanello
  11. 27/03/2024. 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.
  12. 03/04/2024. Ambiguità. Alberi di derivazione e derivazioni. Relazioni tra alberi e derivazioni. Riduzione alle forme normali. Eliminazione di simboli inutili. Eliminazione di ε-produzioni. Eliminazione di produzioni unitarie.
  13. 08/04/2024. La forma normale di Chomsky. Il pumping lemma per i linguaggi liberi dal contesto. Esercizi sulla applicazione del pumping lemma.
  14. 09/04/2024. Ric in aula (1 ora) a cura del dr Riccardo Romanello
    Poi (2 ore): Cenno alla forma normale di Greibach. Proprietà di chiusura dei linguaggi liberi. Proprietà di decidibilità dei linguaggi liberi. Grammatiche di tipo tipo 1.
  15. 29/03/2023. Generazione del linguaggio 0n1n2n. Decidibilità del problema dell'appartenenza per le grammatiche di tipo 1. Calcolare con le grammatiche. Funzioni di base, somma e prodotto.
  16. 15/04/2024. Equivalenza tra la definizione monotona e quella dipendente dal contesto per le grammatiche di tipo 1. Grammatiche di tipo 0 e la gerarchia di Chomsky.

    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.

  17. 16/04/2024. Ric in aula (1 ora) a cura del dr Riccardo Romanello.
    Poi (2 ore). Definizione formale di MdT. Descrizione istantanea e computazione. Relazioni con la nozione di algoritmo/programma. La nozione di funzione Turing calcolabile.
  18. 17/04/2024. Le tre funzioni di base e la loro implementazione con e senza ulteriori richieste aggiuntive. Il formalismo delle funzioni primitive ricorsive. Totalità delle funzioni primitive ricorsive ed esistenza di funzioni intuitivamente calcolabili e non primitive ricorsive.
  19. 22/04/2024. Esempi di funzioni primitive ricorsive: somma, prodotto, predecessore, differenza ed elevamento a potenza. Segno. Definizione per casi, div, mod. Produttoria, Sommatoria, mu operatore limitato.
  20. 23/04/2023. Ric in aula (1 ora) Poi (2 ore): Test di primalità, Pairing functions e loro inverse. Uso delle pairing functions: la funzione di Fibonacci. 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 (totalità) della funzione di Ackermann. Cenno alla diomostrazione che Ackermann non è primitiva ricorsiva.
  21. 24/04/2024. Il mu-operatore e l'insieme delle funzioni (parziali) ricorsive. Teorema di equivalenza tra le funzioni ricorsive parziali e le funzioni Turing-calcolabili. Tesi di Church.

    RESTO DEL PROGRAMMA

  22. 21/04/2023. Cenni alla while calcolabilità, allo spaghetti-code e al Teorema di Bohm-Jacopini. ??? Enumerazione di MdT. MdT Universale. Indecidibilità dell'Halting Problem e conseguenze. Dimostrazione tradizionale. Dimostrazione senza enumerazione sui linguaggi di programmazione. Proposizioni decidibili e semidecidibili. Teorema Smn. Uso semplificato del Teorema smn.
  23. 24/04/2023. Insiemi ricorsivi e ricorsivamente enumerabili. Definizioni e proprietà principali Esempi. L'insieme K e il suo complemento. Teorema di Caratterizzazione degli insiemi ricorsivamente enumerabili.
  24. 26/04/2023. Riducibilità funzionale. Definizione. 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. Insiemi completi. Completezza di K.
  25. 28/04/2023. Esempi di riduzione. Impiego di K per dimostrare la completezza degli altri insiemi completi. Esercitazione sulle riduzioni e sulla completezza.
  26. 03/05/2023. 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. 05/05/2023. Il Teorema di Rice-Shapiro (con dim). Applicazioni. Produttivita' di K.
  28. 13/05/2022. Insiemi produttivi. Proprietà dei produttivi rispetto alle riduzioni. Esercitazione sugli insiemi produttivi. Riduzioni dal complementare di K.
  29. 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.
  30. 18/05/2022. Parte III: Complessità Computazionale
    Problemi e linguaggi. Istanze. Rappresentazione degli interi. Problemi decisionali, funzionali, e di minimizzazione.
  31. 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.
  32. 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.
  33. 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.
  34. 27/05/2022. CIRCUIT VALUE e CIRCUIT SAT Teoremi di Cook-Levin
    SAT NP completezza di SAT. NP come guess and verify.
  35. 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.
  36. 01/06/2022. NP completezza di INDEPENDENT SET (e altri problemi su grafi), e del 3-COLORING. Polinomialita' del 2 coloring.
  37. 03/06/2022. Esercitazione in vista dell'esame.