algorithme (informatique)

1

Présentation

algorithme (informatique), procédé de calcul mis en œuvre sur un ordinateur, et qui, répété autant de fois qu’il est nécessaire, permet d’obtenir le résultat cherché.

2

Historique

Le mot algorithme n’est pas dérivé d’un mot latin ou grec, mais d’une contraction et d’une dérivation du nom du mathématicien arabe al-Khuwarizmi qui publia deux livres importants : l’un sur l’arithmétique et l’autre sur « l’action de faire passer et d’agencer les parties d’un tout » (titre original : Kitab al-jabr wal muqabala). Trois siècles plus tard, le livre, traduit en latin, porta le nom Algorismus.

La première définition du mot algorithme, dans son sens actuel, a été donnée par le mathématicien russe Markov : « Tout ensemble de règles précises qui définit un procédé de calcul destiné à obtenir un résultat déterminé à partir de certaines données initiales .» Les algorithmes sont constitués par un ensemble de règles précises et compréhensibles par tous. Ils s’appliquent à des données qui peuvent changer et élaborent les résultats en fonction des données initiales.

3

Liste d’instructions

Un algorithme se présente comme une liste d’instructions de nature mathématique ou logique pouvant être programmées ; il peut se traduire schématiquement par un organigramme. Convenablement utilisés, les algorithmes informatiques offrent des performances bien supérieures aux méthodes de résolutions manuelles et peuvent être appliqués à des problèmes de taille importante. Ils sont également à la base de méthodes de traitement de l’information : tri en mémoire centrale d’ordinateur, recherche rapide d’informations. Le traitement de données textuelles, la traduction des langages de programmation et le calcul formel représentent d’autres domaines faisant appel à des algorithmes adaptés et efficaces. Un algorithme informatique doit répondre à des règles opérationnelles : il doit être fini et se terminer après un nombre fini d’opérations, chaque instruction doit être définie sans ambiguïté, le fonctionnement de l’algorithme est déterministe (il donne les mêmes résultats pour les mêmes données) et toutes les opérations doivent pouvoir être effectuées par une personne en utilisant des moyens manuels (papier et crayon). Il n’existe pas de méthode pour découvrir un algorithme. Sa réalisation est un acte créatif. De plus, un même problème peut être résolu au moyen de plusieurs algorithmes.

4

Problèmes, algorithmes, programmes

Un ordinateur ne sait rien faire ; il peut être comparé à une marionnette sans ses fils. Pour qu’il puisse prendre vie, il doit mettre en œuvre des programmes. Pour créer ces programmes, appelés logiciels, il faut formaliser le problème, exprimer les actions à exécuter sous la forme d’algorithmes et les traduire dans un langage de programmation.

Soit l’énoncé suivant : « Tracer un octogone régulier .» On ne peut pas directement en déduire l’algorithme. Il faut réfléchir sur les caractéristiques de l’octogone régulier pour espérer pouvoir résoudre l’énoncé. Lorsqu’on aura découvert qu’un octogone est une figure plane, formée par une ligne fermée à huit angles et huit côtés égaux, on sera à même d’écrire l’algorithme du tracé. Il faut être conscient de la complexité et de la difficulté du problème pour mettre en œuvre les bons traitements. Par exemple dans notre énoncé, on utilisera une instruction de tracé de ligne et une instruction de boucle :

• Se placer en un point d’origine
• Répéter
• Tracer un côté de longueur L
• Tourner de 60 degrés
• Jusqu’à 8 fois
• Fin

En revanche, dans une problématique de gestion de stock, il faudra peut-être utiliser des bases de données, des instructions de tri et de calcul.

Pour décrire les algorithmes, il existe des méthodes, comme par exemple les organigrammes pour l’enchaînement des tâches et les tables de décisions pour la description des choix logiques. Aujourd’hui, la plupart des méthodes sont instrumentées et assistent le concepteur dans sa démarche d’analyse.