Algorithmique

De tout temps les hommes ont utilisé des algorithmes. Avant même l’apparition des ordinateurs, les babyloniens (IIIème siècle avant JC) écrivaient des algorithmes sur leurs tablettes :

Les algoritmes, ces méthodes précises servant à résoudre des problèmes sont à la base de nos savoirs techniques dés le plus jeune âge : les méthodes pour additionner, soustraire multiplier, diviser, calculer le PGCD trouver des nombres premiers, etc., sont des algorithmes que l'on apprend dés l'école primaire...

Le terme algorithme nous vient du mathématicien perse Al-Khwârizmî (IXème siècle) Al-Khwârizmî (an 825 environ) est celui par lequel est introduisit en Occident la numération décimale et les règles de calculs s’y rapportant. bien avant l'apparition des ordinateurs. La première implémentation dans un langage de programmation d'un algorithme a été réalisé en 1843 par la mathématicienne Ada Lovelace sur la machine de Charles Babbage, ancêtre de nos ordinateurs (et magnifique objet "steampunk")

L'algorithmique qui à la base était liée aux manipulations numériques, s’est progressivement développée sur des objets plus complexes : graphes, textes, images, son, formules logiques, robotique, etc ...

Pour vous, l'algorithmique sera l'étape préliminaire durant laquelle on utilise son

et son

avant d'utiliser son

Approximativement un algorithme est une méthode c’est à dire une façon systématique de procéder pour faire quelque chose : trier, rechercher, calculer, ... Il répond à des questions du type: "comment faire ceci ?", "comment obtenir cela ?", "comment trouver telle information ?", "comment calculer tel nombre ?", ... C’est un concept pratique, qui traduit la notion intuitive de procédé systématique, applicable mécaniquement, sans réfléchir, en suivant simplement un mode d’emploi précis. Un algorithme est une série d'ordres précis et non ambigus qui, exécutés dans l'ordre (par un humain ou une machine de calcul), apporte une réponse à un problème à partir de données de départ, en un nombre fini d'étape. La réponse au problème est la donnée de sortie.

Les premiers algorithmes que l'on apprend à l'école sont : additionner, soustraire, multiplier et diviser.

Les variables d'entrée sont les deux nombres composer.
la variable de sortie est le résultat obtenu en un nombre fini d'étapes.
La méthode apprise est le coeur de l'algorithme.

Le crible d'Eratosthène est un algorithme permettant de trouver les N premiers nombres premiers.

La variable d'entrée est le nombre N où on s'arrête.
La variable de sortie est la liste des nombres premiers plus petits que N.
Le coeur de l'algorithme est la méthode consistant à barrer les multiples.

Attention, une recette de cuisine est un mauvais exemple d’algorithme car elle est toujours trop imprécise : une pincée de sel (quel poids ?), faire bouillir dix minutes (la température d’ébullition dépend entre autre de l’altitude à laquelle on se trouve). L’activité principale en algorithmique est de concevoir et d’exprimer en langage naturel un futur programme. Seule la première de ces étapes concerne vraiment l'algorithmique : elle est indispensable :

Algorithme rédigé en français (conception)
Codage dans un langage de programmation (programmation)
Traduction automatique en langage machine (compilation)
Exécution (partie utilisateur)

Les questions importantes qui se posent dans la conception d’un algorithme sont :

Quel type de données dois-je utiliser (des nombres entiers pour les notes n'est pas une bonne idée) ?
Mon algorithme fait-il ce que je veux qu'il fasse ?
Mon programme s'arrête-t-il toujours (voir les boucles While) ?
Mon programme est-il efficace ?

Les variables sont l’outil incontournable de désignation des données, qui pour être manipulées doivent être nommées. Avant même l’écriture de l’algorithme elles doivent être recensées et la liste apparaîtra en tête de l’algorithme. Cette liste comportera les noms, les types de ces données. Chaque algorithme représente ses données à l'aide de variables :

Une variable associe un nom (l'identifiant) à une valeur. L'identifiant doit-être unique.
Lister les noms de variable au début d'un algorithme s'appelle "déclarer les variables".

De manière symbolique, on peut représenter une case nommée contenant une valeur. Ci-dessous la variable "a" a pour valeur 12, la variable "b" a pour valeur la chaîne de caractères "bonjour" et la variable "c" a pour valeur la liste [2;3;5;7].

Donner une valeur à une variable s'appelle "affecter une variable". On note généralement : nom_de_la_variable ← valeur On affecte 5 à la variable x : x ← 5

Attention, l’affectation remplace la valeur précédente de la variable par la nouvelle. Ainsi l’instruction A ← 2 affecte la valeur 2 à la variable dont le nom est A et ceci quelle que soit la valeur contenue au préalable dans la variable. Ainsi l'instruction a ← a+1 signifie que la variable a reçoit l'ancienne valeur de a à laquelle on ajoute 1. Les données que l'on traite à l'aide d'un algorithme sont diverses et peuvent être de différents type

Le type entier : sert à représenter les nombres entiers relatifs.
Le type flottant : sert à représenter les nombres décimaux.
Le type booléen : sert à représenter les valeurs de vérités. Un booléen n'a que deux valeurs possibles, vrai ou faux.
Le type chaîne : sert à représenter les chaînes de caractères (données textuelles).

La liste n'est pas un type, mais une structure de données permettant de contenir d'autres éléments et d'y accéder par leurs indices. Les variables de type entier peuvent être composées à l'aide des opérations arithmétiques classique : l'addition $+$, la soustraction $-$, la multiplication $\times$, la puissance ^, la division entière $\frac{.}{.}$, le reste par la division euclidienne %, ... L'algorithme simple suivant calcule le n-ème nombre de Fermat : Entrée : entier n Variables : entier s s← 2^{2^n}+1 Sortie : s Les variables de type flottant servant à représenter les nombres réels peuvent être composées à l'aide des opérations arithmétiques classique : l'addition $+$, la soustraction $-$, la multiplication $\times$, la puissance ^, la division, $\frac{.}{.}$, ainsi que l'ensemble des opérations classiques $sin (.)$, $cos (.)$, $exp (.)$, $|.|$, ... L'algorithme simple suivant calcule la moyenne entre deux nombres réels : Entrées : entier a, entier b Variables : entier s s← (a+b)/2 Sortie : s Les variables de type booléen servent à représenter les valeurs de vérité. Il n'existe que deux booléens, vrai et faux. Ils peuvent être composés à l'aide des fonctions logiques classiques et, ou et non. L'algorithme simple suivant calcule le résultat d'une fonction NOR à partir de deux booléens : Entrées : booléen x, booléen y Variables : booléen s s← non ( x ou y ) Sortie : s Les fonctions de test <, >, ≤, ≥, =, ≠ renvoient des valeurs booléennes. On considère différentes affectations :

a ← (3 > 1)
b ← (2 ≠ 1)
c ← (vrai = faux)
d ← ((4,5 = 4)=faux)

Les valeurs des variables sont :

a prend la valeur vrai
b prend la valeur vrai
c prend la valeur faux
d prend la valeur vrai

Les variables de type chaîne servent à représenter les valeurs textuelles. Le nombre de chaînes de caractères est potentiellement infini et composé des symboles d'écriture utilisé universellement. Les chaînes de caractères sont représentées par un ensemble de caractères placés entre guillemets "" : "pS4µ�®DĥS#.?;Ɩ U+仮0196❿ DطF°MĊ_A仮¨Xjd4Ƃs%¶%&c"

Si la variable c est de type chaîne, on note c[i] son i-ème caractère.
On note "" la chaîne vide qui ne contient aucun caractère.

Les fonctions classiques sur les chaînes de caractère sont :

La fonction longueur qui renvoit sous la forme d'un entier, la longueur de la chaîne donnée
La fonction de concaténation notée +, qui concatène deux chaînes

On se donne deux variables de type chaîne a←"Bonjour" et b←"Hello" :

a[0] vaut "B" et b[4] vaut "o"
a+b vaut "BonjourHello"
longueur (a) vaut 7 et longueur ("") vaut 0
longueur ("a") vaut 1

Il est généralement pratique de pouvoir regrouper en une seule variable, un certain nombre de valeurs. C'est à ça que servent les listes. La liste des 10 premiers chiffres de l'écriture décimales de \pi sont affectées à la variable L : L ← [3,1,4,1,5,9,2,6,5,3] La fonction longueur existe aussi pour les listes, les accés aux éléments se font comme pour mes chaînes de caractères :

longueur (L) vaut 10
L[0] vaut 3, et L[9] vaut 3 aussi.

[] est la liste vide ne contenant aucun élément. Il est possible que les éléments d'une liste soient d'autres types, voire même qu'ils soient eux-mêmes des listes/ L'on souhaite représenter le damier ci-dessous à l'aide d'une structure de données :

Chaque ligne sera représentée par une liste de 4 nombres entiers où 1 signifie qu'il y a un pion et 0 signifie qu'il n'y a rien. Il y aura donc 4 lignes regroupées dans une seule variable qui est une liste de liste : D ← [ [0, 0, 0, 1], [0, 1, 0, 0], [0, 0, 1, 0], [0, 0, 1, 0] ]

D[0] vaut [0,0,0,1]
D[3][2] vaut 1

Les instructions que nous venons de voir sont séquentielles, c’est à dire qu’elles s’exécutent dans l’ordre dans lequel elles sont écrites. Il est évident qu’il faut disposer de nouvelles instructions capables de rompre cette rigidité pour que l’algorithme puisse s'adapter à la situation rencontrée. Ces instructions sont le si ... alors et le si ... alors ... sinon. On suppose une condition condition_1 qui peut être vraie ou fausse, et une instruction instruction_1 dans l'algorithme suivant : si condition_1 alors instruction_1 fin si Si la condition condition_1 est vraie, alors l'instruction instruction_1 est exécutée. Sinon, l'instruction est ignorée. On suppose une autre instruction instruction_2 dans l'algorithme suivant : si condition_1 alors instruction_1 sinon instruction_2 fin si Si la condition condition_1 est vraie, alors l'instruction instruction_1 est exécutée, sinon, l'instruction instruction_2 est exécutée. Voici un algorithme qui retourne un message différent selon l'année entrée : Entrée : a Variables : s si a < 2014 alors s ← "C'est du passé !" sinon s ← "Aujourd'hui est le premier jour du reste de ta vie." fin si Sortie : s Voici un algorithme naïf de mot de passe : Entrée : login Variables : s si login ="admin" alors s ← "Bienvenue, prenez ce que vous voulez" sinon si login = "guest" alors s ← "Bienvenue, enlevez vos chaussures s'il vous plaît" sinon s ← "Sortez d'ici !" fin si Sortie : s Il existe deux connecteurs logiques, le et et le ou permettant de combiner des conditions logiques :

condition_1 et condition_2 est vrai si les les deux conditions sont vraies.
condition_1 ou condition_2 est vrai si une des deux conditions est vraie.

L'algorithme suivant vérifie si vous avez droit à la carte de réduction 12-25 ans de le SNCF : Entrée : a Variables : s si (a ≥ 11) et (a ≤ 25) alors s ← "Vous êtes éligible" sinon s ← "Vous n'êtes pas dans la bonne tranche d'âge" fin si Sortie : s Une autre structure importante est la boucle "pour" qui permet de répéter la même série d’instructions N fois (où N est un nombre entier donné), en faisant varier une variable d'itération. On suppose donnée une variable i et des instructions instructions (i) dans lesquelles la variable i apparaît. L'algorithme suivant répète ces instructions grâce à la boucle pour : Pour i de 1 à N instructions (i) fin pour Les instructions seront répétées N fois, à la différence que :

La 1ère fois, i vaut 1
La 2ème fois, i vaut 2
...
La Nème fois, i vaut N

Les algorithmes,correctement écrits effectuant des tâches répétitives utilisent généralement des boucles pour. Cet algorithme calcule la somme des nombres entiers allant de 1 à 100 : Variables : entier S, entier i Pour i de 1 à 100 S ← S+i fin pour Sortie : S Cet algorithme décale vers la droite tous les éléments d'une liste L de nombres entiers. Par exemple, si la liste d'entrée est [1,2,3,4], la liste de sortie sera [4, 1, 2, 3] : Variables : liste L, entier i, entier l, entier N N=longueur de L l=L[N-1] Pour i de 1 à N-1 L[i] ← L[i-1] fin pour L[0]=l Sortie : L La variable i qui est incrémentée (signifie "augmenter de 1") à chaque étape peut commencer et finir à n'importe quelle valeur, et même compter à rebour. Il existe un deuxième type de boucle plus puissant que la boucle "pour", la boucle "tant que" : On suppose données une condition condition et des instructions instructions. L'algorithme suivant répète ces instructions tant que la condition condition est vraie grâce à la boucle Tant que : Tant que condition instructions fin Tant que Cette boucle est plus puissante mais également plus "dangereuse" car, mal utilisée, elle donne lieu à des algorithme sans fin. Par exemple, l'algorithme suivant ne s'arrête jamais : Variables : entier i i ← 1 Tant que i ≥ 0 i ← i+1 fin Tant que Sortie : i La boucle Tant que est utilisée quand on ne sait pas à l'avance combien de fois il faut boucler (dans ce cas on utilise la boucle pour).

On appelle $elog (x)$ le logarithme entier du nombre $x$ ≤ 1 le nombre de fois qu'il faut le diviser par 2 pour obtenir un nombre inférieur strictement à 1. Par exemple, $elog (30000)=16$ car 30000 divisé par $2^{16}$ vaut 0,915...

Comme on ne sait d'avance combien de fois il faut diviser par 2, on utilise la boucle tant que :

Entrée : flottant x Variables : entier n Tant que x ≥ 1 x ← x/2 n ← n + 1 fin Tant que Sortie n

Il est en général nécessaire d'opérer un tri quand on traite un nombre important de données. On ne trouve une livre dans une bibliothèque que parce que celle-ci est triée. Il existe différentes manières de s'y prendre, donc différents algorithmes plus ou moins efficaces selons les cas. Un exemple d'algorithme de tri fonctionnant sur une liste de cubes s'imbriquant parfaitement les uns dans les autres. Cliquez ici

L'algorithme de tri par sélection déplace un élément d'une liste à la fois. On commence par chercher le plus petit de tous les objets, puis le placer en premier. Il faut alors répéter cet étape sur tous les élements restants, jusqu'à ce que la liste soit triée.

Dans cette stratégie, il faut donc arriver à faire plusieurs choses :

Repérer le plus petit élément
Le placer au début de la liste
Répéter sur une sous-partie de la liste qui n'est pas encore triée

Trions la liste $[52; 8; 90; 3; 5; 12]$ en utilisant l'algorithme par sélection : $$ [52; 8; 90; \textbf{3}; 5; 12]\\ [3; 8; 90; 52; \textbf{5}; 12]\\ [3; 5; 90; 52; \textbf{8}; 12]\\ [3; 5; 8; 52; 90; \textbf{12}]\\ [3; 5; 8; 12; 90; \textbf{52}]\\ [3; 5; 8; 12; 52; 90] $$ L'algorithme permettant de repérer l'indice du plus petit élément est le suivant : Entrée : liste L Variables : entier n, entier k, entier j n ← longueur de L k ← 0 pour j de 1 à n-1 si L[j]≤ L[k] alors k ← j fin si fin pour Sortie : k L'algorithme permettant de d'échanger le i-ème élément avec le k-ième : Entrée : liste L, entier i, entier k Variables : réel z z ← L[i] L[i] ← L[k] L[k] ← z L'algorithme de tri devra réutiliser ces deux algorithmes tout en le répétant pour chaque élément de la liste. Il faudra adapter le premier algorithme pour que une fois le plus petit élément placé en début de liste, le prochain plus petit élément soit cherché à partir du deuxième élement de la liste. De même à chaque étape. L'algorithme de tri par sélection s'écrit de la manière suivante : Entrée : liste L Variables : entier n, entier k, entier i, réel z n ← longueur de }L pour i de 1 à n-1 k ← i pour j de i+1 à n-1 si L[j]≤ L[k] alors k ← j fin si fin pour z ← L[i] L[i] ← L[k] L[k] ← z fin pour Sortie : L On s'apperçoit en triant toute liste que quand il reste deux éléments, une étape suffit à trier. On pourrait donc faire l'économie d'une itération en ne faisant aller la première boucle que jusqu'à n-2. Un exemple en vidéo de l'algorithme de tri par sélection : cliquez ici

L'algorithme de tri à bulles consiste à trier une liste en ne s'autorisant qu'à échanger deux éléments consécutifs. On fait alors l'économie de comparer un terme à tous les autres n fois à chaque étape.

Trions la liste $[15; 7; 2; 8; 16; 12]$ en utilisant l'algorithme de tri à bulles : $$ [\textbf{15}; \textbf{7}; 2; 8; 16; 12]\\ [7; \textbf{15}; \textbf{2}; 8; 16; 12]\\ [7; 2; \textbf{15}; \textbf{8}; 16; 12]\\ [7; 2; 8; \textbf{15}; \textbf{16}; 12]\\ [7; 2; 8; 15; \textbf{16}; \textbf{12}]\\ [7; 2; 8; 15; \textbf{12}; \textbf{16}]\\ [\textbf{7}; \textbf{2}; 8; 15; 12; 16]\\ [\textbf{2}; \textbf{7}; 8; 15; 12; 16]\\ [2; \textbf{7}; \textbf{8}; 15; 12; 16]\\ [2; 7; \textbf{8}; \textbf{15}; 12; 16]\\ [2; 7; 8; \textbf{15}; \textbf{12}; 16]\\ [2; 7; 8; 12; \textbf{15}; \textbf{16}]\\ \text{mais ce n'est pas fini !...} $$ Cet algorithme présente deux avantages forts : il est simple à mettre en oeuvre, et il est très efficace sur des listes présentant "peu de désordre". Son défaut majeur est que la seule manière de détecter que la liste est triée est de passer une dernière fois sans rien trier. L'algorithme de tri à bulles s'écrit de la manière suivante : Entrée : liste L Variables : entier n, entier i, booléen échange_effectué tant que échange_effectué = vrai échange_effectué ← faux pour i de 0 à n - 1 si L[i] > L[i + 1] z ← L[i] L[i] ← L[i+1] L[i+1] ← L[i] échange_effectué = vrai fin si fin pour fin tant que Sortie : L Un exemple en vidéo de l'algorithme de tri à bulles : cliquez ici

Il existe de nombreux algorithmes de tri basés sur des techniques plus ou moins complexes. Chacun présente des avantages et des incovénients. Il n'existe pas d'algorithme plus efficace que tous les autres dans tous les cas. Par exemple le tri à bulle triera très rapidement une liste avec quelques permutations, tandis que l'algorithme par sélection devra passer par la recherche de tous les éléments les plus petits et créer du désordre avant d'arriver à trier complètement.

Vous pouvez voir fonctionner en temps réel des algorithmes de tri différents sur cette page. Il est possible de tester leurs performances sur des listes aléatoires, presque déjà triées, inversées et avec des doublons. Vous constaterez qu'il n'y a pas de meilleur (mais le tri par sélection est toujours dernier) !