L'insegnamento di Teoria della Computazione ha l'obiettivo fondamentale di far acquisire allo studente gli strumenti teorici che permettono di comprendere la complessità computazionale dei problemi, come sono classificati in base alla loro complessità e quali sono le metodologie per risolverli, in modo esatto o con performance di approssimazione dimostrabili. Introduce anche metodologie algoritimiche e strutture dati avanzate per affrontare problemi fondamentali su testi di grandi dimensione.

Più in dettaglio gli obiettivi sono:

• Comprendere concetti fondamentali del principale modello di calcolo (Macchina di Turing) e delle sue varianti.
• Comprendere quali problemi possono essere risolti da un computer (decidibilità) e quali non possono essere risolti in un tempo ragionevole (intrattabilità).
• Imparare come un problema può essere ridotto ad un altro per dimostrare la complessità relativa dei problemi.
• Imparare a classificare i problemi in base alla loro complessità computazionale (ad esempio, P, NP, NP-completi).
• Comprendere gli algoritmi di approssimazione, cioè algoritmi che ottengono in tempi ragionevoli una soluzione dimostrabilmente vicina all'ottimo per problemi intrattabili in modo esatto.
• Comprendere gli algoritmi parametrici, cioè algoritmi che permettono di affrontare in modo esatto alcuni problemi intrattabili limitando la crescita esponenziale dei tempi di calcolo dei loro algoritmi risolutivi a un parametro dell'istanza che risulta essere di valore limitato in casi pratici.

L'insegnamento ha anche lo scopo di introdurre lo studente alle basi teoriche e alle applicazioni pratiche di:

• ricerca esatta e approssimata di stringhe
• strutture dati per l'indicizzazione di stringhe