- Docente: Enrico Malizia
- Crediti formativi: 6
- SSD: ING-INF/05
- Lingua di insegnamento: Italiano
- Modalità didattica: Convenzionale - Lezioni in presenza
- Campus: Bologna
-
Corso:
Laurea in
Matematica (cod. 8010)
Valido anche per Laurea in Informatica (cod. 8009)
Conoscenze e abilità da conseguire
Al termine del corso, lo studente conosce i principi della calcolabilità e le teorie alla base dell'informatica. È in grado di verificare l'esistenza o l'inesistenza di programmi che calcolano una determinata funzione.
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
SDGs
L'insegnamento contribuisce al perseguimento degli Obiettivi di Sviluppo Sostenibile dell'Agenda 2030 dell'ONU.