Algorithmes, mode d’emploi

Ada Lovelace. © Heritage images / Leemage
En 1843, un siècle avant la naissance des calculateurs électroniques, Ada Lovelace formule les premières idées fondamentales de l’informatique. Elle contribue à améliorer les premiers programmes, conçus alors sur papier.

Elle s’appelle Ada, Augusta Ada King, comtesse de Lovelace, fille du célèbre poète Lord George Gordon Byron. Certains vous diront qu’elle a juste joué un rôle de représentation publique, mais ne les écoutez pas : c’est bien grâce à elle que le premier programme informatique a été écrit (cf. dossier en ligne sur DocSciences).

Elle travaille avec Charles Babbage, mathématicien, sur la « machine analytique ». Pour faire marcher cette future machine, Ada crée des « diagrammes » qui ont pour but d’expliquer comment doit procéder la machine pour arriver au résultat recherché… et ceci indépendamment de la façon dont sont réalisées ces opérations. Ce sont des « algorithmes ».

Le mot algorithme vient du nom du grand mathématicien perse Al – Khwarizmi (vers l’an 820) qui introduit en Occident la numération décimale (rapportée d’Inde) et enseigne les règles élémentaires des calculs s’y rapportant. La notion d’algorithme est donc historiquement liée aux manipulations numériques, mais elle s’est progressivement développée pour porter sur des objets de plus en plus complexes : des textes, des images, des formules logiques, des objets physiques…

Un algorithme, très simplement, est une méthode, une façon systématique de procéder pour faire quelque chose : trier des objets, situer des villes sur une carte, multiplier deux nombres, extraire une racine carrée, chercher un mot dans le dictionnaire… Il se trouve que certaines actions mécaniques ? peut-être toutes ! ? se prêtent bien à cette décomposition. On peut les décrire de manière générale, identifier des procédures, des suites d’actions ou de manipulations précises à accomplir séquentiellement. Décomposer chaque action en actions élémentaires pour mieux les recombiner ensuite. C’est cela, un algorithme. En tant que méthode, il répond donc à des questions du type : « Comment faire ceci ? », « Comment obtenir cela ? », « Comment trouver telle information ? », « Comment calculer tel nombre ? ». C’est un concept pratique, qui traduit la notion intuitive de procédé systématique, applicable mécaniquement, sans réfléchir, en suivant simplement un « mode d’emploi » précis.

Mais comment être sûr qu’un mode d’emploi soit rigoureusement précis ? qu’il marche vraiment dans tous les cas sans avoir besoin d’intelligence ? Il suffit de vérifier que même la chose la plus idiote au monde puisse l’utiliser. Prenons le tout premier monstre (virtuel) venu d’un jeu vidéo, appelons-le Gnirut, et voyons ce qu’il saurait faire en étant très très bête.

Gnirut : le monstre testeur

Gnirut, un monstre codeur. © S. Auvin Ce personnage incarne la « machine de Turing ». Cette « machine » n’existe pas réellement, c’est un modèle qui permet d’étudier l’informatique et sur lequel se base le fonctionnement des ordinateurs.

Disons que Gnirut ne sait même pas compter jusqu’à 2 ! Il ne connaît que 0 (pour lui c’est un blanc [ ]) et 1 (pour lui c’est un bâton [I]). Au-delà, il s’embrouille. Supposons aussi qu’il ne se souvient de rien, il note tout sur un gigantesque ruban, sans limite ni à gauche ni à droite, composé de cases qui contiennent chacune un blanc ou un bâton.

Faire exécuter un algorithme à Gnirut revient à lui donner une suite finie d’instructions. Chacune de ces instructions se décompose en quatre actions élémentaires :
1) lire la case qui est devant lui ;
2) soit écrire un bâton si la case est vide ou effacer un bâton dans le cas contraire, soit ne rien faire ;
3) soit décaler le ruban d’une case vers la droite, soit vers la gauche, soit ne pas le déplacer ;
4) passer à une nouvelle instruction.

Gnirut applique chaque instruction à son ruban et passe de l’une à l’autre selon le résultat de la précédente. Il faut aussi prévoir l’instruction « Stop », sinon il continuerait sans jamais s’arrêter ! Pour Gnirut, un algorithme est l’enchaînement de ces instructions appliquées à son ruban.

Voilà ce qu’on peut demander de plus idiot à un individu (réel ou virtuel). Mais, il n’est nul besoin d’invoquer ce pauvre Gnirut imaginaire, il y a plein de manières (avec de la mécanique, de l’électronique ou même de l’optique) de construire une machine qui va pouvoir exécuter les instructions que l’on demande à Gnirut. Ces machines s’appuient sur le modèle abstrait des « machines de Turing ».

Une bête de code

Tous les informaticiens du monde sont d’accord sur le fait que Gnirut, même avec aussi peu de compétences, peut faire du codage. En effet, il peut coder des chiffres sur son ruban, par exemple en binaire : [ ][ ][ ] pour 0, [ ][ ][I] pour 1, [ ][I] [ ] pour 2, [ ][I][I] pour 3… et, en mettant suffisamment de chiffres bout à bout, il peut coder tous les nombres. Il peut aussi y coder des lettres, [ ][ ][ ][ ][ ] pour le A et ainsi de suite, jusqu’à coder des textes entiers. Il peut aussi coder des couleurs, des lignes de couleurs et, en conséquence, des images ! Les notes de musique et les mélodies ne lui échappent pas non plus ! De proche en proche il peut (avec vraiment beaucoup de blancs et de bâtons) coder tous les objets de l’univers qui l’entoure ! Ces codes n’ont rien à voir avec la réalité : ce sont juste des signes pour la représenter (Voir l’article Nom de code : binaire).

Ensuite, avec les bonnes instructions, Gnirut peut faire des opérations sur ces nombres ou ces signes.

Par exemple, « Ajouter 1 à un nombre » : c’est facile, même pour lui ! Il suffit d’abord d’aller le plus à droite du nombre, codé en binaire avec des blancs et des bâtons. Si c’est un blanc, Gnirut le transforme en bâton et il a fini. Si c’est un bâton, il le transforme en un blanc et, comme il y a une retenue, il se déplace d’un pas à gauche, il regarde le nouveau chiffre et… il applique la même règle qu’à la case d’avant ! Tout cela, Gnirut peut le faire en ayant toutes les instructions élémentaires dont il a besoin. Ensuite, en combinant les instructions précédentes, il peut aller jusqu’à 2 : il sait ajouter 1 à un nombre, donc faire une opération comme 1 1 ! Bien que Gnirut ne sache pas ce qu’est 2, il va quand même pouvoir calculer 2 en suivant les instructions. Ainsi, il est capable de faire toutes les additions. Avec d’autres paquets d’instructions, il fait des soustractions, teste si un nombre est égal à un autre… et beaucoup d’autres opérations de calcul. Voilà Gnirut au moins aussi utile qu’une calculette !

Gnirut, l’ordi… nosaure

De plus, si les blancs et les bâtons correspondent à des signes (lettres et mots, notes et mélodies, couleurs et images), c’est-à-dire si Gnirut dispose des données codées, il peut, en combinant des quantités d’instructions, mémoriser des documents, rechercher des mots dans des textes, trier, comparer, combiner… Il est en mesure de faire précisément ce que tous les ordinateurs du monde font !

Mais au fait, comment Gnirut fait-il pour se souvenir de ces instructions, pour les enchaîner, passer des unes aux autres ? Il va utiliser un deuxième ruban. Gnirut a juste à se souvenir de décaler le ruban à gauche ou à droite, d’écrire un blanc ou un bâton et de retenir le numéro de l’instruction suivante (codée elle aussi avec des blancs et des bâtons). Rien de plus facile à coder. Gnirut note alors toutes ces instructions (toujours à l’aide de blancs et de bâtons) sur un deuxième ruban qu’il n’a plus qu’à lire au fur et à mesure pour enchaîner toutes les instructions. Trop compliqué pour Gnirut me direz-vous ? Non !

Un ruban universel

En effet, pour lire ce deuxième ruban, il n’a besoin d’apprendre que quelques instructions qui lui permettent alors de trouver les instructions pour faire toutes les opérations possibles sur le premier ruban.

Finalement, Gnirut n’est pas si bête, il pourrait même être le boss de fin du jeu ! En effet, il n’y pas un calcul « mécanique », pas un « traitement automatique » que Gnirut ne sache faire avec ses deux rubans ! Quand ce n’est pas Gnirut mais un objet qui fonctionne ainsi, on parle ici de « machine de Turing universelle ».

Cela montre aussi combien calculer est un processus physique, comment les mathématiques s’incarnent quand elles deviennent algorithmes. C’est un processus physique qui marche avec ces « machines universelles à algorithmes » et il est possible que de nouvelles technologies (mécanismes biologiques, nanocalculateurs…) bouleversent complètement cette vision des algorithmes élémentaires : un sujet passionnant à suivre.

De monstrueux calculs

Tous les mathématiciens le pensent : tout ce qui est « calculable », lorsque l’on considère des nombres, ou « décidable », lorsque l’on considère des signes, peut se faire sur une machine de Turing. Ils ont « démontré » que tout ce qui est construit mathématiquement et qui correspond à ces mécanismes (fonctions calculables…) se ramène à ce que sait faire Gnirut avec ses deux rubans ! Cet état de fait s’appelle la thèse de « Church-Turing » qui « tient » depuis plus de cinquante ans. Vraiment tout ? Pas si simple. Cela peut prendre un temps énorme, « exponentiel » ! Cette difficulté se retrouve dans de nombreux problèmes « combinatoires » : il y a bien des choses que l’on peut faire en temps raisonnable, comme trier des données ou trouver le plus court chemin, mais des problèmes aussi simples que remplir au mieux un sac à dos ne pourront jamais ? c’est démontré mathématiquement ? être résolus efficacement. Il faudrait explorer presque toutes les possibilités et cela donne alors des temps de calculs vertigineux ? plusieurs siècles même avec l’électronique la plus rapide ? dès que la taille du problème augmente de beaucoup. On qualifie un tel problème de « NP-complet ». Cela peut ainsi ne jamais aboutir ! Par exemple, il est indispensable de savoir si un algorithme finit par s’arrêter ou s’il boucle indéfiniment. Un algorithme peut-il résoudre automatiquement ce problème ? Eh bien non ! Il n’existe pas d’algorithme qui puisse tester à coup sûr si un autre algorithme finit par s’arrêter ou non. Tous les algorithmes risquent de boucler indéfiniment ou de tomber dans un cas « singulier » qui provoque une erreur. Pire encore : beaucoup d’algorithmes qui seraient bien utiles pour contrôler la façon de faire des algorithmes n’existent pas !

Finalement Gnirut et ses deux rubans n’ont pas fini de nous faire cogiter. Surtout que les mathématiciens ont bien démontré que tous les ordinateurs du monde ne sont que des machines de Turing qui peuvent exécuter en une fois des gros blocs d’instructions. Mais leur mémoire est finie, contrairement aux rubans de Gnirut.

Les talents cachés de Gnirut

En attendant que les informaticiens aient fini de comprendre ces problèmes, essayons de faire des choses utiles avec les machines de Turing :

• programmer un robot pour qu’il sorte d’un labyrinthe (par exemple en le faisant toujours aller à droite sans jamais qu’il ne revienne sur son parcours) ;
• chercher un mot dans le dictionnaire ;
• trouver le chemin le plus court d’un point à un autre (par exemple en simulant un groupe de personnes qui à chaque carrefour se sépare en deux, pour explorer toutes les combinaisons… le premier arrivé prévenant tous les autres) ;
• tester si un théorème mathématique est exact (en générant toutes les formules exactes possibles à l’aide des règles de la logique, des formules de plus en plus longues et en regardant si la formule recherchée apparaît) ;
• simuler des phénomènes naturels, comme la météo de la semaine à venir, ou contrôler des systèmes comme un moniteur cardiaque ou un avion de ligne…

Il n’est pas question de redonner à chaque fois toutes les instructions élémentaires, nous ne nous en sortirions pas ! Comment faire ? Il existe deux méthodes efficaces. Gnirut sait faire une addition. Convenons avec lui que si on dit : « Additionner A et B. », il copie le nombre A sur son ruban, tout comme le nombre B, puis il enchaîne toutes les instructions pour que la somme A B s’inscrive aussi sur son ruban. Nous avons défini la fonction « addition » et pouvons désormais concevoir des algorithmes sans revenir à de tels détails. On fait de même avec toutes les opérations susceptibles d’être utilisées : multiplier, comparer, trier… mais aussi : afficher une image, tracer une droite, jouer une note de musique… On définit la fonction et ses paramètres, par exemple : « Jouer do pendant 1 seconde. » où la note (do) et sa durée (1 seconde) sont des paramètres. Une fois défini « Jouer une note pendant une durée. » avec d’autres fonctions elles-mêmes définies avec d’autres fonctions… jusqu’aux instructions élémentaires elles-mêmes déjà définies (sur le ruban), nous allons pouvoir les combiner et… jouer de la musique.
Comment organiser ces fonctions pour faire des choses de plus en plus complexes ? C’est très simple. Il y a trois grandes idées : combiner les fonctions, introduire des choix, des branchements, et utiliser des boucles ou des définitions récursives. Ainsi on peut décrire de manière prodigieusement concise tous les algorithmes.

Ce sont les langages informatiques qui permettent de « mettre en musique » ces mécanismes… grâce à la programmation.

Pour aller plus loin, nous vous proposons quelques références bibliographiques.

Cet article est paru dans la revue DocSciences n°5 Les clés de la révolution numérique, éditée par le CRDP de l’Académie de Versailles en partenariat avec l’INRIA.