Automata, Computability and Complexity

This course introduces three areas of the theory of computation.

First, automata are used to recognize words in (formal) languages, and we will discern several types of languages along with the types of automata that can recognize them.

Second, once we have an intuition about languages, we discuss the topic of computability, where you will learn not only what kinds of problems a computer can solve but also how to prove this.

Third, we will examine the class of computable problems and make a distinction between "easy" and "hard" problems and delve into the famous problem: P = NP?

A written, closed-book exam. You are allowed to bring a hand-written double sided A4 cheat sheet. No additional materials are permitted, including but not limited to: books, printouts of the slides, or devices.

The final grade of the course is based on the final exam for 100%.

Disclaimer: information may change depending on unforeseen circumstances or measures (see: TER Art 29, sub 4).