Du point de vue de l'informatique, le mathématicien Jacques RIGUET donne la définition suivante d'un algorithme:
"On appelle algorithme une méthode générale pour la résolution d'une classe de problèmes, fixée en tous ses détails par des règles dépourvues de sens, de façon à ce qu'on puisse l'appliquer sans avoir à la comprendre."
Des définitions précédentes, on peut déduire qu'un algorithme est un procédé systématique qui est largement indépendant du caractère sémantique attaché aux informations traitées. Il doit vérifier les cinq règles suivantes:
L'énoncé d'un algorithme doit comprendre une définition des données auxquelles il s'applique.
Normalement, un algorithme possède une ou plusieurs données d'entrée [angl. input data; all. Eingabedaten], c'est-à-dire des valeurs qui sont connues avant son exécution et sur lesquelles l'algorithme est appliqué. Comme un algorithme doit tenir compte des propriétés des données d'entrée, l'ensemble de ces données doit être spécifié de façon exacte. Evidemment cet ensemble peut être l'ensemble vide.
Un algorithme possède une ou plusieurs données de sortie [angl. output data; all. Ausgabedaten], c'est-à-dire des valeurs produites par lui-même. Ces données sont en relation exactement spécifiée avec les données d'entrée.
Un algorithme doit se terminer après un nombre fini de pas.
Le concepteur d'un algorithme doit vérifier attentivement que l'algorithme est fixé dans tous ses détails, c'est-à-dire que l'algorithme décrit précisément la procédure qu'il doit suivre, que tous les cas ont été prévus et, en particulier, que l'ordre dans lequel les règles devront être appliquées n'est pas ambigu.
Chaque opération doit donc être définie d'une manière précise et claire.
Cette tâche est connue sous le nom d'affinement progressif de l'algorithme ou conception descendante.
Exemple: Considérons l'exemple, pris de la vie courante, qui est celui de la personne qui indique à un étranger l'itinéraire pour aller dans une certaine rue. L'algorithme qu'elle donne est par exemple le suivant: "Tourner à droite au magasin, allez jusqu'au prochain croisement, puis prenez la troisième rue à gauche . . . ". Cette description est presque parfaite à l'exception de quelques détails près (à quel magasin tourner, par exemple) et risque fort d'entraîner l'étranger vers une toute autre rue. Or, l'étranger a la possibilité de demander plus de renseignements à la personne. Malheureusement les ordinateurs n'ont pas encore cette ressource.
Pour des raisons pratiques, un algorithme doit pouvoir être exécuté de manière efficace.
On dit qu'un algorithme doit être efficace ce qui signifie que:
• chaque opération doit être suffisamment simple, afin qu'elle soit exécutable en un temps fini,
• le nombre d'opérations doit être fini et limité de façon à ce que la machine soit capable de terminer leur exécution dans un temps raisonnable.
Considérons l'exemple suivant:
Exemple: Calcul de la racine carrée d'un nombre réel positif N
Méthode:
(1) Remplacer X par 1;
(2) Diviser N par X;
(3) Additionner X et prendre la moitié;
(4) Remplacer X par le résultat obtenu;
(5) Continuer sous 2).
En exécutant séquentiellement les pas 1 à 5, on constate que la variable X tend vers ÖN. Pour N = 2, on obtient:
X0 =1
X1 = 1.5
X2 = 1.146
X3 = 1.413
. . .
Le nombre de pas étant infini, on ne peut qualifier la méthode ci-dessus d'algorithme. On dit que c'est une méthode de calcul [angl. computational method].
Remarque:
On notera qu'un ordinateur ne peut représenter des nombres arbitrairement grands et qu'un nombre réel est toujours calculé de façon approximative. Ceci implique concrètement qu'il faudrait démontrer (mathématiquement) d'un côté que toutes les formules utilisées sont algébriquement correctes, et vérifier d'un autre côté que toutes les valeurs des variables ainsi que toutes les valeurs intermédiaires appartiennent au domaine des valeurs pouvant être représenté par la machine
Ainsi par exemple, quoiqu'on a l'égalité
(a + b) - c = a + (b - c)
l'une des deux expressions peut retourner selon le cas une valeur n'appartenant pas au domaine des valeurs représentables par l'ordinateur.
Termes techniques
• affinement progressif
• clarté
• conception descendante
• efficacité
• entrée
• méthode de calcul
• sortie
• terminaison
© Aflo Informatique , 2003-2004