Fondamenti di informatica

Docenti: Giorgio Gambosi, Miriam Di Ianni

Comunicazioni

04-07-2022 17:16

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

07-03-2022 12:43

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

17-02-2022 17:45

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

17-02-2022 17:43

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

01-10-2021 16:35

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

01-10-2021 16:34

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


Lezioni

2531-05-2022

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

2426-05-2022

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

2324-05-2022

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à

2219-05-2022

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

2117-05-2022

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

2012-05-2022

Modulo 2. Il teorema di Cook-Levin

1910-05-2022

Modulo 2. Caratterizzazione alternativa della classe NP.

1805-05-2022

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.

1703-05-2022

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

1628-04-2022

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.

1526-04-2022

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.

1421-04-2022

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.

1319-04-2022

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

1214-04-2022

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.

1112-04-2022

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

1007-04-2022

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

905-04-2022

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

831-03-2022

Modulo 2. L'Halting Problem: accettabilità e indecidibilità.

729-03-2022

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.

624-03-2022

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

522-03-2022

Modulo 2. La macchina di Turing universale.

417-03-2022

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.

315-03-2022

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.

211-03-2022

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.

110-03-2022

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 didattico

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à

Informazioni

Anno accademico2021-2022
Crediti12
SettoreINF/01
Anno2
Semestre1-2
PropedeuticitàMatematica discreta.

Programma

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.

 

 


Testi di riferimento

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.


Ricevimento studenti

Da richiedere a mezzo posta elettronica: il giovedì, al termine della lezione, o telematicamente in giorni e orari da concordare


Modalità di esame

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.