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.