Fondamenti di informatica

Modulo 2, link alla classe TEAMS:

https://teams.microsoft.com/l/team/19%3a0b3414d9c7d8412b85094df2aba3bea5%40thread.tacv2/conversations?groupId=8c5ebc48-995b-4621-86eb-6285394d1706&tenantId=24c5be2a-d764-40c5-9975-82d08ae47d0e

Sito modulo 1

Tutte le informazioni, le comunicazioni e i materiali relativi al modulo 1 del corso sono disponibili a questo indirizzo (si suggerisce di aprire il link in un nuovo pannello o una nuova finestra)

Modulo 2, link alla classe TEAMS:

https://teams.microsoft.com/l/team/19%3a0b3414d9c7d8412b85094df2aba3bea5%40thread.tacv2/conversations?groupId=8c5ebc48-995b-4621-86eb-6285394d1706&tenantId=24c5be2a-d764-40c5-9975-82d08ae47d0e

Modulo 2. Lezione aperta alle domande 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.

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.

Modulo 2. Esercizi: la classe NP

Modulo 2. Esercizi: la classe P

Modulo 2. Esercizi: 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 3: accettabilità, decidibilità, calcolabilità e la Tesi di Church-Turing

Modulo 2, dispensa 2:macchine di Turing e macchina di Turing Universale

Modulo 2, dispensa 9: la classe NP

Modulo 2, dispensa 8: la classe P

Modulo 2, dispensa 7: linguaggi e problemi

Modulo 2, dispensa 6: linguaggi e complessità

Modulo 2, dispensa 4: ordini di infinito

Modulo 2, dispensa 1: introduzione alla calcolabilità

Secondo modulo

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.

- Cardinalità di insiemi. Insiemi numerabili e non numerabili. Diagonalizzazione.
- Linguaggi non decidibili. 

- 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. 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: M. Di Ianni "Il sentiero dei problemi impossibili". Franco Angeli, 2020. ISBN: 978-88-351-0611-1.

Modulo 2: da richiedere a mezzo posta elettronica.

MODULO 2 - NEW (20/01/22): la modalità di esame per gli appelli della sessione invernale è la stessa degli appelli delle precedenti sessioni dell'anno accademico 2020/21: pre-test in modalità telematica e prova orale. Gli studenti devono, pertanto collegarsi alla classe TEAMS il giorno della prova scritta (pre-test) alle ore 10.

Si rammenta agli studenti che gli appelli sono esclusivi.

Prego gli studenti di comunicarmi a mezzo posta elettronica la modalità con la quale intendono sostenere la prova orale.

Per partecipare ad una seduta di esame del modulo 2 è necessario:

1) iscriversi alla classe Teamd dedicata agli appelli del modulo 2 al link

https://teams.microsoft.com/l/team/19%3aS10v2xQJok9KEEUyI5095KT_jvVzLe79Xk9rJF0tvNM1%40thread.tacv2/conversations?groupId=0883ce68-645d-4c7c-ad91-5d676d0394de&tenantId=24c5be2a-d764-40c5-9975-82d08ae47d0e

(si consiglia agli studenti di farlo appena letta la presente comunicazione)

2) iscriversi sul portale delphi all'esame di Fondamenti di Informatica

3) riempire il modulo relativo all'appello presente nella classe Teams Esami Fondamenti di Informatica - modulo 2.

La non osservanza di uno o più dei punti sopra indicati comporta la non ammissione alle prove dell'appello.

Modalità di esame.

Ciascun appello di esame consiste in un pre-test e di una prova orale.

Il pre-test, che consiste in un test a risposte multiple, è volto a verificare le conoscenze di base del candidato al fine di ammetterlo o meno a sostenere la prova orale. Esso non ha acluna influenza sul voto finale. Il pre-test viene erogato in modalità telematica: il giorno fissato per la prova scritta dell'appello, all'ora indicata (solitamente, le 10 del mattino) lo studente si collega alla classe Teams Esami Fondamenti di Informatica - modulo 2: viene svolto appello e verifica dei documenti da parte del docente e viene erogato il pre-test. Al termine del pre-test viene fissato il calendario delle prove orali.

Le prove orali possono essere svolte in presenza (in accordo alle normative vigenti alla data dell'appello) o in modalità telematica (sempre su Teams, alla classe Esami Fondamenti di Informatica - modulo 2) secondo le preferenze che lo studente avrà indicato nel modulo di cui al punto 3. Nessuna giustificazione è richiesta dal docente circa la preferenza di sostenere la prova orale in modalità telematica. Gli studenti che decidono di sostenere la prova orale in modalità telematica possono decidere se sostenerla: lo stesso giorno della prova scritta, oppure in uno dei giorni compresi fra la data della prova scritta e la data della prova orale (secondo le indicazioni del del docente), oppure al termine delle prove orali in presenza (sempre concordando la data con il docente).