The main question in this couse is : "What can we do with a computer? (and what cannot we do?)"

To address these questions, we will present a very simple model for a computer: the Turing Machine. We will also present less powerful models (finite automata & pushdown automata) which can only simulate simple automatism.

In a second time, we will turn our interest on ressources (time and memory) that are needed to solve a given task. We will define complexity classes, especially the classes P and NP. We will see that some tasks, although feasible, in theory, by a computer, may need a crippling amount of ressources in practice. Finally, we will show that, in some cases, using randomness can facilitate computation.