Genèse d’un algorithme
D’où viennent ces algorithmes que les auteurs d’Interstices décortiquent et analysent avec tant de brio et de clarté ? Certes, ils sont le produit de l’intelligence humaine, chaque algorithme ayant été ingénieusement conçu pour résoudre une classe de problèmes plus ou moins étendue. Mais, comment, en pratique, conçoit-on un algorithme ?
Nous vous proposons de participer à la genèse d’un algorithme, de l’énoncé de la classe de problèmes qu’il est censé résoudre jusqu’à sa programmation et son test, en passant par sa formulation, puis sa formalisation.
1. Un problème simple
Nous considérons à cet effet un problème simple, dont l'intérêt scientifique ne saute sans doute pas aux yeux. Dans sa version la plus imagée, le problème consiste en effet à mettre dans l’ordre une pile de crêpes de différentes tailles. La crêpe de plus grand diamètre doit se retrouver en dessous de pile ; la plus petite au sommet ; entre les deux, toute crêpe doit reposer sur une crêpe plus large. Pour modifier l’arrangement de la pile de crêpes, vous êtes armé d’une spatule appropriée et contraint à un seul type d'action : insérer la spatule entre deux crêpes et retourner l'ensemble des crêpes du dessus.
Pour bien comprendre le problème posé, la première étape consiste, assez naturellement, à « jouer avec » et à chercher, en tâtonnant, des solutions dans les cas simples. Vous pouvez donc débuter votre apprentissage dans votre cuisine en confectionnant, par exemple, une pile de quatre ou cinq crêpes de tailles différentes. Vous testerez simultanément vos capacités physiques et intellectuelles en cherchant à les empiler par taille décroissante. Pour cela, vous devrez effectuer autant de fois que nécessaire l’opération qui consiste à placer la spatule sous une certaine crêpe judicieusement choisie et à retourner, en une seule action, l’ensemble des crêpes situées au-dessus de la spatule. Il est à parier que l’état de votre cuisine vous conduise très rapidement à reconnaître la nécessité d’abstraire le problème posé.
Il apparaît clairement que vous ne dénaturez pas le problème à résoudre en remplaçant les crêpes par des disques de carton, ou mieux encore des disques en bois, matière noble et nettement moins grasse que nos crêpes du début. Faut-il préciser que vous pouvez renoncer à l’usage de la spatule, si vous acceptez la règle qui consiste à ne retourner, en un seul mouvement, qu’un groupe de disques accessibles en sommet de pile ? Vous pouvez aussi, avantageusement et sans complexe, emprunter un des jeux dit d’éveil du petit dernier ou de la petite dernière de la famille.
Alternativement, vous pouvez monter d’un niveau dans l’abstraction du problème posé en vous essayant à le résoudre dans les différentes configurations que vous propose l’applet suivante. Comme le reste du monde, nos crêpes sont en passe de devenir numériques !
| Applet réalisée par Régis Monte. Si l'applet ne s'affiche pas correctement, vérifiez votre configuration technique |
Alors, avez-vous réussi à identifier de façon systématique, à chaque étape, la crêpe en dessous de laquelle il vous faut placer votre spatule (virtuelle), de façon à arriver, en un nombre fini (s’il vous plaît…) d’actions, à remettre la pile dans l’ordre ?
Si oui, nous vous invitons à poursuivre votre lecture. Si non, continuez votre quête, honorable lecteur, et que l’inspiration soit avec vous.
Français