Algorithmique:
Le mot algorithme vient du nom de l’auteur persan Al-Khuwarizmi (né vers 780 - mort vers 850)
qui a écrit en langue arabe le plus ancien traité d’algèbre « abrégé de calcul par la complétion et la
simplification » dans lequel il décrivait des procédés de calcul à suivre étape par étape pour résoudre
des problèmes ramenés à des équations.
On définit parfois les algorithmes de la manière suivante : « un algorithme est une suite finie de règles
à appliquer dans un ordre déterminé à un nombre fini de données pour arriver, en un nombre fini
d’étapes, à un certain résultat et cela indépendamment des données ». Le résultat doit donc s’obtenir
en un temps fini.
Dans ce chapitre, nous allons nous intéresser à la notion de variable. Une variable est une sorte de
« boîte » dans laquelle on peut stocker une information (texte, nombre, liste de nombres, figure,. . .) ;
une variable est nommée (elle a un nom) par exemple MaVariable, a, Nombre1, . . . sont des noms de
variables. Dans un algorithme, « a ← b » signifie que le contenu de la « boîte » b vient se mettre à
la place du contenu de la « boîte » a. À noter que le contenu initial de b reste aussi dans b il est en
quelque sorte recopié dans a.
Le tri à bulles:
Cette partie provient largement d’une activité proposée sur le site internet de l’irem de Lille par
Jean-Marc Duquesnoy et Raymond Moché.
Le tri à bulles ou tri par propagation est un algorithme de tri qui consiste à faire remonter progressivement
les plus grands éléments d’une liste, comme les bulles d’air remontent à la surface d’un liquide.
L’algorithme parcourt la liste, et compare les couples d’éléments successifs. Lorsque deux éléments
successifs ne sont pas dans l’ordre croissant, ils sont échangés. Après chaque parcours complet de la
liste, l’algorithme recommence l’opération. Lorsqu’aucun échange n’a lieu pendant un parcours, cela
signifie que la liste est triée : l’algorithme peut s’arrêter.
1. Apparemment, on peut ranger deux nombres donnés a et b à l’aide de l’algorithme suivant :
En sortie, on demande d’afficher successivement les contenus des cases a et b.
Question - Pourquoi cet algorithme est-il incorrect ? Quel résultat donne-t-il ? (Prendre par
exemple au départ a = 5 et b = 3.)
2. Voici un algorithme correct pour ordonner a et b dans l’ordre croissant :
On voit que le problème est d’échanger le contenu des deux variables a et b.
Question - Donner une solution utilisant une variable auxiliaire c. La réponse sera donnée en
complétant le cadre vide de l’algorithme ci-dessous :
3. Complément : que fait l’algorithme suivant ? Quel est son avantage par rapport au
précédent ?
4. Qu’est-ce que le « tri à bulles » ?
Supposons que l’on ait à ordonner dans l’ordre croissant la liste
A = (5, 1, 4, 8, 2).
La manipulation de base du « tri à bulles » consiste à examiner successivement les couples formés
par les nombres de rang 1 et 2, puis par les nombres de rang 2 et 3 et ainsi de suite jusqu’à
la fin et de leur appliquer le traitement suivant :
Voici les transformations successives subies par A au cours de ce processus :
A = (5, 1, 4, 8, 2) → (1, 5, 4, 8, 2) → (1, 4, 5, 8, 2) → (1, 4, 5, 8, 2) → B = (1, 4, 5, 2, 8)
La liste B n’est pas ordonnée dans l’ordre croissant mais nous avons fait des progrès dans le
classement car le maximum de 5, 1, 4, 8, 2, qui est 8, se trouve maintenant à la fin de la liste,
qui est sa place définitive.
Cela conduit naturellement à appliquer à B la manipulation de base. Voici ce que cela donne
B = (1, 4, 5, 2, 8) → (1, 4, 5, 2, 8) → (1, 4, 5, 2, 8) → (1, 4, 2, 5, 8) → C = (1, 4, 2, 5, 8)
C’est mieux car les deux derniers termes sont maintenant à leurs places définitives. Recommençons
en appliquant la manipulation de base à C :
C = (1, 4, 2, 5, 8)→ (1, 4, 2, 5, 8) → (1, 2, 4, 5, 8) → (1, 2, 4, 5, 8)→ (1, 2, 4, 5, 8)
On voit que le rangement de A dans l’ordre croissant est terminé. Pour cela, on a dû appliquer
trois fois la manipulation de base.
Si on imagine maintenant que A est une liste quelconque de n >= 2 nombres quelconques, il est
clair qu’après une première application de la manipulation de base, le dernier terme du nouvel
état de A sera à sa place définitive ; après la seconde application de la manipulation de base, les
deux derniers termes seront à leurs places définitives, et ainsi de suite. Par conséquent, après la
(n−1)ème application de la manipulation de base, les (n−1) derniers termes - et par conséquent
le premier - seront à leurs places définitives, ce qui veut dire que le rangement sera terminé.
L’exemple A = (5, 1, 4, 8, 2) montre que, quelquefois, il n’y a pas besoin d’effectuer les (n−1)
applications de la manipulation de base.
Question : combien faut-il de manipulations de base pour ranger 5, 4, 3, 2, 1 dans l’ordre
croissant ?
5. Voici l’algorithme du « tri à bulles », en langage naturel :
Questions :
a. peut-on l’améliorer de sorte que le traitement aille plus vite ?
b. modifier cet algorithme pour que l’état initial de la liste A soit conservé et affiché en même
temps que le résultat
Le mot algorithme vient du nom de l’auteur persan Al-Khuwarizmi (né vers 780 - mort vers 850)
qui a écrit en langue arabe le plus ancien traité d’algèbre « abrégé de calcul par la complétion et la
simplification » dans lequel il décrivait des procédés de calcul à suivre étape par étape pour résoudre
des problèmes ramenés à des équations.
On définit parfois les algorithmes de la manière suivante : « un algorithme est une suite finie de règles
à appliquer dans un ordre déterminé à un nombre fini de données pour arriver, en un nombre fini
d’étapes, à un certain résultat et cela indépendamment des données ». Le résultat doit donc s’obtenir
en un temps fini.
Dans ce chapitre, nous allons nous intéresser à la notion de variable. Une variable est une sorte de
« boîte » dans laquelle on peut stocker une information (texte, nombre, liste de nombres, figure,. . .) ;
une variable est nommée (elle a un nom) par exemple MaVariable, a, Nombre1, . . . sont des noms de
variables. Dans un algorithme, « a ← b » signifie que le contenu de la « boîte » b vient se mettre à
la place du contenu de la « boîte » a. À noter que le contenu initial de b reste aussi dans b il est en
quelque sorte recopié dans a.
Le tri à bulles:
Cette partie provient largement d’une activité proposée sur le site internet de l’irem de Lille par
Jean-Marc Duquesnoy et Raymond Moché.
Le tri à bulles ou tri par propagation est un algorithme de tri qui consiste à faire remonter progressivement
les plus grands éléments d’une liste, comme les bulles d’air remontent à la surface d’un liquide.
L’algorithme parcourt la liste, et compare les couples d’éléments successifs. Lorsque deux éléments
successifs ne sont pas dans l’ordre croissant, ils sont échangés. Après chaque parcours complet de la
liste, l’algorithme recommence l’opération. Lorsqu’aucun échange n’a lieu pendant un parcours, cela
signifie que la liste est triée : l’algorithme peut s’arrêter.
1. Apparemment, on peut ranger deux nombres donnés a et b à l’aide de l’algorithme suivant :
Question - Pourquoi cet algorithme est-il incorrect ? Quel résultat donne-t-il ? (Prendre par
exemple au départ a = 5 et b = 3.)
2. Voici un algorithme correct pour ordonner a et b dans l’ordre croissant :
On voit que le problème est d’échanger le contenu des deux variables a et b.
Question - Donner une solution utilisant une variable auxiliaire c. La réponse sera donnée en
complétant le cadre vide de l’algorithme ci-dessous :
3. Complément : que fait l’algorithme suivant ? Quel est son avantage par rapport au
précédent ?
4. Qu’est-ce que le « tri à bulles » ?
Supposons que l’on ait à ordonner dans l’ordre croissant la liste
A = (5, 1, 4, 8, 2).
La manipulation de base du « tri à bulles » consiste à examiner successivement les couples formés
par les nombres de rang 1 et 2, puis par les nombres de rang 2 et 3 et ainsi de suite jusqu’à
la fin et de leur appliquer le traitement suivant :
Voici les transformations successives subies par A au cours de ce processus :
A = (5, 1, 4, 8, 2) → (1, 5, 4, 8, 2) → (1, 4, 5, 8, 2) → (1, 4, 5, 8, 2) → B = (1, 4, 5, 2, 8)
La liste B n’est pas ordonnée dans l’ordre croissant mais nous avons fait des progrès dans le
classement car le maximum de 5, 1, 4, 8, 2, qui est 8, se trouve maintenant à la fin de la liste,
qui est sa place définitive.
Cela conduit naturellement à appliquer à B la manipulation de base. Voici ce que cela donne
B = (1, 4, 5, 2, 8) → (1, 4, 5, 2, 8) → (1, 4, 5, 2, 8) → (1, 4, 2, 5, 8) → C = (1, 4, 2, 5, 8)
C’est mieux car les deux derniers termes sont maintenant à leurs places définitives. Recommençons
en appliquant la manipulation de base à C :
C = (1, 4, 2, 5, 8)→ (1, 4, 2, 5, 8) → (1, 2, 4, 5, 8) → (1, 2, 4, 5, 8)→ (1, 2, 4, 5, 8)
On voit que le rangement de A dans l’ordre croissant est terminé. Pour cela, on a dû appliquer
trois fois la manipulation de base.
Si on imagine maintenant que A est une liste quelconque de n >= 2 nombres quelconques, il est
clair qu’après une première application de la manipulation de base, le dernier terme du nouvel
état de A sera à sa place définitive ; après la seconde application de la manipulation de base, les
deux derniers termes seront à leurs places définitives, et ainsi de suite. Par conséquent, après la
(n−1)ème application de la manipulation de base, les (n−1) derniers termes - et par conséquent
le premier - seront à leurs places définitives, ce qui veut dire que le rangement sera terminé.
L’exemple A = (5, 1, 4, 8, 2) montre que, quelquefois, il n’y a pas besoin d’effectuer les (n−1)
applications de la manipulation de base.
Question : combien faut-il de manipulations de base pour ranger 5, 4, 3, 2, 1 dans l’ordre
croissant ?
a. peut-on l’améliorer de sorte que le traitement aille plus vite ?
b. modifier cet algorithme pour que l’état initial de la liste A soit conservé et affiché en même
temps que le résultat
Tags
algorithme