Fondamenti di Informatica 1


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

Docente: Massimiliano Goldwurm




1. Presentazione del corso
2. Programma
3. Dispense e testi di riferimento
4. Modalità d'esame
5. Appelli per l'a.a. 2018/2019
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 si illustra e si giustifica la tesi di Church, si presentano i problemi indecidibili fondamentali e i risultati principali di teoria della ricorsività. La seconda parte è dedicata alla complessità computazionale dei problemi decidibili, ovvero all'analisi della quantità di risorse (tempo di calcolo e spazio di memoria) richiesta dai corrispondenti algoritmi. In particolare vengono studiate le principali classi di complessità in tempo e spazio e le proprietà dei problemi NP-completi.


PROGRAMMA


DISPENSE E TESTI DI RIFERIMENTO



MODALITÀ D'ESAME

L'esame consiste in una prova orale sugli argomenti del programma.
Si ricorda che per sostenere l'esame è indispensabile iscriversi all'appello prescelto.

APPELLI D'ESAME PER L'A.A. 2018/2019


Le date, i termini di iscrizione e il luogo di svolgimento delle prove orali degli appelli sono reperibili al sito ccdmat alla voce "Appelli dell'anno".

LEZIONI

Il corso si svolge nel primo semestre, a partire da martedì 2 Ottobre 2018.

ORARIO DI RICEVIMENTO

Prof. Massimiliano Goldwurm, presso il Dip. di Matematica, via Saldini 50 (secondo piano, ufficio 2069), martedì ore 14:30-17:30, oppure su appuntamento (accordi per e-mail).