Fondamenti di informatica

Modulo 2. Si avvisano gli studenti che, per ogni appello, non verranno concessi ricevimenti a meno di cinque giorni dalla data dell'appello.

Lezioni settimana 07-11/03/2022

la lezione di giovedì 10 marzo avrà luogo in modalità telematica sulla piattaforma TEAMS (link alla classe: https://teams.microsoft.com/l/team/19%3aVjgTPIDiXM7pjLIwkKZRHhAwTvx3Ek-xZsKRfzw32QY1%40thread.tacv2/conversations?groupId=508a3185-600f-4edf-8c58-73b503d44951&tenantId=24c5be2a-d764-40c5-9975-82d08ae47d0e) con inizio alle ore 9:00. Per agevolare gli eventuali spostamenti, la lezione del corso di Sistemi Operativi e Reti di giovedì 11 marzo avrà inizio alle ore 11:30

Sito modulo 2

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

Classe Teams modulo 2

La classe Teams relativa la secondo modulo del corso è accessibile a https://teams.microsoft.com/l/team/19%3aVjgTPIDiXM7pjLIwkKZRHhAwTvx3Ek-xZsKRfzw32QY1%40thread.tacv2/conversations?groupId=508a3185-600f-4edf-8c58-73b503d44951&tenantId=24c5be2a-d764-40c5-9975-82d08ae47d0e

Classe Teams modulo 1

La classe Teams relativa la primo modulo del corso è accessibile a https://teams.microsoft.com/l/team/19%3afnpjj8Gpf9_eVm-UpC5GkDIXqIIa46FfG3vUh9LI9fE1%40thread.tacv2/conversations?groupId=d4c5d008-9873-4b48-bbb9-9b3481d37e8e&tenantId=24c5be2a-d764-40c5-9975-82d08ae47d0e

Sito modulo 1

Informazioni e comunicazioni sul primo modulo del corso disponibili a https://tvml.github.io/fo2122/ 

Modulo 2. Lezione aperta, dedicata al chiarimento di dubbi degli studenti

Modulo 2. Il ruolo delle costanti nella complessità dei problemi. Il problema Partizione e i problemi numerici: algoritmi pseudo-polinomiali e NP-completezza in senso debole. NP-completezza in senso forte e il problema TSP. Esercitazione

Modulo 2. Esercitazione sulle dimostrazioni di NP-completezza: dal problema Ciclo Hamiltoniano ai problemi Percorso Hamiltoniamo, Long Path e Commesso Viaggiatore; 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, 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. Correlazione polinomiale dei modelli di calcolo (solo enunciata).

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

Esercizi: la classe NP

Esercizi: la classe P

Dispensa 9: la classe NP

Dispensa 8: la classe P

Dispensa 7: linguaggi e problemi

Esercizi: linguaggi e complessità

Dispensa 6: linguaggi e complessità

Esercizi: accettabilità e decidibilità di linguaggi

Esercizi: macchine di Turing

Dispensa 5: l'Halting Problem

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

Lucidi delle lezioni: lezione 5 del 24/03/2022

Lucidi delle lezioni: lezione 5 del 22/03/2022

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

Lucidi delle lezioni: lezione 4 del 17/03/2022

Lucidi delle lezioni: lezione 3 del 15/03/2022

Dispensa 2: macchine di Turing

Lucidi delle lezioni: lezione 2 del 11/03/2022

Lucidi delle lezioni: Lezione 1

Dispensa 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. 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: il giovedì, al termine della lezione, 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.