Fondamenti di Informatica 1


Insegnamento per il corso di laurea Magistrale di Matematica (6 crediti)
Università degli Studi di Milano
Anno accademico 2017/2018

Docente: Massimiliano Goldwurm




1. Presentazione del corso
2. Programma
3. Testi di riferimento
4. Modalità d'esame
5. Appelli per l'a.a. 2016/2017
6. Orari di lezione e ricevimento


PRESENTAZIONE DEL CORSO

Il corso è dedicato a due argomenti principali: la calcolabilità e la complessità computazionale. Nella prima parte la nozione di calcolabilità viene introdotta usando semplici linguaggi di programmazione. In particolare vogliamo illustrare e motivare la tesi di Church, lo studio dei problemi indecidibili, e i risultati principali di teoria della ricorsività. La seconda parte è dedicata alle principali classi di complessità in tempo e spazio, in particolare ai problemi NP-completi.


PROGRAMMA