#AlgorithmesCopier le lien

Définition, propriétés et exemples d'algorithmes classiques, avec leur déroulé pas à pas et leurs coûts.

#PrérequisCopier le lien

Savoir lire une boucle et une comparaison en Python. Les pages décomposition (invariants) et complexité (coûts) complètent ce chapitre.

#Objectifs d'apprentissageCopier le lien

• Énoncer les propriétés qu'une suite d'instructions doit satisfaire pour mériter le nom d'algorithme.
• Dérouler à la main une recherche linéaire, une recherche dichotomique, un tri à bulles et un tri rapide.
• Établir la correction d'une boucle par son invariant et sa condition de sortie.
• Prouver la terminaison d'un algorithme récursif par une mesure bien fondée.
• Borner une structure définie inductivement par induction structurelle.
• Connaître le coût au pire cas de chaque algorithme présenté, et savoir le démontrer par sa récurrence.

#Qu'est-ce qu'un algorithme ?Copier le lien

Un algorithme est une séquence finie d'instructions précises et non ambiguës qui, à partir d'entrées, produit une sortie en un nombre fini d'étapes. La recette de cuisine en est l'analogue quotidien : ingrédients (entrées), étapes ordonnées, plat (sortie). La différence : une recette tolère « une pincée de sel », un algorithme non.

#PropriétésCopier le lien

• Finitude : l'exécution se termine en un nombre fini d'étapes, pour toute entrée licite.
• Précision : chaque instruction est claire et non ambiguë ; deux exécutions avec la même entrée font la même chose.
• Entrées : zéro ou plusieurs valeurs, avec leurs domaines.
• Sorties : une ou plusieurs valeurs, liées aux entrées par la spécification.
• Faisabilité : chaque instruction est réalisable en temps fini par l'exécutant (humain ou machine).

La correction d'un algorithme se prouve par la conjonction de deux propriétés : la terminaison (on finit par sortir de chaque boucle) et la validation partielle (si on sort, la sortie satisfait la spécification). L'outil central est l'invariant de boucle, présenté dans décomposition.

#Terminaison : la mesure bien fondéeCopier le lien

Pour un algorithme itératif, la terminaison se prouve en exhibant une quantité entière positive qui décroît strictement à chaque tour : elle ne peut décroître indéfiniment, donc la boucle s'arrête. Pour un algorithme récursif, la même idée s'énonce sur les appels : il faut une mesure qui décroît strictement d'un appel à ses sous-appels.

Le cadre général est celui des ensembles bien fondés. Un ordre est bien fondé s'il n'existe pas de suite infinie strictement décroissante ; un ensemble muni d'un bon ordre est dit inductif. Deux faits du cours en découlent :

• un ensemble ordonné $(E, \le)$ est bien fondé si et seulement si toute partie non vide de $E$ admet au moins un élément minimal ;
• sur un ensemble bien fondé, le principe d'induction généralisé s'applique : si pour tout $x$, $(\forall y \lt x,\ P(y)) \Rightarrow P(x)$, alors $P(x)$ est vraie partout.

C'est ce principe qui légitime l'induction structurelle sur un ensemble défini inductivement (arbres, listes, expressions bien formées) : il suffit de vérifier la propriété sur la base et de montrer que les opérations de construction la préservent.

#Induction sur les entrées : un exempleCopier le lien

L'induction structurelle sert à la fois à prouver la correction d'un algorithme récursif et à borner les structures qu'il manipule. Prenons les arbres binaires, définis inductivement par $\emptyset \in AB$ et « si $g, d \in AB$ alors $(\cdot, g, d) \in AB$ ». Notons $h$ la hauteur, $n$ le nombre de nœuds et $f$ le nombre de feuilles. On montre par induction structurelle que

$n(x) \le 2^{h(x)} - 1 \qquad \text{et} \qquad f(x) \le 2^{h(x)-1}.$

L'étape décisive consiste à écrire $n(x) = 1 + n(g) + n(d)$, à appliquer l'hypothèse d'induction aux deux sous-arbres, puis à utiliser $h(g), h(d) \le h(x) - 1$. Les deux bornes sont atteintes par l'arbre parfait, donc elles sont optimales.

Conséquence directe. La première inégalité se réécrit $h(x) \ge \log_2(n+1)$ : un arbre à $n$ nœuds ne peut pas être plus plat que logarithmique. C'est la justification rigoureuse de la promesse « recherche en $O(\log n)$ sur un arbre équilibré » — et l'explication de son effondrement quand l'arbre dégénère en liste, cas où $h = n$ et la recherche redevient linéaire. La démonstration complète figure dans les annales corrigées.

#Recherche linéaireCopier le lien

Le plus simple des algorithmes de recherche : parcourir le tableau élément par élément jusqu'à trouver la valeur.

Principe :

1. Commencer au premier élément.
2. Comparer l'élément courant avec la valeur cherchée.
3. Si trouvé, retourner l'index.
4. Sinon, passer à l'élément suivant.
5. Répéter jusqu'à la fin du tableau ; si la fin est atteinte, retourner une valeur sentinelle (par exemple -1).

1def recherche_lineaire(tableau, element):2    for i in range(len(tableau)):3        if tableau[i] == element:4            return i5    return -16 7t = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]8print(recherche_lineaire(t, 23))   # 59print(recherche_lineaire(t, 100))  # -1

Sorties :

152-1

Invariant : au début de l'itération i, l'élément cherché n'apparaît pas dans tableau[:i]. À la sortie, soit on l'a trouvé, soit il est absent de tout le tableau.

Coût : O(n) au pire cas (l'élément est en dernière position, ou absent). Aucune hypothèse sur les données : le tableau n'a pas besoin d'être trié.

#Recherche dichotomiqueCopier le lien

La dichotomie exige un tableau trié et exploite cet ordre : à chaque comparaison, elle élimine la moitié de l'espace de recherche.

Principe :

1. Déterminer les bornes gauche et droite de l'espace de recherche.
2. Calculer l'indice du milieu.
3. Comparer l'élément du milieu avec la valeur cherchée.
4. Si égal, retourner l'index.
5. Si la valeur cherchée est plus grande, chercher dans la moitié droite.
6. Si elle est plus petite, chercher dans la moitié gauche.
7. Répéter jusqu'à trouver ou épuiser l'espace.

1def recherche_dichotomique(tableau, element):2    gauche, droite = 0, len(tableau) - 13    while gauche <= droite:4        milieu = (gauche + droite) // 25        if tableau[milieu] == element:6            return milieu7        elif tableau[milieu] < element:8            gauche = milieu + 19        else:10            droite = milieu - 111    return -112 13t = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]14print(recherche_dichotomique(t, 23))   # 5

Sorties :

152-1

#Déroulé pas à pasCopier le lien

Cherchons 23 dans ce tableau trié de 10 éléments. À chaque tour, la fenêtre [gauche, droite] se resserre :

1tour 1 : gauche=0 droite=9 milieu=4  t[4]=16 < 23 → chercher à droite2tour 2 : gauche=5 droite=9 milieu=7  t[7]=56 > 23 → chercher à gauche3tour 3 : gauche=5 droite=6 milieu=5  t[5]=23     → trouvé, index 5

Trois comparaisons, contre six pour la recherche linéaire. Cherchons maintenant 24, absent du tableau :

1tour 1 : gauche=0 droite=9 milieu=4  t[4]=16 < 24 → droite de 162tour 2 : gauche=5 droite=9 milieu=7  t[7]=56 > 24 → gauche de 563tour 3 : gauche=5 droite=6 milieu=5  t[5]=23 < 24 → droite de 234tour 4 : gauche=6 droite=6 milieu=6  t[6]=38 > 24 → gauche=7 > droite=6 → sortie, -1

Terminaison : à chaque itération, soit on sort (trouvé), soit la largeur droite - gauche diminue strictement (la fenêtre perd au moins l'élément du milieu). Une quantité entière positive strictement décroissante atteint forcément zéro : la boucle se termine.

Invariant : si l'élément est présent dans le tableau, il est dans tableau[gauche..droite]. Chaque itération préserve cette propriété parce que le tableau est trié.

Coût : O(log n). L'espace de recherche est divisé par 2 à chaque tour : avec 1 024 éléments, au plus 10 comparaisons (car $2^{10} = 1024$) ; avec un million d'éléments, au plus 20.

#Tri à bullesCopier le lien

Le tri à bulles compare chaque paire d'éléments adjacents et les échange si elles sont mal ordonnées. À chaque passage complet, le plus grand élément restant « remonte » comme une bulle vers sa position finale à droite.

Principe :

1. Parcourir le tableau de gauche à droite.
2. Comparer chaque paire d'éléments adjacents.
3. Échanger si la paire est mal ordonnée.
4. Répéter ; à chaque passage, l'élément le plus grand de la zone non triée atteint sa place définitive.

1def tri_bulles(t):2    n = len(t)3    for i in range(n - 1):4        for j in range(n - 1 - i):5            if t[j] > t[j + 1]:6                t[j], t[j + 1] = t[j + 1], t[j]7    return t8 9print(tri_bulles([5, 1, 4, 2, 8]))

Sortie :

1[1, 2, 4, 5, 8]

#Déroulé pas à pas sur [5, 1, 4, 2, 8]Copier le lien

1passage 1 : [5,1,4,2,8] → [1,5,4,2,8] → [1,4,5,2,8] → [1,4,2,5,8] → [1,4,2,5,8]2             (3 échanges ; le 8 est en place)3passage 2 : [1,4,2,5,8] → [1,2,4,5,8]4             (1 échange ; le 5 est en place)5passage 3 : [1,2,4,5,8]6             (0 échange ; tableau trié)

Invariant : au début du passage i, les i plus grands éléments du tableau initial occupent leurs positions finales dans t[n-i:].

Coût : O(n²) au pire cas et en moyenne (deux boucles imbriquées parcourant chacune O(n)). Sur une entrée déjà triée avec la variante qui s'arrête dès qu'un passage ne fait aucun échange, le coût tombe à O(n) : c'est le seul cas où le tri à bulles est raisonnable. En pratique, on lui préfère sorted ou list.sort() (Timsort, O(n log n) garanti et O(n) sur les données presque triées).

#Tri rapide (quicksort)Copier le lien

Le tri rapide suit la stratégie « diviser pour régner » : choisir un pivot, répartir les éléments autour de lui (partition), puis trier récursivement chaque côté.

Principe :

1. Choisir un élément pivot (dernier élément, ici).
2. Partitionner : réorganiser le tableau pour que tout élément plus petit que le pivot soit à sa gauche, tout élément plus grand à sa droite.
3. Le pivot est alors à sa position définitive.
4. Appliquer récursivement aux deux sous-tableaux.

1def partition(t, gauche, droite):2    pivot = t[droite]3    i = gauche - 14    for j in range(gauche, droite):5        if t[j] < pivot:6            i += 17            t[i], t[j] = t[j], t[i]8    t[i + 1], t[droite] = t[droite], t[i + 1]9    return i + 110 11def tri_rapide(t, gauche=0, droite=None):12    if droite is None:13        droite = len(t) - 114    if gauche < droite:

Sortie :

1[1, 2, 3, 4, 5, 8]

#Déroulé de la partition sur [3, 8, 2, 5, 1, 4], pivot = 4Copier le lien

1départ    : [3, 8, 2, 5, 1 | 4]   i = -12j=0 : 3 < 4 → i=0, échange t[0],t[0] → [3, 8, 2, 5, 1 | 4]3j=1 : 8 ≥ 4 → rien4j=2 : 2 < 4 → i=1, échange t[1],t[2] → [3, 2, 8, 5, 1 | 4]5j=3 : 5 ≥ 4 → rien6j=4 : 1 < 4 → i=2, échange t[2],t[4] → [3, 2, 1, 5, 8 | 4]7fin  : échange t[3],t[5] → [3, 2, 1, 4, 8, 5]   pivot à l'indice 3

Invariant de la partition : pendant la boucle sur j, t[gauche..i] ne contient que des éléments plus petits que le pivot, et t[i+1..j-1] que des éléments plus grands ou égaux. À la sortie, le pivot est à sa place définitive.

Coût : la partition est O(n). Si le pivot coupe à peu près en deux, la récursion a une profondeur O(log n) et le total est O(n log n) en moyenne. Si le pivot est systématiquement le plus petit (tableau déjà trié avec pivot au bout), chaque partition ne retire qu'un élément : la profondeur devient O(n) et le total O(n²) au pire cas. C'est pourquoi les implémentations sérieuses choisissent le pivot aléatoirement ou en médiane de trois.

#Pourquoi le pire cas est quadratiqueCopier le lien

L'affirmation précédente se démontre. Notons $c(n)$ le nombre de comparaisons au pire cas pour trier $n$ éléments. La partition coûte $n+1$ comparaisons, puis la récursion repart sur $n-1$ éléments :

$c(2) = 3, \qquad c(n) = c(n-1) + n + 1 \ \text{pour } n \gt 2.$

La méthode de sommation (écrire la relation aux rangs successifs et additionner membre à membre) donne

$c(n) = c(2) + \sum_{k=4}^{n+1} k = 3 + \frac{(n+1)(n+2)}{2} - 6 = \frac{n^2 + 3n - 4}{2}.$

Vérification : $c(3) = 3 + 4 = 7$ et $(9 + 9 - 4)/2 = 7$ ; $c(4) = 7 + 5 = 12$ et $(16 + 12 - 4)/2 = 12$.

Le résultat est un polynôme de degré 2 : le tri rapide est $\Theta(n^2)$ dans le pire cas, alors qu'il est $O(n \log n)$ en moyenne. La résolution complète et le pseudo-code du cours figurent dans les annales corrigées.

#Tableau récapitulatifCopier le lien

#ExercicesCopier le lien

1. Déroulez à la main la recherche dichotomique de 72 dans t = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91] en notant gauche, milieu, droite à chaque tour.
2. Combien de comparaisons au plus la dichotomique fait-elle dans un tableau d'un million d'éléments ? Et dans un tableau de 16 éléments ?
3. Déroulez la partition de Lomuto sur [7, 2, 9, 4, 3] avec le dernier élément comme pivot, en notant l'état du tableau après chaque échange.
4. Énoncez l'invariant de boucle de la recherche linéaire et prouvez qu'il est préservé à chaque itération.