Informatica teorica

L'insegnamento introduce le basi della teoria della calcolabilità e della complessità, presentando i necessari strumenti teorici utili anche per affrontare in maniera rigorosa numerose altre problematiche in ambito informatico. Viene caratterizzato rigorosamente il concetto di problema risolubile per via algoritmica ed esplorata la classe dei problemi non risolubili. Vengono poi studiati i problemi in base alla richiesta di risorse computazionali impiegate per la soluzione automatica, definendo rigorosamente il concetto di efficienza algoritmica. In tale ambito, viene affrontata la famosa questione P = NP.

Lo studente acquisirà conoscenze specifiche di calcolabilità e complessità, fondamentali in qualunque percorso di ricerca informatica e, più in generale, nell'analisi rigorosa di problemi di varia natura e relative soluzioni algoritmiche. Sarà anzitutto in grado di formulare e modellare correttamente i problemi, quindi di analizzare formalmente da diversi punti di vista le relative soluzioni algoritmiche.