11933 - Theoretical Computer Science

Course contents

• Problems and algorithms
• Computability vs Complexity
• Turing machines
• Recursive and recursively enumerable problems
• Complexity classes
• The classes P and NP
• NP-complete problems, and the P vs. NP question
• A quick look at space complexity classes
• A quick look at oracle classes, class hierarchies, and functional classes

Prerequisites:

Students are assumed to have a solid background in algorithmic reasoning, and are somewhat familiar with basic data structures such as lists, trees, and graphs. Previous knowledge of the notion of finite state automaton is helpful but not necessary.

Readings/Bibliography

Textbook:

• Hopcroft, Motwani, Ullman. Introduction to Automata Theory, Languages, and Computation. 3rd ed. Pearson Education, 2013
  

Additional readings:

• Sipser. Introduction to the Theory of Computation. 3rd ed. Cengage Learning, 2012
  
• Arora, Barak. Computational Complexity: A Modern Approach, Cambridge University Press, 2009

Teaching methods

Class lectures; Guided exercises.

Assessment methods

The exam consists in a written test, and and a possible oral examination. These activities aim at assessing that the student has acquired the necessary knowledge of the course topics and the skills in formal argumentation.

 

Students with learning disorders and\or temporary or permanent disabilities: please, contact the office responsible (https://site.unibo.it/studenti-con-disabilita-e-dsa/en/for-students) as soon as possible so that they can propose acceptable adjustments. The request for adaptation must be submitted in advance (15 days before the exam date) to the lecturer, who will assess the appropriateness of the adjustments, taking into account the teaching objectives.

Office hours

See the website of Enrico Malizia