Introduzione alla calcolabilità e alla complessità computazionale

La calcolabilità delle funzioni e la complessità computazionale dei problemi sono due argomenti classici di Informatica Teorica. In questo testo si presentano gli aspetti principali di queste tematiche con uno scopo didattico e divulgativo. La nozione di calcolabilità è legata all’esistenza di algoritmi in grado di calcolare una funzione o di risolvere un problema. In questo contesto sono di interesse anche le funzioni e i problemi che non ammettono algoritmi. La complessità computazionale invece riguarda l’analisi delle risorse (tipicamente tempo e spazio) richieste da un algoritmo per risolvere un dato problema o calcolare una certa funzione. Entrambe queste tematiche sono considerate di base per una laurea in Informatica o in Matematica e il presente testo si rivolge in particolare agli studenti dei corsi di laurea a carattere scientifico che possono ritrovare questi argomenti in diversi insegnamenti nel loro percorso di studi.