Fondamenti di informatica

Docenti: Giorgio Gambosi, Miriam Di Ianni

Comunicazioni

24-02-2021 18:07

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

24-02-2021 18:06

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


Lezioni

2501-06-2021

Modulo 2. Lezione aperta alle domande degli studenti

2428-05-2021

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

2326-05-2021

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à

2225-05-2021

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

2119-05-2021

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

2018-05-2021

Modulo 2. Il teorema di Cook-Levin

1912-05-2021

Modulo 2. Caratterizzazione alternativa della classe NP.

1811-05-2021

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.

1705-05-2021

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

1604-05-2021

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.

1530-04-2021

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.

1428-04-2021

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.

1321-04-2021

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

1220-04-2021

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.

1114-04-2021

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

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.

906-04-2021

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

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

730-03-2021

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

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

523-03-2021

Modulo 2. La macchina di Turing universale.

417-03-2021

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.

316-03-2021

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.

210-03-2021

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.

109-03-2021

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

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à

Informazioni

Anno accademico2020-2021
Crediti12
SettoreINF/01
Anno2
Semestre1-2
PropedeuticitàMatematica discreta.

Programma

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.

 


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


Ricevimento studenti

Modulo 2: da richiedere a mezzo posta elettronica.

 


Modalità di esame

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