Cours d'algorithmique : introduction

Préambule

L’algorithmique est un terme d’origine arabe, comme algèbre, amiral ou zénith. Ainsi, l’algo n’est pas " rythmique ", à la différence du bon rock’n roll. L’algo n’est pas non plus " l’agglo ". Alors, ne confondez pas l’algorithmique avec l’agglo rythmique, qui consiste à poser des parpaings en cadence.

1. Qu’est-ce que l’algomachin ?

Avez-vous déjà ouvert un livre de recettes de cuisine ? Avez vous déjà déchiffré un mode d’emploi traduit directement du coréen pour faire fonctionner un magnétoscope ou un répondeur téléphonique réticent ? Si oui, sans le savoir, vous avez déjà exécuté des algorithmes. Plus fort : avez-vous déjà indiqué un chemin à un touriste égaré ? Avez vous fait chercher un objet à quelqu’un par téléphone ? Ecrit une lettre anonyme stipulant comment procéder à une remise de rançon ? Si oui, vous avez déjà fabriqué – et fait exécuter – des algorithmes. Comme quoi, l’algorithmique n’est pas un savoir ésotérique réservé à quelques rares initiés touchés par la grâce divine, mais une aptitude partagée par la totalité de l’humanité. Donc, pas d’excuses…

2. Définissons l’algorithmique

Un algorithme, c’est une suite d’instructions, qui une fois exécutée correctement, conduit à un résultat donné. Si l’algorithme est juste, le résultat est le résultat voulu, et le touriste se retrouve là où il voulait aller. Si l’algorithme est faux, le résultat est, disons, aléatoire, et décidément, cette saloperie de répondeur ne marche pas. Complétons toutefois cette définition. Après tout, en effet, si l’algorithme, comme on vient de le dire, n’est qu’une suite d’instructions menant celui qui l’exécute à résoudre un problème, pourquoi ne pas donner comme instruction unique : " résous le problème ", et laisser l’interlocuteur se débrouiller avec ça ? A ce tarif, n’importe qui serait champion d’algorithmique sans faire aucun effort. Pas de ça Lisette, ce serait trop facile. Le malheur (ou le bonheur, tout dépend du point de vue) est que justement, si le touriste vous demande son chemin, c’est qu’il ne le connaît pas. Donc, si on n’est pas un goujat intégral, il ne sert à rien de lui dire de le trouver tout seul. De même les modes d’emploi contiennent généralement (mais pas toujours) un peu plus d’informations que " débrouillez vous pour que ça marche ". Pour fonctionner, un algorithme doit donc contenir uniquement des instructions compréhensibles par celui qui devra l’exécuter. C’est d’ailleurs l’un des points délicats pour les rédacteurs de modes d’emploi : les références culturelles, ou lexicales, des utilisateurs, étant variées, un même mode d’emploi peut être très clair pour certains et parfaitement abscons pour d’autres. En informatique, heureusement, il n’y a pas ce problème : les choses auxquelles ont doit donner des instructions sont les ordinateurs, et ceux-ci ont le bon goût d’être tous strictement aussi idiots les uns que les autres.

3. Faut-il être matheux pour être bon en algorithmique ?

Je consacre quelques lignes à cette question, car cette opinion aussi fortement affirmée que faiblement fondée sert régulièrement d’excuse : " moi, de toute façon, je suis mauvais(e) en algo, j’ai jamais rien pigé aux maths ". Faut-il être " bon en maths " pour expliquer correctement son chemin à quelqu’un ? Je vous laisse juge. La maîtrise de l’algorithmique requiert deux qualités :

• il faut être rigoureux. Car chaque fois qu’on écrit une série d’instructions qu’on croit justes, il faut se mettre à la place de la machine qui va les exécuter, pour vérifier si le résultat obtenu est bien celui que l’on voulait. Mais cette opération ne requiert pas la moindre once d’intelligence, uniquement d’être méthodique.
• il faut avoir une certaine intuition, car aucune recette ne permet de savoir a priori quelles instructions permettront d’obtenir le résultat voulu. C’est là, si l’on y tient, qu’intervient la forme " d’intelligence " requise pour l’algorithmique. Alors, c’est certain, il y a des gens qui ont au départ davantage cette intuition que les autres. Mais… mais d’une part, les réflexes, cela s’acquiert, et l’expérience finit par compenser largement bien des intuitions. D’autre part, pour être bon en algo, il ne faut pas oublier le point numéro 1.

4. L’ADN, les Shadoks, et les ordinateurs Quel rapport me direz-vous ? Eh bien le point commun est : quatre mots de vocabulaire. L’univers lexical Shadok, c’est bien connu, se limite aux termes " Ga ", " Bu ", " Zo ", et " Meu ". Ce qui leur a tout de même permis de formuler quelques fortes maximes, telles que : " Mieux vaut pomper et qu’il ne se passe rien, plutôt qu’arrêter de pomper et risquer qu’il se passe quelque chose de pire " . L’ADN, qui est en quelque sorte le programme génétique, l’algorithme à la base de construction des êtres vivants, est une chaîne construite à partir de quatre éléments invariables. Ce n’est que le nombre de ces éléments, et l’ordre dans lequel ils sont arrangés, qui va déterminer si on obtient une puce ou un éléphant. Et tous autant que nous sommes, splendides réussites de la Nature, avons été construits par un " programme " constitué uniquement de ces quatre briques, ce qui devrait nous inciter à la modestie. Enfin, les ordinateurs, quels qu’ils soient, ne sont fondamentalement capables d’exécuter que quatre opérations logiques (je n’inclus pas ici les opérations de calcul). Ces opérations sont :

• l’affectation de variables
• la lecture / écriture
• les tests
• les boucles

Un algorithme informatique se ramène donc toujours au bout du compte à la combinaison de ces quatre petites briques de base. Il peut y en avoir quelques unes, quelques dizaines, et jusqu’à plusieurs centaines de milliers dans certains programmes de gestion. Rassurez-vous, dans le cadre de ce cours, nous n’irons pas jusque là (cependant, la taille d’un algorithme ne conditionne pas en soi sa complexité : de longs algorithmes peuvent être finalement assez simples, et de petits très compliqués).

5. Algorithmique et programmation

Pourquoi apprendre l’algorithmique pour apprendre à programmer ? En quoi a-t-on besoin d’un langage spécial, distinct des langages de programmation compréhensibles par les ordinateurs ? Parce que l’algorithmique exprime les instructions résolvant un problème donné indépendamment des particularités de tel ou tel langage. Pour prendre une image, si un programme était une dissertation, l’algorithmique serait le plan, une fois mis de côté la rédaction et l’orthographe. Or, vous savez qu’il vaut mieux faire d’abord le plan et rédiger ensuite que l’inverse…

6. Avec quelles conventions écrit-on un algorithme ?

Historiquement, plusieurs types de notations ont représenté des algorithmes. Il y a eu notamment une représentation graphique, avec des carrés, des losanges, etc. qu’on appelait des organigrammes. Aujourd’hui, cette représentation est quasiment abandonnée, pour deux raisons. D’abord, parce que dès que l’algorithme commence à grossir un peu, ce n’est plus pratique du tout du tout. Ensuite parce que cette représentation favorise le glissement vers un certain type de programmation, dite non structurée (nous définirons ce terme plus tard), que l’on tente en général d’éviter. C’est pourquoi on utilise généralement une série de conventions appelée " pseudo-code ", qui ressemble à un langage authentique, la plupart des problèmes de syntaxe étant mis de côté.