ComunicazioniProve esame modulo 2 giugno 202301-06-2023 20:43
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 222-02-2023 10:50
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 222-02-2023 10:39
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 127-09-2022 15:44
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
|
Lezioni24 | 06-06-2023
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. | 23 | 01-06-2023
Modulo 2. Esercitazione sulle dimostrazioni di NP-completezza: Dominating Set; dal problema Ciclo Hamiltoniano ai problemi Percorso Hamiltoniamo, Long Path e Commesso Viaggiatore. | 22 | 30-05-2023
Modulo 2. Esercitazione sulle dimostrazioni di NP-completezza: i problemi Vertex Cover, Independent Set, Clique. | 21 | 25-05-2023
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 | 20 | 23-05-2023
Modulo 2. Il teorema di Cook-Levin | 19 | 18-05-2023
Modulo 2. Caratterizzazione alternativa della classe NP. | 18 | 16-05-2023
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. | 17 | 11-05-2023
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 | 16 | 09-05-2023
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. | 15 | 04-05-2023
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. | 14 | 02-05-2023
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. | 13 | 27-04-2023
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). | 12 | 20-04-2023
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. | 11 | 18-04-2023
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). | 10 | 06-04-2023
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. | 9 | 04-04-2023
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 | 8 | 30-03-2023
Modulo 2. Esistenza di linguaggi non accettabili: il metodo della diagonalizzazione. L'Halting Problem: accettabilità e indecidibilità. | 7 | 28-03-2023
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. | 6 | 23-03-2023
Modulo 2. Linguaggi, linguaggi accettabili, linguaggi decidibili. Funzioni, funzioni totali, funzioni calcolabili. Relazione fra accettabilità/decidibilità di linguaggi e calcolabilità di funzioni. | 5 | 21-03-2023
Modulo 2. La macchina di Turing universale. | 4 | 16-03-2023
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. | 3 | 14-03-2023
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. | 2 | 09-03-2023
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. | 1 | 07-03-2023
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. |
Materiale didatticoModulo 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) | |
| InformazioniAnno accademico | 2022-2023 |
---|
Crediti | 12 |
---|
Settore | INF/01 |
---|
Anno | 2 |
---|
Semestre | 1-2 |
---|
Propedeuticità | Matematica discreta. |
---|
ProgrammaMODULO 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.
|
Testi di riferimentoMODULO 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.
|
Ricevimento studentiDa richiedere a mezzo posta elettronica: al termine delle lezioni, o telematicamente in giorni e orari da concordare |
Modalità di esameMODULO 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.
|
|