Algorithme

1 Définition

Les mots «algorithme» et «programmation» étant polysémiques, il est nécessaire de clarifier le sens que nous retiendrons dans ce document. Les mots «algorithme » et « programmation » s’entendent ici comme création d’un programme d’actions, à ne pas confondre avec « algorithme » qui signifierait «rythme de la douleur», ce qui serait une conception navrante des mathématiques ! Travailler les algorithmes en maternelle n’est pas seulement construire « des colliers de perles » de couleurs répétitives, etc. La notion d’algorithme n’est pas propre à l’informatique : en maths les programmes indiquent notamment la compétence cible « Mettre en œuvre un algorithme de calcul posé pour l’addition, la soustraction, la multiplication ». Une recette de cuisine est un algorithme, dont les actions sont de « casser les œufs », de « mettre de la farine » ou de « si nécessaire, rajouter un peu de sel ». En informatique, les actions dont il est question sont, par exemple, d’afficher une information à l’écran, de demander une donnée à l’utilisateur ou de faire un calcul. Elles sont souvent structurées par des boucles (qui permettent de répéter une séquence d’actions) et/ou des structures conditionnelles (structures Si-Alors-Sinon, qui permettent de faire une séquence d’actions ou une autre en fonction de l’évaluation d’une condition). Un programme est un algorithme traduit dans un langage de programmation. Un ordinateur est une machine qui (entre autres) est capable d’exécuter un programme ».

2 Définition

Le mot « algorithme » vient du nom du savant persan Al-Kharezmi (IXe siècle). « Un algorithme, c’est simplement une méthode, explique Gérard Berry, professeur au Collège de France. 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. Une méthode applicable sans réfléchir, mécaniquement, en suivant un mode d’emploi précis. » Bref, c’est une série d’instructions permettant d’obtenir un résultat. Une recette de cuisine, par exemple, c’est un algorithme.

3 Définition

Le mot « algorithme » vient du nom de l’auteur persan Al-Khuwarizmi (né vers 780 – mort vers 850). Une définition: « un algorithme est une suite finie de règles à appliquer dans un ordre déterminé à un nombre fini de données pour arriver, en un nombre fini d’étapes, à un certain résultat et cela indépendamment des données.»

Définition 4

Un algorithme est « une suite finie de règles à appliquer dans un ordre déterminé à un nombre fini de données pour arriver, sans indétermination, en un nombre fini d’étapes, à un certain résultat et cela indépendamment des données » (Michel Philippot). En mathématiques, l’algorithme d’Euclide (recherche du plus grand commun diviseur de deux nombres) figure parmi les exemples les plus célèbres. Et les programmes informatiques ne sont autres que des algorithmes transcrits en un langage compréhensible par l’ordinateur.

Définition 5

L’algorithme est une suite de raisonnements ou d’opération qui fournit la solution d’un problème. Procédure de résolution d’un problème ou d’un ensemble de problèmes de même type contenant des opérations bien définies portant sur des informations, s’exprimant dans une séquence définie sans ambigüité, destinée à être traduite dans un langage de programmation. Un programme n’est rien d’autre que la représentation d’un algorithme dans un langage plus technique compris par un ordinateur (par exemple : Assembleur, Cobol, Java, C++, . . .). Ce type de langage est appelé langage de programmation.

Définition 6

Un algorithme est une méthode générale pour résoudre un type de problèmes. Il est dit correct lorsque, pour chaque instance du problème, il se termine en produisant la bonne sortie, c’est-à-dire qu’il résout le problème posé. On mesure l’efficacité d’un algorithme notamment par sa durée de calcul, par sa consommation de mémoire vive (en partant du principe que chaque instruction a un temps d’exécution constant), par la précision des résultats obtenus (par exemple avec l’utilisation de méthodes probabilistes), sa scalabilité (son aptitude à être efficacement parallélisé), etc. Les ordinateurs sur lesquels s’exécutent ces algorithmes ne sont pas infiniment rapides, car le temps de machine reste une ressource limitée, malgré une augmentation constante des performances des ordinateurs. Un algorithme sera donc dit performant s’il utilise avec parcimonie les ressources dont il dispose, c’est-à-dire le temps CPU, la mémoire vive et (aspect objet de recherches récentes) la consommation électrique. L’analyse de la complexité algorithmique permet de prédire l’évolution en temps calcul nécessaire pour amener un algorithme à son terme, en fonction de la quantité de données à traiter.