Fondamenti di informatica

Termine del corso

Si avvisano gli studenti che lezioni del corso termineranno giovedì 29 maggio. Il 30 maggio e la settimana successiva si terranno esercitazioni a cura del tutor del corso. L'ultimo incontro con la docente per un'esercitazione aperta è fissato per giovedì 12 giugno

Ripresa lezioni del vecchio modulo 2

Si avvisano gli studenti che devono sostenere l'esame da 12 cfu che le lezioni riguardanti argomenti in programma nel modulo 2 del vecchio corso riprenderanno a partire da mercoledì 23 aprile.

Lezioni sulle grammatiche formali

Si avvisano gli studenti che devono sostenere l'esame da 12 cfu che a partire dal 28 marzo e fino a nuova comunicazione le lezioni riguarderanno argomenti non in programma nel modulo 2 del vecchio corso e che, pertanto, non fanno parte del loro programma di esame

AULA LEZIONI DEL MERCOLEDI'

Si avvisano gli studenti che il mercoledì le lezioni si terranno in aula 18 anziché in aula 3PP2

Per gli studenti che devono sostenere l'esame da 12 cfu. Per ciascuno degli appelli, e con le medesime date, verranno aperte su Delphi anche le prenotazioni corrispondenti al corso da 12 cfu. Prenotarsi è necessario per accedere alle prove d'esame. Gli studenti che devono sostenere la prova relativa al modulo 2 si presenteranno alla prova scritta (durante la quale risponderanno alle domande corrispondenti al programma del modulo 2). Gli studenti che devono sostenere la prova relativa al modulo 1 dovranno contattare a mezzo posta elettronica il Prof. Gambosi.

Lezione aperta: esercizi e domande poste dagli studenti

Il ruolo delle costanti nella complessità dei problemi. Esercitazione sulle dimostrazioni di NP-completezza e di coNP-completezza.

Esercitazione sulle dimostrazioni di NP-completezza: dal problema Ciclo Hamiltoniano ai problemi Percorso Hamiltoniamo, Long Path e Commesso Viaggiatore (TSP); dal problema 3-colorabilità ai problemi k-colorabilità (con k costante) e colorabilità.

Esercitazione sulle dimostrazioni di NP-completezza: i problemi Vertex Cover, Independent Set, Clique, Dominating Set.

Il ruolo del teorema di Cook-Levin nella congettura fondamentale della Teoria della Complessità Computazionale. Dimostrazioni di NP-completezza. Esercizio: NP-completezza di 3SAT. Teorema di Ladner (solo enunciato) e struttura di NP. Struttura di NP e coNP

Il teorema di Cook-Levin

Introduzione alla classe NP: algortmi non deterministici; esempi di problemi in NP e algoritmi non deterministici che li decidono (in tempo polinomiale): 3SAT, CLIQUE, CIRCUITO HAMILTONIANO

Dalla complessità di linguaggi alla complessità di problemi di decisione: linguaggio associato a un problema decisionale, linguaggio delle istanze, linguaggio complemento e linguaggio associato al problema complemento. Relazione fra complessità del linguaggio associato a un problema e complessità del linguaggio delle istanze

Problemi: istanze, soluzioni possibili, soluzioni effettive. Tipi di problemi: ricerca, enumerazione, ottimizzazione, decisione. Formalizzazione di problemi di decisione. Codifica dell'insieme delle istanze: codifiche ragionevoli e irragionevoli.

Classi complemento: coP, coNP, coPSPACE, coEXPTIME, coNEXPTIME. Equivalenza delle classi deterministiche con le corrispondenti classi complemento. La classe coNP e la seconda Congettura della Teoria della Complessità Computazionale. Chiusura di coNP rispetto alla riducibilità polinomiale. Linguaggi coNP-completi.

Riducibilità polinomiale. Chiusura di una classe rispetto a una riducibilità. Completezza di un problema per una classe rispetto a una riducibilità. Problemi NP-completi. Congettura fondamentale della Teoria della Complessità Computazionale.

Delimitazione temporale alla decisione di linguaggi appartenenti a NTIME[f(n)] quando f è una funzione time-constructible. Inclusione di NTIME[f(n)] in DTIME[2^{O(f(n))}] quando f è una funzione time-constructible. Le classi P, NP, PSPACE, NPSPACE, EXPTIME, NEXPTIME e relazioni di inclusione (improprie). P contenuto strettamente in EXPTIME (solo enunciato). PSPACE = NPSPACE (solo enunciato).

Esercizi: unione, intersezione e complemento di linguaggi decidibili e accettabili

Classi di complessità: deterministiche, non deterministiche, classi complemento e relazioni fra esse. Gap-theorem (solo enunciato), funzioni time- e space-constuctible e teoremi di gerarchia (solo enunciati)

Misure di complessità: assiomi di Blum; funzioni dtime, dspace, ntime, nspace e loro relazioni. Decidibilità dei linguaggi accettabili in tempo (spazio) f(n) per ogni funzione f totale e calcolabile. Correlazione polinomiale fra modelli di calcolo

Grammatiche regolari: automi a stati finiti non deterministici e inclusione della classe dei linguaggi regolari nella classe dei linguaggi accettati da un ASFND; proprietà di chiusura dei linguaggi regolari; espressioni regolari.

Introduzione alla teoria della complessità

Grammatiche regolari: definizioni, pumping lemma per le grammatiche regolari (enunciato) e inclusione stretta della classe dei linguaggi regolari nella classe dei linguaggi context-free, automi a stati finiti (deterministici) e inclusione della classe dei linguaggi accettati da un ASFD nella classe dei linguaggi regolari

Grammatiche e linguaggi context-free: automi a pila e macchine di Turing; automi a pila non deterministici e deterministici e linguaggi context-free; alberi sintattici e ambiguità; linguaggi context-free e linguaggi di programmazione

Grammatiche e linguaggi context-free: pumping lemma e inclusione propria della classe dei linguaggi context-free nella classe dei linguaggi di tipo 1; unione, intersezione e complemento dei linguaggi context-free. Definizioni di automa a pila e di accettazione di una parola da parte di un automa a pila

Decidibilità dei linguaggi generati da grammatiche di tipo 1. Introduzione alle grammatiche di tipo 2 ed esempi

Equivalenza fra Macchina di Turing e Grammatica Formale: per ogni linguaggio  L generato da una grammatica esiste una macchinadi Turing che accetta L. Esercizio: grammatica che genera il linguaggio delle parole binarie contenenti un numero pari di 1

Esercizio: generazione delle parole nella forma xx con x parola non vuota nell'alfabeto {a,b} (seconda parte). Equivalenza fra Macchina di Turing e Grammatica Formale: per ogni lingaggio accettabile L esiste una grammatica che genera L

La gerarchia di Chomsky. Gerarchia di Chomsky e ε-produzioni. Esercizio: generazione delle parole nella forma xx con x parola non vuota nell'alfabeto {a,b} (prima parte)

Introduzione ai modelli generative e alle grammatiche formali. Esempi ed esercizi

Lezione di 3 ore.

Simulazione della macchina di Turing universale mediante un programma in PascalMinimo. Esercitazione: simulazione di macchine non deterministiche mediante programmi in PascalMinimo (non in programma).

Modelli di calcolo e la tesi di Church-Turing. Il linguaggio PascalMinimo e sua simulazione mediante Macchina di Turing.

Lezione di 3 ore.

Indecidibilità dell'Halting Problem. Riduzioni many-to-one fra linguaggi: definizioni e ruolo della riducibilità ai fini della dimostrazione della decidibilità/accettabilità o della non decidibilità/non accettabilità dei linguaggi. Esempio di riduzione (lucidi 23-30, non in programma)

Esistenza di linguaggi non accettabili: il metodo della diagonalizzazione. L'Halting Problem: definizione e accettabilità

Linguaggi, linguaggi accettabili, linguaggi decidibili. Funzioni, funzioni totali, funzioni calcolabili. Relazione fra accettabilità/decidibilità di linguaggi e calcolabilità di funzioni.

Lezione di 3 ore.

La macchina di Turing Universale.

Esercitazione: progetto di un riconoscitore che decida se il suo input è una parola nella forma xx (Lucidi della lezione 3, dal lucido 35 al termine)

Struttura dell'insieme delle quintuple. Insieme non totale. Macchine deterministiche e non deterministiche. Interpretazione del non determinismo. Equivalenza dei modelli deterministico e non deterministico.

Macchine di tipo trasduttore e riconoscitore. Modelli di macchine di Turing: ad un nastro, a k nastri a testine indipendenti, a k nastri a testine solidali, operanti su alfabeto generico o binario. Equivalenza dei modelli introdotti.

Lezione di 3 ore.

Esempi di macchine di Turing e introduzione al concetto di simulazione (Lucidi della lezione 3, fino al lucido 35)

Definizione formale di macchina di Turing. Esempi di macchine di Turing. Alfabeti e parole. Stati globali, transizioni, computazioni (deterministiche) di macchine di Turing.

Introduzione al corso: problemi istanze, procedimenti risolutivi. Analisi di Turing del processo di calcolo. Introduzione informale alla Macchina di Turing: una macchina a tre nastri per eseguire la somma di due numeri naturali.

Lucidi della lezione 34: costanti, NP-completezza e oltre NP

Lucidi della lezione 33: prove di NP-completezza

Lucidi della lezione 32: prove di NP-completezza

Lucidi della lezione 31: NP-completezza

Lucidi della lezione 30: il teorema di Cook-Levin

Lucidi della lezione 29: caratterizzazione alternativa della classe NP

Lucidi della lezione 28: la classe NP

Esercizi: la classe NP

Esercizi: la classe P

Dispensa 9: la classe NP

Dispensa 8: la classe P

Dispensa 7: linguaggi e problemi

Lucidi della lezione 27: complessità dei problemi decisionali

Lucidi della lezione 26: problemi e codifiche

Lucidi della lezione 25: classi complemento

Lucidi della lezione 24: riducibilità polinomiale

Lucidi della lezione 23: funzioni time- e space-constructible e specifiche classi di complessitè

Lucidi della lezione 22: classi di complessità

Esercizi: linguaggi e complessità

Dispensa 6: linguaggi e complessità

Lucidi della lezione 21: misure di complessità

Lucidi della lezione 20: dalle grammatiche regolari alle espressioni regolari e introduzione alla Teoria della Complessità

Lucidi della lezione 19: grammatiche e linguaggi regolari

Lucidi della lezione 18: automi a pila e macchine di Turing; alberi sintattici e ambiguità

Lucidi della lezione 17: grammatiche context-free e automi a pila

Lucidi della lezione 16: decidibilità dei linguaggi di tipo 1 e introduzione alle grammatiche di tipo 2

Lucidi della lezione 15: macchina di Turing che accetta il linguaggio generato da una grammatica

Lucidi della lezione 14: grammatica che genera un linguaggio accettabile

Lucidi della lezione 13: la gerarchia di Chomsky

Lucidi della lezione 11: modelli generativi e grammatiche formali

Lucidi della lezione 11: simulazione di macchine di Turing mediante programmi in PascalMinimo

Lezione 10: modelli di calcolo e la Tesi di Church-Turing, dal PascalMinimo alla Macchina di Turing

Lucidi della lezione 9: indecidibilità dell'Halting problem, riduzioni many-to-one

Lucidi della lezione 8: esistenza di linguaggi indecidibili, Halting problem e sua accettabilità

Dispensa 5: linguaggi indecidibili e Halting Problem

Dispensa 4 (non in programma): cardinalità di insiemi e il metodo di diagonalizzazione di Cantor

Esercizi: accettabilità/decidibilità di linguaggi, calcolabilità di funzioni

Dispensa 3: accettabilità, decidibilità, calcolabilità e la Tesi di Church-Turing

Lucidi della lezione 7: linguaggi e funzioni; accettabilità, decidibilità, calcolabilità

Lucidi della lezione 6: la macchina di Turing Universale

Lucidi della lezione 3: progetto di macchine di Turing e tecnica di simulazione

Esercizi: macchine di Turing

Lucidi della lezione 5: struttura dell'insieme delle quintuple e non determinismo

Lucidi della lezione 4: modelli di macchine di Turing e loro equivalenza

Lucidi dellanlezione 2: macchine di Turing

Lucidi della lezione 1: introduzione alla calcolabilità

Dispensa 2: macchina di Turing

Dispensa 1: introduzione alla calcolabilità

Parte 1, calcolabilità:

- Ancora sulle Macchine di Turing: trasduttori e riconoscitori, Macchine ad un nastro e a k nastri, Macchine  deterministiche e non deterministiche. Macchina di Turing universale. 
- Linguaggi e funzioni. Linguaggi e linguaggi complemento. Accettabilità e decidibilità di linguaggi. Calcolabilità di funzioni. La tesi di Church-Turing e modello di calcolo equivalenti alla macchina di Turing.

- Linguaggi non decidibili. L'Halting Problem.

- Riducibilità tra linguaggi

- Grammatiche formali. Gerarchia di Chomsky. Grammatiche e calcolabilità. Linguaggi di tipo 2 e automi a pila. Linguaggi di tipo e e automi a stati finiti.

Parte 2, complessità:

- Misure di complessità: DTIME, DSPACE, NTIME, NSPACE. 
- Classi di linguaggi. Gap theorem e funzioni time-constructible. Teoremi di compressione e di accelerazione. Definizione delle classi di complessità spaziale e temporale: P, NP, PSPACE, NPSPACE, EXP, coNP, FP. Inclusione, inclusione propria, coincidenza. Riducibilità polinomiale. Chiusura. Completezza.

- Problemi e codifiche. Problemi decisionali e loro complemento. 
- La classe NP. Linguaggi NP-completi e Teorema di Cook. Chiusura rispetto alla riduzione polinomiale. Esempi di dimostrazioni di NP-completezza: 3-SAT, Vertex Cover, 3-Colorability, Colorability, Independent Set, Clique, Hamiltonian Circuit/Path, Longest Path, Commesso Viaggiatore. Problemi NP-intermedi: il teorema di Ladner.

Dispense a cura del docente e lucidi delle lezioni disponibili in questa pagina (materiale sufficiente ai fini della preparazione all'esame).

Per consultazione, gli studenti possono far riferimento a: G. Ausiello, F. D'Amore, G. Gambosi, L. Laura "Linguaggi, Modelli, Complessità" nuova edizione. Franco Angeli, 2014. ISBN 978-88-917-0553-2.

Per gli studenti interessati a un'introduzione informale e divulgativa agli argomenti del corso (nonché as un approfondimento degli stessi): M. Di Ianni "Il sentiero dei problemi impossibili". Franco Angeli, 2020. ISBN: 978-88-351-0611-1.

Da richiedere a mezzo posta elettronica. Su richiesta dello studente, è possibile fissare anche ricevimenti on-line.

Per partecipare all'esame è neccesario prenotarsi su Delphi (appelli del corso di Fondamenti di Informatica): non saranno ammessi alle prove gli studenti che non si siano prenotati.

Gli esami consistono di una prova scritta eventualmente seguita da una prova orale, secondo le modalità di seguito descritte:

• gli studenti che ottengono nella prova scritta una valutazione inferiore a 15 non possono sostenere l'orale, e non superano l'esame
• gli studenti che ottengono nella prova scritta una valutazione compresa fra 15 e 17 devono sostenere la prova orale per superare l'esame
• gli studenti che ottengono nella prova scritta una valutazione compresa fra 18 e 24 possono decidere se verbalizzare il voto della prova scritta (mediato con il voto del modulo 1) senza sostenere l'orale oppure sostenere la prova orale
• gli studenti che ottengono alla prova scritta una valutazione maggiore di 24 possono decidere se sostenere o meno la prova orale: se decidono di non sostenere la prova orale verbalizzeranno 24 (mediato con il voto del modulo 1) indipendentemente dal voto ottenuto nella prova scritta