public:informatique_theorique [WiKi informatique]

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.

=== Description ===

La question centrale à laquelle on tentera de répondre est : « Que peut-on faire avec un ordinateur ? (& que ne peut-on pas faire ?) »

Pour répondre à cette question, on présentera un modèle très simple d'ordinateur : la **machine de Turing**, ainsi que d'autres modèles moins puissants (les **automates finis** & les **automates à pile**), qui ne peuvent simuler que des automatismes "simples".
 
Dans un deuxième temps, on s'intéressera aux ressources (temps et espace (mémoire)) nécessaires pour résoudre une tâche donnée & on définira quelques **classes de complexité**, en particulier les classes **P** et **NP**. On verra alors que certaines tâches, bien que réalisables en théorie par un ordinateur, peuvent nécessiter des ressources rédhibitoires en pratique. On terminera en voyant que, dans certains cas, l'utilisation du "hasard" peut grandement faciliter les choses. 

[[public:In_English|In English]]



Le [[http://pascal.prea.perso.centrale-marseille.fr/visible/Option_InfoTh%E9o/InfoTheo.pdf|polycopié]]