Calcolabilità e complessità computazionale

Un primo obiettivo dell'insegnamento è quello di introdurre la nozione di calcolabilità usando semplici linguaggi di programmazione. Ricordiamo che una funzione si dice calcolabile (e un problema decidibile) se esiste un algoritmo che la calcola (lo risolve). In particolare vogliamo illustrare e motivare la tesi di Church, lo studio dei problemi indecidibili, i risultati fondamentali della teoria della ricorsività. Un secondo obiettivo riguarda invece la classificazione dei problemi decidibili in base alla loro complessità computazionale, ovvero la quantità di tempo di calcolo e/o spazio di memoria necessari per risolverli. In particolare si intende presentare e motivare lo studio dei 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 studiare e formalizzare modelli di calcolo.