- Docente titolare: Libor Vesely
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.
- Docente titolare: Massimiliano Goldwurm
- Docente titolare: Chiara Camere
- Docente titolare: Lambertus Van Geemen