Fondamenti di informatica

Esame per 12 CFU

Per gli studenti che devono sostenere l'esame da 12 cfu. Per ciascuno degli appelli, e con le medesime date, verranno aperte su Delphi anche le prenotazioni corrispondenti al corso da 12 cfu. Prenotarsi è necessario per accedere alle prove d'esame. Gli studenti che devono sostenere la prova relativa al modulo 2 si presenteranno alla prova scritta possibilmente indicando che devono sostenere le prove per il modulo 2 (durante la quale risponderanno alle domande corrispondenti al programma del modulo 2). Gli studenti che devono sostenere la prova relativa al modulo 1 dovranno contattare a mezzo posta elettronica il Prof. Gambosi.

Lezione di 3 ore.

La macchina di Turing Universale.

Esercitazione: progetto di un riconoscitore che decida se il suo input è una parola nella forma xx (Lucidi della lezione 3, dal lucido 38 al termine)

Struttura dell'insieme delle quintuple. Insieme non totale. Macchine deterministiche e non deterministiche. Interpretazione del non determinismo. Equivalenza dei modelli deterministico e non deterministico.

Macchine di tipo trasduttore e riconoscitore. 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.

Lezione di 3 ore.

Esempi di macchine di Turing e introduzione al concetto di simulazione (Lucidi della lezione 3, fino al lucido 38)

Definizione formale di macchina di Turing. Esempi di macchine di Turing. Alfabeti e parole. Stati globali, transizioni, computazioni (deterministiche) di macchine di Turing.

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: macchine di Turing

Lucidi della lezione 6: la macchina di Turing Universale

Lucidi della lezione 5: struttura dell'insieme delle quintuple e non determinismo

Lucidi della lezione 4: modelli di macchine di Turing e loro equivalenza

Lucidi della lezione 3: progetto di macchine di Turing e tecnica di simulazione

Lucidi della lezione 2: macchine di Turing

Dispensa 2: la Macchina di Turing

Lucidi della lezione 1: introduzione alla calcolabilità

Dispensa 1: introduzione alla calcolabilità

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

- Grammatiche formali. Gerarchia di Chomsky. Grammatiche e calcolabilità. Linguaggi di tipo 2 e automi a pila. Linguaggi di tipo e e automi a stati finiti.

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, FP. Inclusione, inclusione propria, coincidenza. Riducibilità polinomiale. Chiusura. Completezza.

- Problemi e codifiche. Problemi decisionali e loro complemento. 
- 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.

Dispense a cura del docente e lucidi delle lezioni disponibili in questa pagina (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. Su richiesta dello studente, è possibile fissare anche ricevimenti on-line.

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.

Gli esami 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  indipendentemente dal voto ottenuto nella prova scritta