Theoretical Computer Science

The course aims at introducing basics of computability and complexity theory, suitably presenting theoretical tools also useful to rigorously approach several other issues in computer science. The notion of algorithmically solvable problem is formally investigated, as well as the class of unsolvable problems. Next, the classification of problems into complexity classes is presented, depending on the amount of required computational resources for their automatic solution. The notion of efficiently solvable problem is formally settled.

The student will be able to apply approaches and formal methods presented along the course into the analysis of problems from several realms. She/he will be able first to correctly formulate and model the problem, then to formally analyze proposed algorithmic solutions, not only focusing on feasibility and efficiency, but also investigating any other issue relevant to the problem under consideration. Moreover, the student will acquire specific knowledge on computability and complexity, fundamental in any computer science research path.