Afficher la pageAnciennes révisionsLiens de retourAjouter au livre.Exporter en PDFHaut de page Cette page est en lecture seule. Vous pouvez afficher le texte source, mais ne pourrez pas le modifier. Contactez votre administrateur si vous pensez qu'il s'agit d'une erreur. 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. public/in_english.txt Dernière modification : 2019/03/19 14:24de pprea