- Docente: Andrea Asperti
- Crediti formativi: 12
- 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 Magistrale in Scienze filosofiche (cod. 8773)
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
Il programma e' diviso in due moduli incentrati rispettivamente
sulla teoria della Calcolabilita' e sulla Teoria della
Complessita'.
Calcolabilita':
Linguaggi subricorsivi: ricorsione primitiva, sistema
T;incompletezza dei formalismi totali;
Macchine di Turing e altri formalismi equivalenti; la tesi
di Church.
Il problema della terminazione, altri problemi indecidibili;
il teorema di Rice.
Insiemi ricorsivi e ricorsivamente enumerabili; il teorema
di Rice-Shapiro.
Il teorema del punto fisso di Kleene.
Riducibilita'; insiemi produttivi, creativi, immuni,
semplici.
Calcolabilita' e (in)completezza.
Complessita':
Problemi computazionali;
Modelli di Computazione e misure di Complessita';
Classi e gerarchie di complessita'; classi notevoli;
riduzione
P vs NP e altri problemi aperti
Macchine ad oracolo e gerarchia polinomiale
Testi/Bibliografia
Note del docente.
Testi addizionali consigliati:
N.J.Cutland. Computability. Cambridge University Press.
S.Arora, B.Barak. Computational Complexity: a modern approach.
Cambridge University Press, 2009
Complessita': C. H. Papadimitriou. Computational Complexity.
Addison Wesley, 1994.
Metodi didattici
Lezioni frontali. Uso slides, ma lavoro anche spesso alla lavagna.
Modalità di verifica e valutazione dell'apprendimento
Esame scritto e orale.
Orario di ricevimento
Consulta il sito web di Andrea Asperti