Certaines énigmes célèbres dans la liste des énigmes classiques de l'informatique sont :
- Dîner de philosophes (Concurrence et impasses)
- Cinq philosophes sont assis autour d'une table circulaire. Devant chaque philosophe se trouve une grande assiette de riz. Les philosophes alternent leur temps entre manger et réfléchir. Il y a une baguette entre chaque philosophe, à leur droite et à leur gauche immédiates. Pour manger, un philosophe donné doit utiliser les deux baguettes. Comment faire en sorte que tous les philosophes puissent manger de manière fiable sans mourir de faim ?
- Comment résoudre le problème ? Il existe diverses solutions allant de l'auteur du problème lui-même, Edsger W. Dijkstra, à d'autres réponses arbitraires.
- Vendeur ambulant (P=NP)
- Un vendeur a un itinéraire de villes qui constituent sa tournée. Quel'est l'itinéraire de vente le plus efficace qui visite chaque ville exactement une fois, puis retourne à la ville d'origine ?
- Nous avons des heuristiques mais on ne sait toujours pas s'il peut être résolu avec un algorithme en temps polynomial.
- Huit reines (conception d'algorithme)
- Donné huit reines sur un échiquier standard 8 x 8, combien de positions uniques - à l'exclusion des rotations et des images miroir - ces huit reines peuvent-elles occuper sans s'attaquer les unes aux autres ?
- Solution : Le retour en arrière en est une, la branche et la liaison une autre.
- Deux généraux (protocoles de communication)
- Deux armées, chacune dirigée par un général, se préparent à attaquer une ville. Les armées sont campées à l'extérieur de la ville sur deux montagnes séparées par une grande vallée. Afin de capturer la ville, les généraux doivent attaquer exactement au même moment. Le seul moyen pour les généraux de communiquer est d'envoyer des messagers à travers la vallée. Malheureusement, la vallée est occupée par les défenseurs de la ville, donc il y a une chance que n'importe quel messager soit capturé. Chaque général n'a aucun moyen de savoir si son messager est arrivé. Comment les généraux coordonnent-ils leur attaque ?
-
- Tours de Hanoi (Récursion)
- Vous avez une pile de disques, du plus grand au plus petit, qui glissent sur la première cheville d'un plateau à trois chevilles. Votre objectif est de déplacer la totalité de la pile de disques du premier piquet au troisième piquet. Cependant, vous ne pouvez déplacer que le disque le plus haut de n'importe quelle cheville, et les plus petits disques doivent toujours être placés sur les plus grands. Combien de déplacements faudra-t-il faire ?
- Réponse : Pour [math]n[/math] disques, nous avons [math]2^n-1[/math] étapes/mouvements à résoudre, ce qui peut être fait en utilisant la récursion.
- Tours de Hanoi (Récursion)
Source : Puzzles informatiques classiques
Un très bon livre est The Science of Programming de David Gries dans lequel il discute de diverses idées derrière les puzzles de Dijkstra et d'autres idées classiques de puzzles. Par exemple ceci : Un puzzle combinatoire classique :
Un sac contient quelques boules noires et blanches. Le processus suivant doit être répété aussi longtemps que possible (en supposant que nous avons une réserve infinie de boules noires et blanches).
- Sélectionner aléatoirement deux boules dans le sac. Si elles sont de la même couleur, jetez-les, mais mettez une boule noire supplémentaire.
- Si elles sont de couleurs différentes, remettez la blanche dans le sac et jetez la noire.
Essayez de le résoudre, c'est beaucoup plus simple quand on le fait sur papier.