Fondamenti di informatica

Lezioni 28 e 29 maggio

Si avvisano gli studenti che le lezioni del 28 e 29 maggio subiranno le seguenti variazioni:

- MARTEDI’ 28 MAGGIO dalle 11 alle 13 in aula L5 a Sogene;

- MERCOLEDI’ 29 MAGGIO dalle 9 alle 11 in aula G2b

Lezioni ed esercitazioni dal 24/04 al 03/05

Si avvisano gli studenti che le lezioni e le esercitazioni dal 24 aprile al 3 maggio subiranno le seguenti variazioni:

- la lezione del 24 aprile si terrà alle ore 9 in aula G2b

- la lezione del 30 aprile non si terrà

- il 3 maggio alle 9 in aula T7 si terrà la lezione con la docente (in recupero della lezione del 30 aprile)

Lezione del 3 aprile e esercitazione del 5 aprile

Si avvisano gli studenti che la lezione del 3 aprile e l'esercitazione del 5 aprile saranno scambiate, ossia:

- il 3 aprile alle 11 in aula 3PP2 si terrà un'esercitazione con il tutor

- il 5 aprile alle 9 in aula T7 si terrà la lezione con la docente

Informazioni e comunicazioni relative al modulo 2

Tutte le informazioni relative al modulo 2 del corso e tutto il materiale didattico necessario saranno resi disponibili in questa pagina.

Sito del corso e classe Teams

Informazioni e comunicazioni sul primo modulo del corso disponibili all'indirizzo https://tvml.github.io/fo2324/, oltre che nella classe Teams relativa, accessibile a questo indirizzo.

Modulo 2. Esercitazione sulle dimostrazioni di NP-completezza. Il ruolo delle costanti nella complessità dei problemi. Esercizi vari.

Modulo 2. 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à.

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

Modulo 2. 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

Modulo 2. Il teorema di Cook-Levin

Modulo 2. Caratterizzazione alternativa della classe NP.

Modulo 2. 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

Modulo 2. 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

Modulo 2. 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.

Modulo 2. 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.

Modulo 2. 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.

Modulo 2. 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 (con dimostrazione). PSPACE = NPSPACE (solo enunciato).

Modulo 2. Classi di complessità: DTIME[f(n)], DSPACE[f(n)], NTIME[f(n)], NSPACE[f(n)] e loro complementi. Relazioni fra classi deterministiche e relazioni fra classi non determistiche. Inclusione delle classi deterministiche nelle corrispondenti classi non deterministiche. Ruolo della funzione limite e Gap Theorem (solo enunciato). Funzioni time-constructible e space-constructible. Teoremi di gerarchia (solo enunciati).

Modulo 2. Classi di complessità: DTIME[f(n)], DSPACE[f(n)], NTIME[f(n)], NSPACE[f(n)] e loro complementi. Relazioni fra classi deterministiche e relazioni fra classi non determistiche. Inclusione delle classi deterministiche nelle corrispondenti classi non deterministiche. Ruolo della funzione limite e Gap Theorem (solo enunciato). Correlazione polinomiale fra modelli di calcolo (solo definizione)

Modulo 2. 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. Introduzione alla teoria della Complessità Computazionale

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

Modulo 2. Simulazione della macchina di Turing universale mediante un programma in PascalMinimo. Simulazione di macchine non deterministiche mediante programmi.

Modulo 2. Completamento delle relazioni fra accettabilità/decidibilità di linguaggi e calcolabilità di funzioni. Modelli di calcolo e la tesi di Church-Turing. Il linguaggio PascalMinimo e sua simulazione mediante Macchina di Turing.

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

Modulo 2. La macchina di Turing Universale

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

Modulo 2. 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.

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

Modulo 2. 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.

Modulo 2, lucidi della lezione 24: relazioni fra costanti e complessità nei problemi in NP; esercitazione

Modulo 2, lucidi della lezione 23: problemi di cammini e di colorabilità

Modulo 2, lezione 22: prove di NP-completezza (VC, IS, CLIQUE, DS)

Modulo 2, lucidi della lezione 21: NP-completezza e struttura della classe NP

Modulo 2, lucidi della lezione 20: il teorema di Cook-Levin

Modulo 2, lucidi della lezione 19: caratterizzazione alternative di NP

Modulo 2, lucidi della lezione 18: introduzione alla classe NP

Modulo 2. Esercizi: la classe P

Modulo 2. Esercizi: la classe NP

Modulo 2, Dispensa 8: la classe NP

Modulo 2, Dispensa 8: la classe P

Modulo 2, lucidi della lezione 17: dalla complessità dei linguaggi alla complessità dei problemi

Modulo 2. Dispensa 7: linguaggi e problemi

Modulo 2, lucidi della lezione 16: linguaggi e problemi, codifiche ragionevoli e irragionevoli

Modulo 2, lucidi della lezione 15: classi complemento

Modulo 2, lucidi della lezione 14: riducibilità polinomiale

Modulo 2, lucidi della lezione 13: funzioni time- e space-constructible e le classi P, NP, EXPTIME, DSPACE

Modulo 2. Esercizi: linguaggi e complessità

Modulo 2, lucidi della lezione 12: classi di complessità

Modulo 2. Dispensa 6: Linguaggi e complessità

Modulo 2, lucidi della lezione 11: misure di complessità

Modulo 2, lucidi della lezione 10: riduzioni fra linguaggi e introduzione alla teoria della Complessità Computazionale

Modulo 2. Esercizi: accettabilità e decidibilità di linguaggi

Modulo 2. Esercizi: macchine di Turing

Modulo 2. Dispensa 5: l'Halting Problem

Modulo 2. Dispensa 4: cardinalità di insiemi (non in programma)

Modulo 2, lucidi della lezione 9: esistenza di linguaggi nin accettabili e l'Halting problem

Modulo 2, lucidi delle lezioni 7 e 8: modelli di calcolo e la Tesi di Church-Turing

Modulo 2, Dispensa 3 la tesi di Church-Turing

Modulo 2, lucidi della lezione 6: decidibilità e accettabilità di linguaggi, calcolabilità di funzioni

Modulo 2, lucidi della lezione 5: la macchina di Turing Universale

Modulo 2, lucidi della lezione 4: struttura di P e macchine non deterministiche

Modulo 2, lucidi della lezione 3: modelli di macchine di Turing

Modulo 2, Dispensa 2: macchine di Turing

Modulo 2, Dispensa 1: introduzione al corso

Modulo 2, lucidi della lezione 2: macchine di Turing

Modulo 2, lucidi della lezione 1: introduzione alla calcolabilità

MODULO 2

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

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.

MODULO 2

Dispense a cura del docente, disponibili in questa pagina e lucidi delle lezioni disponibili sulla piattaforma TEAMS (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: al termine delle lezioni, o telematicamente in giorni e orari da concordare

MODULO 2.

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.

Poiché l'esame è suddiviso in due moduli (Modulo 1 tenuto dal Prof. Gambosi, e Modulo 2 tenuto da me), chiedo cortesemente agli studenti di comunicarmi (o tramite Delphi o inviandomi un messaggio di posta elettronica) che intendono sostenere il mio modulo.

Gli esami relativi al modulo 2 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