Découvrir l’algorithmique

1. Un premier exemple d’algorithme

Si le bourgeois gentilhomme de Molière, monsieur Jourdain, pratiquait la prose sans en avoir conscience, nous utilisons tous, sans le savoir, un mode de pensée rationnelle et analytique, assimilable, en un certain sens, à un algorithme. En effet, nos vies personnelles et professionnelles sont remplies d’objectifs que nous nous fixons, ou qui nous sont attribués, et que nous essayons d’atteindre au mieux. Pour y parvenir, nous décomposons généralement en étapes et actions le chemin, parfois le labyrinthe, permettant de passer de l’idée de l’objectif à sa réalisation. Illustrons ceci avec un exemple trivial, emprunté à notre quotidien : celui de la recette de cuisine.

Admettons que vous soyez un cuisinier débutant, disposant de plaques de cuisson et capable d’utiliser des ustensiles de cuisine, notamment une casserole. L’heure du déjeuner approchant, vous décidez de préparer rapidement un plat de pâtes au beurre. Pour ce faire, vous réalisez la séquence d’actions suivantes :

Prendre une casserole 
La remplir d'eau 
Porter la casserole à ébullition 
Prendre des pâtes 
Les plonger dans l'eau lorsque l'eau bout 
Régler votre minuteur sur 7 minutes 
Éteindre les plaques de cuisson lorsque le minuteur sonne 
Retirer la casserole des plaques de cuisson 
Égoutter les pâtes à l'aide d'une passoire 
Servir les pâtes dans une assiette 
Prendre le pain de beurre 
Prendre un couteau 
Découper une noix de beurre avec le couteau 
Mélanger la noix de beurre avec les pâtes 

En préparant ce déjeuner, vous venez d’exécuter un algorithme, ceci sans vous en rendre compte ; c’est-à-dire, formulé sommairement, une séquence d’actions réalisant un objectif.

Le résultat de cet algorithme est un plat de pâtes au beurre réalisé à partir de deux ingrédients : des pâtes et du beurre.

Nous dirons que les ingrédients (pâtes et beurre) constituent les entrées de l’algorithme tandis que le plat préparé...

1. L’objectif de l’algorithme

Le point de départ est naturellement l’objectif du programme et donc celui de l’algorithme. L’objectif répond à la question du quoi ?, qui elle-même dérive de la raison d’être du programme, correspondant au pourquoi. Rappelons que l’algorithme répond lui à la question du comment, c’est-à-dire comment implémenter l’objectif ou, par quel chemin relier les entrées à la sortie, ce chemin s’écrivant comme une séquence de primitives.

Il est impératif que l’objectif décrive le plus précisément possible la sortie attendue du programme. De plus, il est possible, et même souhaitable, d’expliciter des contraintes sur cette sortie. La formulation de l’objectif peut également décrire les entrées du programme, mais il est possible qu’à ce stade, les entrées nécessaires à la production de la sortie ne soient pas encore parfaitement claires dans l’esprit du développeur.

Considérons l’objectif simple suivant : « Calculer le reste de la division entière de deux entiers naturels ».

Dans cet exemple, on a clairement décrit la sortie attendue (le reste d’une division entière), on a aussi indiqué les entrées de l’algorithme (deux entiers naturels). Nous pourrions ajouter une contrainte, par exemple « Le reste doit être un entier naturel », ce qui sous-entendrait qu’il ne peut être négatif.

2. Exécution pas à pas d’un exemple pour induire un principe plus général

Le principe de l’algorithme exprime, idéalement en une phrase, l’idée permettant...

1. Données et actions élémentaires

Comme nous l’avons dit, les algorithmes manipulent des données en entrée pour calculer la ou les données de sortie. De plus, d’autres données internes sont généralement nécessaires aux calculs intermédiaires.

Toutes ces données peuvent être des constantes ou des variables. Par définition, les données constantes sont invariables.

Si les constantes peuvent apparaître « en dur » dans l’algorithme, c’est-à-dire explicitement, nous préconisons de leur donner un nom pour faciliter la lecture du pseudo-code. À l’évidence, le nombre π se lit plus aisément que 3,14159265358979.

Une donnée est donc une constante ou une variable, elle possède un nom et une valeur peut lui être affectée ou assignée, la première affectation s’appelle l’initialisation ; avant celle-ci, la donnée a une valeur indéterminée, c’est-à-dire inconnue.

Nous noterons l’affectation d’une valeur à une donnée nommée NOM_DE_LA_DONNÉE comme suit :

NOM_DE_LA_DONNÉE <- valeur 

La valeur affectée à une donnée peut résulter d’une opération :

SOMME <- 10 + 5 

Le type de la valeur affectée doit être identique ou compatible avec celui de la donnée. Lorsqu’ils sont différents mais compatibles, une conversion est effectuée implicitement.

Par exemple NUM NOMBRE <- ‘4’ suppose...

1. Le load balancing

Il est courant d’avoir à répartir l’effort de traitement (CPU, volumes, etc.) sur plusieurs processeurs, disques, etc. C’est le thème de la répartition de charge (load balancing).

Ici l’objectif est donc l’équilibrage et la répartition de la charge d’un service sur plusieurs entités. On est souvent amené à choisir l’algorithme le plus adapté à son contexte, comme « comment répartir les accès à des informations situées sur plusieurs ordinateurs, entre plusieurs personnes, en parallèle et en privilégiant ou non tel ou tel comportement global ».

Ce type d’algorithme comprend deux familles (les deux listes ne sont pas exhaustives) :