Fondamenti dell'Informatica, A.A. 2025/2026

2026: LUN 8.30 C2, MER 8:30 C2, GIO 8.30

Argomenti trattati a lezione

  1. 02/03/2026. 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. 04/03/2026.
    Parte 1: Linguaggi Formali
    Alfabeti, stringhe, linguaggi. Automi a stati finiti deterministici: descrizione modellistica e matematica. Definizione di linguaggio regolare. Esempi.
  3. 05/03/2026. Crescita esponenziale del numero degli stati del DFA che accetta stringhe con n-ultimo simbolo 0. Introduzione al non determinismo. Automi a stati finiti non deterministici.
  4. 09/03/2026. Teoremi di equivalenza tra formalismi DFA e NFA (con dimostrazione). Esempio di trasformazione da NFA e DFA evitando di analizzare troppi stati inutili. Regolarità dei linguaggi finiti. Esercizi.
  5. 11/03/2026. Automi con ε-transizioni. Definizioni e esempi. Equivalenza tra formalismi NFA e ε-NFA. Operazioni tra linguaggi. Espressioni regolari. Alcune proprietà algebriche delle espressioni regolari.
  6. 12/03/2026. Costruzione di ε-NFA per una e.r. Calcolo delle espressioni regolari associate ad un DFA. Soluzione di sistemi di equazioni per espressioni regolari. Esempi.
  7. 16/03/2026. Pumping Lemma per i linguaggi regolari. Applicazioni del pumping lemma ed esempi. Risultati di decidibilità (vuoto, finito, infinito).
  8. 18/03/2026. Relazioni di equivalenza e partizioni. Le relazioni RM e RL. Il teorema di Myhill-Nerode.
  9. 19/03/2026. 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.
  10. 23/03/2026. Proprietà di chiusura dei linguaggi regolari. Grammatica (lineare destra) dedotta da un DFA. Grammatiche libere dal contesto (CF). Linguaggio generato. La nozione di linguaggio libero dal contesto. Il linguaggio 0n1n.
  11. 25/03/2026. Esempi di derivazioni e loro alberi. Ambiguità. Alberi di derivazione e derivazioni. Relazioni tra alberi e derivazioni. Forme normali di Chomsky e Greibach
    Riduzione alle forme normali. Eliminazione di simboli inutili. Eliminazione di ε-produzioni. Eliminazione di produzioni unitarie. Esempi. La forma normale di Chomsky.
  12. 26/03/2026. Il pumping lemma per i linguaggi liberi dal contesto. Esercizi sulla applicazione del pumping lemma.
  13. 30/03/2026. Proprietà di chiusura dei linguaggi liberi. Proprietà di decidibilità dei linguaggi liberi.
  14. 01/04/2026. Generazione del linguaggio 0n1n2n. Grammatiche di tipo 1. Decidibilità del problema dell'appartenenza per le grammatiche di tipo 1. Calcolare con le grammatiche. Funzioni di base, somma, differenza, prodotto e loro collocazione nella gerarchia di Chomsky.

    RESTO DEL CORSO

  15. 08/04/2026. 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.
  16. 09/04/2026. 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. 14/04/2025. 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 aggiuntive.
  18. 16/04/2025. Il formalismo delle funzioni primitive ricorsive. Totalità delle funzioni primitive ricorsive ed esistenza di funzioni totali non primitive ricorsive. Esempi di funzioni primitive ricorsive: somma, prodotto, predecessore, differenza ed elevamento a potenza. Segno. Definizione per casi, div, mod.
  19. 23/04/2025. Produttoria, Sommatoria, mu operatore limitato. 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.
  20. 24/04/2025. 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.
  21. 28/04/2025. Enumerazione di MdT. MdT Universale. Indecidibilità dell'Halting Problem e conseguenze. Dimostrazione tradizionale. Dimostrazione senza enumerazione sui linguaggi di programmazione.
  22. 30/04/2025. Teorema Smn. Suo significato anche nei linguaggi di programmazione. Uso semplificato del Teorema smn. Proposizioni decidibili e semidecidibili. Insiemi ricorsivamente enumerabili.
  23. 05/05/2025. Insiemi ricorsivi e ricorsivamente enumerabili. Definizioni e proprietà principali Esempi. L'insieme K e il suo complementare. Teorema di Caratterizzazione degli insiemi ricorsivamente enumerabili.
  24. 07/05/2025. 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. 08/05/2025. Impiego di K per dimostrare la completezza degli altri insiemi completi. Esercitazione sulle riduzioni e sulla completezza.
  26. 12/05/2025. 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/2025. Il Teorema di Rice-Shapiro (con dim). Applicazioni. Produttivita' di K. Insiemi produttivi. Prova diretta di non r.e. di un produttivo. Proprietà dei produttivi: sottoinsieme r.e. e infinito.
  28. 15/05/2025. Proprietà dei produttivi rispetto alle riduzioni. Esercitazione sugli insiemi produttivi. Riduzioni dal complementare di K.
  29. 19/05/2025. Insiemi creativi. Teorema di Myhill. Definizione di insieme semplice e sue proprietà. Teorema di esistenza di un insieme semplice.
  30. 21/05/2025. Parte III: Complessità Computazionale
    Problemi e linguaggi. Istanze. Rappresentazione degli interi. Problemi decisionali, funzionali, e di minimizzazione. Macchine di Turing a k nastri. Classi di Complessità in tempo deterministiche. La classe P. Il problema PAL.
  31. 22/05/2025. Cenni allo speed-up theorem e alla tesi di Church computazionale. Il non determinismo. La MdT non deterministica. Definizioni principali. La classe NP. Inclusione tra P e NP. Il problema del millennio.
  32. 26/05/2025. Classi in spazio. Le classi L e PSPACE. Principali relazioni tra classi in tempo ed in spazio: in particolare: L, P, NP, PSPACE e EXPTIME. Riduzioni. Osservazioni e definizioni principali. Completezza per una classe. Simulatore:
  33. 28/05/2025. CIRCUIT VALUE e CIRCUIT SAT Teoremi di Cook-Levin
    SAT NP completezza di 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.
  34. 04/06/2025. NP come guess and verify. NP completezza di 3SAT, NAESAT, Polinomialita' di 2 SAT NP completezza di INDEPENDENT SET (e altri problemi su grafi), e del 3-COLORING. Polinomialita' del 2 coloring.
  35. 05/06/2025. (2 ore). Esercitazione in vista dell'esame.

    COSE NON VISTE

    Parentesi: Alcuni risultati di indecidibilità dei linguaggi liberi. Cenni alla while calcolabilità, allo spaghetti-code e al Teorema di Bohm-Jacopini.