Informatica teorica

L'insegnamento si propone di introdurre le basi della teoria della calcolabilità e della complessità, presentando opportunamente i necessari strumenti teorici utili anche per affrontare in maniera rigorosa numerose altre problematiche in ambito informatico. Viene affrontato rigorosamente il concetto di problema risolubile per via algoritmica ed esplorata la classe dei problemi non risolubili. Vengono poi presentate la classificazione e la suddivisione dei problemi in classi di complessità, definite in termini di limiti alla quantità di risorse computazionali a disposizione per la loro soluzione automatica.

Lo studente sarà in grado di applicare gli approcci e gli strumenti formali presentati nell'insegnamento all'analisi di problemi di varia natura. Sarà anzitutto in grado di formulare e modellare correttamente il problema, quindi di analizzare formalmente soluzioni algoritmiche proposte non solo in riferimento a problematiche di efficiente calcolabilità ma considerando e valutando qualunque altro aspetto rilevante al problema in oggetto. Lo studente inoltre acquisirà conoscenze specifiche di calcolabilità e complessità fondamentali in qualunque percorso di ricerca informatica.