Algorithmes [Algorithmes et programmes]

Algorithmes

Objectif

Comprendre le concept d'algorithme.

Mise en situation

Aujourd'hui, il est courant d'entendre parler d'algorithmes, et ce n'est plus un terme réservé aux milieux des mathématiques et de l'informatique. Dans le même temps, ce terme a dérivé de sa signification première, et il est fréquent que sa définition ne soit pas bien comprise. En effet, le grand public parle souvent d'un algorithme pour désigner le fonctionnement obscur d'une application, ou à l'inverse une sorte de solution miracle à tous les maux. En réalité, la définition d'un algorithme est plus simple et neutre que ce que l'on peut croire.

Étymologie

Le mot algorithme vient du nom du mathématicien perse Al-Khwârizmî. Il n'a pas inventé la notion d'algorithme mais a eu une grande influence sur les mathématiques de son époque, par exemple en classifiant les algorithmes existants ou en diffusant l'utilisation des nombres arabes grâce à son Traité du système de numération des Indiens.

Définition : Définition simple

Un algorithme est une suite finie et non ambiguë d'opérations ou d'instructions permettant de résoudre un problème. Un algorithme prend des paramètres d'entrée et retourne un résultat.

Définition : Faire tourner un algorithme

« Faire tourner un algorithme » consiste à réaliser manuellement, une à une, les instructions et opérations de l'algorithme.

Finitude

Il est indispensable que l'algorithme soit une suite finie d'instructions, sinon il serait simplement impossible de résoudre le problème. En effet, il est impossible de réaliser une suite infinie d'instructions par définition.

Non-ambiguïté

Les instructions (ou les opérations) doivent être très simples afin de s'assurer qu'il est bien possible de réaliser l'algorithme. En d'autres termes, le résultat d'un algorithme doit être indépendant de l'interprétation de la personne le faisant tourner. Sinon, deux personnes différentes pourraient avoir deux résultats différents. De plus, une ambiguïté pourrait masquer un problème sous-jacent, potentiellement insoluble.

Exemple : Instructions simples

Voici des exemples d'instructions simples et répandues :

Tant que x > 0 alors : ...
Pour i de 1 à 30 faire : ...
Si x > 0 alors : ...
Soit x de valeur initiale 21
x prend la valeur 84
Incrémenter la valeur de x
x prend la valeur de x + y

Exemple : Algorithme simple

Voici un algorithme qui prend un nombre en entrée et écrit sa table de multiplication jusqu'à 10.

Entrées: 
    x nombre
Pour i de 1 à 9 alors:
    résultat prend la valeur i * x
    Afficher i * x = résultat
FinPour

Entrées: 
    x nombre

Pour i de 1 à 9 alors:
    résultat prend la valeur i * x
    Afficher i * x = résultat
FinPour

Cet algorithme peut être implémenté en JavaScript, par exemple à travers le code suivant :

const x = Number(prompt("Enter the value of x :"))
for (let i = 1; i < 10; i++) {
  const result = x * i
  console.log(i, "*", x, "=", result)
}

const x = Number(prompt("Enter the value of x :"))

for (let i = 1; i < 10; i++) {
  const result = x * i
  console.log(i, "*", x, "=", result)
}

Analogie avec une recette de cuisine

Pour introduire la notion d'algorithme, il est commun de le comparer à une recette de cuisine. Celle-ci correspond parfaitement à la définition ci-dessus car ses instructions sont bien finies et non ambiguës. Si ce n'est pas le cas, la recette sera impossible à réaliser.

À retenir

Un algorithme est une suite d'instructions précisément définies permettant de réaliser une tâche.