CRDP

Accueil > Les numéros > DocSciences 5 : Les clés de la révolution numérique

Algorithmes, mode d’emploi

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.

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 ».

JPEG - 90 ko
Un algorithme pour trois applications (© INRIA/TREC (haut) et GEOMETRICA (bas)/DocSciences)
Qu’ont en commun ces trois images ? Elles résultent du même type de calcul ! En effet, c’est le même algorithme qui a permis de représenter des réseaux informatiques (en haut), un objet en trois dimensions (à gauche) et une protéine (à droite)

Ce mot 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 (cf. ci-dessous)… 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.


Du plus simple au plus malin

Pour chercher un mot dans un dictionnaire, sans aucune information sémantique, une première méthode est de tourner les pages une à une. S’il y a 1 000 pages, il faut entre 1 et 1 000 gestes suivant que le mot commence par A ou Z. Cela est fastidieux, mais de cette façon on est sûr de ne pas manquer le mot recherché.

Les informaticiens savent faire mieux : ouvrir le dictionnaire en son milieu ; si le mot est situé avant le milieu, ne considérer que la première moitié des pages, s’il est situé après, ne considérer que la deuxième moitié ; ouvrir le dictionnaire au milieu de la moitié des pages considérées ; répéter le procédé jusqu’à ce qu’il ne reste qu’une page. Que se passe-t-il ?

À chaque fois, on ne considère que la moitié des pages, donc 1 000, 500, 250, 125, 63, 32, 16, 8, 4, 2, 1 page… et hop le mot est trouvé ! en 10 étapes au lieu de 1 000 ! Voilà un bel algorithme, « optimal », on ne peut pas être plus efficace, et qui « converge », diviser sans cesse le nombre de pages ne peut que finir par donner 1. Presque tous les algorithmes de recherche sont construits sur de tels mécanismes.

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.

En savoir plus

Sur DocSciences :

Livres

  • Delahaye J.-P., Complexités. Aux limites des mathématiques et de l’informatique, coll. « Bibliothèque scientifique », Belin - Pour la science, 2006.
  • Dewdney A. K., The (New) Turing Omnibus. 66 Excursions in Computer Science, Holt Rinehart and Winston, 2003.
  • Hernet P., Les Algorithmes, coll. « Que sais-je ? », n° 2928, Puf, 2002.

Sites Web