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. Queste attività mirano a verificare che lo studente abbia acquisito la necessaria dimestichezza oltre che con gli argomenti del corso, anche con l'argomentazione formale.

 

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.

Orario di ricevimento

Consulta il sito web di Enrico Malizia