Fondamenti di informatica

Prove esame modulo 2 giugno 2023

Le prove di esame per il modulo 2 del corso di Fondamenti di Informatica per il primo appello della sessione estiva si terranno, regolarmente, in accordo al calendario precedentemente fissato, ossia:

- prova scritta il 14 giugno alle ore 10 (aula T7)

- prova orale il 20 giugno alle ore 10 nel mio studio

Classe TEAMS modulo 2

La classe TEAMS relativa al modulo 2 è

https://teams.microsoft.com/l/team/19%3aVjgTPIDiXM7pjLIwkKZRHhAwTvx3Ek-xZsKRfzw32QY1%40thread.tacv2/conversations?groupId=508a3185-600f-4edf-8c58-73b503d44951&tenantId=24c5be2a-d764-40c5-9975-82d08ae47d0e

Sito Modulo 2

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

Informazioni e comunicazioni relative al modulo 1

Informazioni e comunicazioni sul primo modulo del corso disponibili nella classe Teams relativa, accessibile all'indirizzo  seguente: https://teams.microsoft.com/l/team/19%3anvds5Q6EEHxfeg8dHrO-iKJFBbfR8KtxmroNT3Z4bQI1%40thread.tacv2/conversations?groupId=f334b1da-4bfa-4ca9-a842-6b1da30758e1&tenantId=24c5be2a-d764-40c5-9975-82d08ae47d0e

Modulo 2. Esercitazione sulle dimostrazioni di NP-completezza. Dal problema 3-colorabilità ai problemi k-colorabilità (con k costante) e colorabilità. Il ruolo delle costanti nella complessità dei problemi. Esercizi vari.

Modulo 2. Esercitazione sulle dimostrazioni di NP-completezza: Dominating Set; dal problema Ciclo Hamiltoniano ai problemi Percorso Hamiltoniamo, Long Path e Commesso Viaggiatore.

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

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, LONG PATH.

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. 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. Funzioni time-constructible e space-constructible. Teoremi di gerarchia. 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.

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).

Modulo 2. Misure di complessità: assiomi di Blum, funzioni dtime, dspace, ntime e nspace. Relazioni fra spazio e tempo deterministici e fra spazio e tempo non deterministici. Decidibilità dei linguaggi accettati in tempo/spazio non deterministico.

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. Modelli di calcolo e la tesi di Church-Turing. Il linguaggio PascalMinimo e sua equivalenza con la Macchina di Turing. Un programma in PascalMinimo che simula la macchina di Turing Universale ed uno che simula una macchina non deterministica.

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. 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. Macchine di tipo trasduttore e riconoscitore.

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 23 (1/06/2023)

Modulo 2. Esercizi: la classe NP

Modulo 2. Esercizi: la classe P

Modulo 2. Lucidi della lezione 22 (30/05/2023)

Modulo 2. Lucidi della lezione 21 (25/05/2023)

Modulo 2. Lucidi della lezione 20 (23/05/2023)

Modulo 2. Lucidi della lezione 19 (18/05/2023)

Modulo 2.Dispensa 9: la classe NP

Modulo 2.Dispensa 8: la classe P

Modulo 2. Lucidi della lezione 18 (16(05/2023)

Modulo 2. Lucidi della lezione 17 (11/05/2023)

Modulo 2. Dispensa 7: linguaggi e problemi

Modulo 2. Lucidi della lezione 16 (09/05/2023)

Modulo 2. Lucidi della lezione 15 (04/05/2023)

Modulo 2. Lucidi della lezione 14 (02/05/2023)

Modulo 2. Esercizi: Linguaggi e complessità

Modulo 2. Lucidi della lezione 13 (27/04/2023)

Modulo 2. Lucidi della lezione 12 (20/04/2023)

Modulo 2. Lucidi della lezione 11 (18/04/2023)

Modulo 2. Lucidi della lezione 9 (04/04/2023)

Modulo 2. Lucidi della lezione 1 (07/03/2023)

Modulo 2. Lucidi della lezione 10 (06/04/2023)

Modulo 2. Dispensa 6: linguaggi e complessità

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 8 (30/03/2023)

Modulo 2. Lucidi della lezione 7 (28/03/2023)

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

Modulo 2. Lucidi della lezione 6 (26/03/2023)

Modulo 2. Lucidi della lezione 5 (21/03/2023)

Modulo 2. Lucidi della lezione 4 (16/03/2023)

Modulo 2. Lucidi della lezione 3 (14/03/2023)

Modulo 2. Dispensa 2: macchine di Turing

Modulo 2. Lucidi della lezione 2 (09/03/2023)

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. Inclusione, inclusione propria, coincidenza. Completezza.

- Problemi e codifiche. Problemi decisionali e loro complemento. 
- La classe P. (brevi cenni) Riducibilità polinomiale e chiusura di P rispetto alla riducibilità polinomiale. Problemi in P: 2-SAT, 2-COLORABILITA'. Funzioni in FP: trasformazione di una funzione booleana in forma congiuntiva normale. 
- 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.

- Algoritmi pseudo-polinomiali, problemi numerici e NP-completezza in senso forte; il problema PARTIZIONE.

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

Gli appelli della sessione autunnale e gli appelli della sessione invernale sono esclusivi: gli studenti che *consegnano*  la prova scritta del primo appello (di una delle due sessioni) e non superano l'esame non possono partecipare al secondo appello.