Fondamenti di informatica

Docenti: Giorgio Gambosi, Miriam Di Ianni

Comunicazioni

Informazioni e comunicazioni relative al modulo 2

27-02-2024 17:01

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


Sito del corso e classe Teams

29-09-2023 20:06

Informazioni e comunicazioni sul primo modulo del corso disponibili all'indirizzo https://tvml.github.io/fo2324/, oltre che nella classe Teams relativa, accessibile a questo indirizzo.


Lezioni


Materiale didattico

Informazioni

Anno accademico2023-2024
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, 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.

 


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: al termine delle lezioni, 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