41169 - INFORMATICA TEORICA (6 CFU)

Conoscenze e abilità da conseguire

Il corso fornisce una introduzione alla teoria della calcolabilita' e alla teoria della complessita' computazionale.Al termine del corso lo studente avra' acquisito consapevolezza dei limiti teorici e pratici dei metodi effettivi di calcolo e sara' in grado di utilizzare ed applicare metodologie e tecniche proprie dei metodi formali nello studio della trattabilita' computazionale di problemi algoritmici di svariata natura.

Contenuti

• Problemi e algoritmi
• Calcolabilità vs. Complessità
• Macchine di Turing
• Problemi decidibili, semidecidibili, e indecidibili
• Classi di complessità
• Le classi P ed NP
• Problemi NP-completi, e la questione P vs. NP
• Cenni alle classi di complessità spaziali
• Cenni alle classi ad oracolo, alle gerarchie di classi, e alle classi funzionali

Prerequisiti:

Si assume che gli studenti abbiano acquisito solide basi di ragionamento algoritmico, la nozione di chiamata a subroutine, e abbiano una certa dimestichezza con strutture dati quali liste, alberi, grafi. Conoscenza pregressa della nozione di automa a stati finiti è utile ma non indispensabile.

Testi/Bibliografia

Testo consigliato:

• Hopcroft, Motwani, Ullman. Introduction to Automata Theory, Languages, and Computation. 3rd ed. Pearson Education, 2013 (è stata pubblicata anche un'edizione italiana)

Testi aggiuntivi:

• Sipser. Introduction to the Theory of Computation. 3rd ed. Cengage Learning, 2012 (è stata pubblicata anche un'edizione italiana)
• Arora, Barak. Computational Complexity: A Modern Approach. Cambridge University Press, 2009

Metodi didattici

Lezioni frontali, esercitazioni guidate in aula.

Modalità di verifica e valutazione dell'apprendimento

L'esame consiste in una prova scritta ed una eventuale prova orale.

In particolare, la prova scritta consiste in:
- Un esercizio di "progettazione" di una macchina di Turing per decidere un linguaggio dato
- 4/5 domande teoriche a risposta aperta sugli argomenti visti nel corso
- Un paio di dimostrazioni di risultati teorici visti a lezione
- Un esercizio in cui si chiede di dimostrare la decidibilità o indecidibilità di un linguaggio (non visto a lezione)
- Un esercizio in cui si chiede di dimostrare la complessità di un problema (non visto a lezione), generalmente NP-completo.

In base al voto ottenuto allo scritto, a parte la possibilità di rifiutare il voto e risostenere la prova scritta, per lo studente si aprono i seguenti scenari:

• da 15 a 17 (compresi): lo studente può sostenere l'orale per arrivare a 18 (ma non di più);
• da 18 a 26 (compresi): lo studente può registrare il voto (senza sostenere l'orale);
• da 27 a 28 (compresi): lo studente può registrare il voto (senza sostenere l'orale), oppure sostenere l'orale;
• da 29 a salire: lo studente può registrare 28 (non il voto dello scritto), oppure sostenere l'orale.

Il voto all'orale può salire o scendere (o rimanere invariato) rispetto al voto dello scritto. Una volta che lo studente opta per sostenere la prova orale e questa ha inizio, il voto dello scritto è perso e l'esito dell'orale è quello che sarà preso in considerazione (non c'è la possibilità di "preferire e tenersi" il voto dello scritto).

Sia la prova scritta che l'eventuale prova orale, mirano a verificare che lo studente abbia acquisito la necessaria dimestichezza oltre che con gli argomenti del corso, anche con l'argomentazione formale. In particolare queste sono le fasce di voto con le relative capacità che lo studente deve mostrare per collocarvisi:

• 18 - 21: *buona* conoscenza delle definizioni di base (minimo per passare l'esame (con un voto minimale)), e capacità di manipolore semplici concetti;
  ad esempio: nozione di algoritmo, problema, linguaggio, macchina di Turing (nelle sue varianti), le classi P / NP, NP-hard, esempi di problemi indecidibili, esempi di problemi NP-completi
• 22 - 26: *buona* e precisa conoscenza di definizioni più sofisticate / capacità di *dimostrare formalmente* semplici risultati / capacità di collegare semplici concetti
  ad esempio: cos'è una riduzione, a cosa serve, esempi di riduzione, dimostrare l'indecidibilità di alcuni linguaggi, dimostrare l'NP-completezza di alcuni linguaggi, teorema di Rice
• 27+: capacità di *dimostrare formalmente* risultati più sofisticati / capacità di collegare concetti più sofisticati
  ad esempio: dimostrazione che Hamiltonian-cycle è NP-completo, dimostrare il teorema di Cook, dimostrazione di indecidibilità sofisticate; per la lode, lo studente, oltre a mostrare *piena* padronanza degli argomenti svolti a lezione, deve mostrare di essere in grado di collegare argomenti in modo creativo e rispondere a domande su cose non spiegate in aula

Il collocamento del voto specifico all'interno della fascia dipende dall'esposizione e quindi: quanto lo studente si è impadronito dei concetti? Li riesce a maneggiare? Quanto precise e formali sono le definizioni che da? Le dimostrazioni sono formali a sufficienza? C'è un flusso logico nell'esposizione? I nessi causali sono espliciti? Il legame fra concetti è chiaro?

 

Studenti/sse con DSA o disabilità temporanee o permanenti: si raccomanda di contattare per tempo l’ufficio di Ateneo responsabile (https://site.unibo.it/studenti-con-disabilita-e-dsa/it): sarà sua cura proporre agli/lle studenti/sse interessati/e eventuali adattamenti, che dovranno comunque essere sottoposti, con un anticipo di 15 giorni, all’approvazione del/della docente, che ne valuterà l'opportunità anche in relazione agli obiettivi formativi dell'insegnamento.

Strumenti a supporto della didattica

Verranno forniti i pdf di quello che verrà scritto in aula sulla "lavagna virtuale".

Orario di ricevimento

Consulta il sito web di Enrico Malizia