Qu’est-ce qu’un algorithme ?
Même si les algorithmes sont souvent considérés comme étant du ressort exclusif des mathématiques et de l’informatique, leur champ d’application est en réalité beaucoup plus vaste.
Le mot « algorithme » vient du nom du grand mathématicien persan Al Khwarizmi (vers l’an 820), qui introduisit en Occident la numération décimale (rapportée d’Inde) et enseigna lesrè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, etc.
De la méthode
Un algorithme, très simplement, c’est une méthode. Une façon systématique deprocé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 à la décortication. 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. C’est cela, un algorithme. En tant que méthode, il répond donc à des questions du type : « comment faire ceci ? », « obtenir cela ? », « trouver telle information ? », « 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.
Unexemple commun est par exemple la recherche d’un mot dans le dictionnaire. On regarde d’abord la première lettre du mot, et on la compare avec celle des mots de la page où le dictionnaire est actuellement ouvert. Suivant la position relative des deux lettres en question dans l’ordre alphabétique, on tourne alors les pages en avant ou en arrière, jusqu’à ce que les premières lettres coïncident.Puis on reproduit la même procédure avec la deuxième lettre du mot, puis la troisième, et ainsi de suite… Cet algorithme familier nous indique que les objets manipulés ne sont pas nécessairement des nombres ou des objets mathématiques. Ici, ce sont des mots, ou des lettres. De plus, on comprend que pour qu’un algorithme soit applicable, il faut que les objets manipulés se présentent sous un formatbien précis, qui assure à la fois l’efficacité et la généralité du procédé. En l’occurrence, s’il s’agit d’un dictionnaire français, il faut que les mots recherchés soient des mots français écrits en lettres latines, et surtout que, dans le dictionnaire, les mots soient bien classés par ordre alphabétique !
Du nombre à l’information
La vertu essentielle des algorithmes est de permettrel’exécution optimisée de procédés répétitifs, essentiellement grâce à la formalisation et à la description des enchaînements logiques à un niveau plus abstrait, et donc plus général. Ils s’étendent ainsi à des domaines de la société toujours plus nombreux et plus inattendus. Cette généralisation a accompagné le développement des langages de programmation depuis les années 60, qui permettent aujourd’hui lamanipulation de structures et d’objets ayant des propriétés et des comportements analogues à ceux du monde ordinaire. Leur relation avec les couches profondes du traitement informatique est assurée après coup par le compilateur, de manière transparente pour le programmateur et le concepteur d’algorithmes.
En définitive, le codage numérique des objets manipulés (au niveau informatique) estdevenu secondaire pour l’algorithmique. L’essentiel est de percevoir les éléments clés d’un processus de calcul, ou d’un procédé quelconque, et d’imaginer les suites d’opérations logiques les plus astucieuses et les plus efficaces pour le mettre en œuvre de façon automatique et performante. L’algorithme est donc en réalité le squelette abstrait du programme informatique, sa substantifique moelle,…