- Docente: Fabio Zanasi
- Crediti formativi: 6
- SSD: INF/01
- Lingua di insegnamento: Italiano
- Modalità didattica: Convenzionale - Lezioni in presenza
- Campus: Bologna
-
Corso:
Laurea in
Informatica (cod. 8009)
Valido anche per Laurea in Matematica (cod. 8010)
-
dal 21/02/2023 al 26/04/2023
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
- macchine di Turing e modelli computazionali equivalenti; tesi di Church-Turing
- problema della fermata e altri problemi indecidibili; teorema di Rice
- classi di complessità e riduzioni; P vs NP e altri problemi aperti
Testi/Bibliografia
Testi consigliati:
- Introduction To The Theory Of Computation - Michael Sipser
- N.J.Cutland. Computability. Cambridge University Press.
Metodi didattici
Lezioni frontali ed esercitazioni.
Modalità di verifica e valutazione dell'apprendimento
Esame scritto.
Strumenti a supporto della didattica
Slides
Orario di ricevimento
Consulta il sito web di Fabio Zanasi