Fondamenti dell'informatica 1

Scopo principale dell'insegnamento è quello di presentare la nozione di calcolabilità usando semplici linguaggi di programmazione. In particolare vogliamo illustrare e motivare la tesi di Church, lo studio dei problemi indecidibili, i risultati fondamentali della teoria della ricorsività. Una seconda parte è invece dedicata alla complessità computazionale e in particolare ai problemi NP-completi.

Comprensione dei principali concetti di calcolabilità e decidibilità. Capacità di riconoscere l'indecidibilità e la difficoltà dei problemi nei casi principali. Capacità di formalizzare modelli di calcolo.