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.
Le polycopié