Question transversaleMathsNSIAlgorithmes et complexité

Peut-on inventer un algorithme de tri encore plus rapide, ou existe-t-il une limite infranchissable ?

Un tri par comparaisons doit distinguer les n! ordres possibles ; chaque comparaison ne fait que diviser les possibilités par 2 au mieux, il en faut donc au moins log₂(n!). Pour 4 nombres, 24 ordres demandent 5 comparaisons ; pour 10, 22. Et log₂(n!) est de l'ordre de n log₂ n.

Grand oral session 2027 : exposé de 10 minutes debout, puis 10 minutes d'échange, sans calculatrice. Plan prévu pour 9,5 min.

Pourquoi cette question : un modèle d'introduction

Le jury attend que vous expliquiez pourquoi vous avez choisi la question. Inspirez-vous de ce modèle, mais racontez votre propre parcours.

Après avoir découvert le tri fusion, je me suis demandé s'il existait un tri encore plus rapide, et pourquoi les informaticiens n'en avaient pas trouvé. J'ai appris qu'on pouvait démontrer qu'aucun tri par comparaisons ne fait mieux qu'un certain nombre d'étapes. Démontrer qu'un algorithme n'existe pas m'a semblé fascinant.

L'enjeu et les notions du programme

Utiliser le dénombrement des permutations et le logarithme pour démontrer une borne inférieure valable pour tous les algorithmes.

Mathématiques

Permutations, factorielle (terminale)
Logarithme, propriétés algébriques (terminale)
Raisonnement par l'absurde, majoration (seconde, terminale)

Numérique et sciences informatiques

Algorithmes de tri, coût (première)
Arbres binaires : hauteur et nombre de feuilles (terminale)

Le plan de l'exposé en 9,5 min

1. Introduction
1 min
Le tri fusion coûte environ $n lo g_{2} n$ nlog₂n comparaisons. Problématique : est-ce un record provisoire, ou peut-on démontrer qu'on ne fera jamais mieux en comparant les éléments deux à deux ?
2. Mathématiques : compter les ordres possibles
4 min
Une liste de $n$ n nombres distincts peut se présenter dans $n!$ n! ordres. Pour la trier, l'algorithme doit identifier l'ordre initial parmi ces $n!$ n! possibilités.
Chaque comparaison « $a < b$ a<b ? » a deux réponses. Après $k$ k comparaisons, l'algorithme a distingué au plus $2^{k}$ 2^(k) situations. Il faut donc $2^{k} \geq n!$ 2^(k)≥ n!, c'est-à-dire $k \geq lo g_{2} (n!)$ k≥log₂(n!).
Pour $n = 4$ n=4 : $4! = 24$ 4!=24 et $2^{4} = 16 < 24 \leq 32 = 2^{5}$ 2⁴=16<24≤32=2⁵, donc au moins 5 comparaisons dans le pire cas. Pour $n = 10$ n=10 : $lo g_{2} (10!) \approx 21, 8$ log₂(10!)≈21,8, au moins 22.
Ordre de grandeur : $lo g_{2} (n!) = lo g_{2} 1 + lo g_{2} 2 + \dots + lo g_{2} n$ log₂(n!)=log₂ 1+log₂ 2+…+log₂ n. La moitié des termes, de $\frac{n}{2}$ n/2 à $n$ n, valent au moins $lo g_{2} \frac{n}{2}$ log₂n/2, donc $lo g_{2} (n!) \geq \frac{n}{2} lo g_{2} \frac{n}{2}$ log₂(n!)geqn/2log₂n/2. Et chaque terme est au plus $lo g_{2} n$ log₂n, donc $lo g_{2} (n!) \leq n lo g_{2} n$ log₂(n!)≤ nlog₂n. La borne est bien de l'ordre de $n lo g_{2} n$ nlog₂n : le tri fusion est optimal à une constante près.
3. NSI : l'arbre de décision
3 min
On représente tout algorithme de tri par comparaisons par un arbre binaire : chaque nœud est une comparaison, chaque feuille un ordre final. L'arbre doit avoir au moins $n!$ n! feuilles ; or un arbre binaire de hauteur $h$ h a au plus $2^{h}$ 2^(h) feuilles. La hauteur, c'est-à-dire le nombre de comparaisons dans le pire cas, vérifie $h \geq lo g_{2} (n!)$ h≥log₂(n!).
Cette borne ne vaut que pour les tris qui comparent. Si l'on sait que les valeurs sont des entiers entre 0 et 100, le tri par comptage compte les occurrences de chaque valeur sans comparer : il est linéaire. La borne n'est pas contournée, ses hypothèses ne s'appliquent plus.
4. Conclusion
1,5 min
Aucun tri par comparaisons ne peut faire mieux que $lo g_{2} (n!)$ log₂(n!), de l'ordre de $n lo g_{2} n$ nlog₂n : c'est une limite démontrée, pas un record. Le tri fusion l'atteint. J'ouvre sur les grandes questions ouvertes de complexité, comme P = NP, où l'on ne sait pas démontrer de telles bornes.

Ce que j'écris au tableau

Pas de calculatrice ni de support numérique : un calcul clé écrit au tableau rend l'exposé concret et montre la solidité des connaissances.

2^{k} \geq n! ⟺ k \geq lo g_{2} (n!) n = 4 : 16 < 24 \leq 32 \Rightarrow k \geq 5 2^(k)\geq n!\Leftrightarrow k\geqlog₂(n!) n=4: 16<24\leq32\Rightarrow k\geq5 \frac{n}{2} lo g_{2} \frac{n}{2} \leq lo g_{2} (n!) \leq n lo g_{2} n n/2log₂n/2\leqlog₂(n!)\leq nlog₂n

Conclusion : la réponse à la question

On peut démontrer l'impossibilité : tout tri par comparaisons demande au moins $lo g_{2} (n!)$ log₂(n!) comparaisons. Le dénombrement des permutations fixe une limite que toute l'ingéniosité du monde ne franchira pas.

Les questions probables du jury

Pendant les 10 minutesd'échange, le jury vous fait préciser et approfondir, sur tout le programme de vos spécialités en lien avec la question.

Pourquoi 2^k situations au plus après k comparaisons ?

Chaque comparaison a deux issues ; par le principe multiplicatif, k comparaisons en ont au plus 2^k.

Combien de comparaisons au minimum pour trier 3 nombres ?

$3! = 6$ 3!=6, $2^{2} = 4 < 6 \leq 8$ 2²=4<6≤8 : 3 comparaisons.

Le tri par comptage contredit-il la borne ?

Non : il ne compare pas les éléments et utilise une information supplémentaire (les valeurs sont des petits entiers).

Rappelez la propriété ln(ab) = ln a + ln b. À quoi sert-elle ici ?

À écrire $lo g_{2} (n!)$ log₂(n!) comme une somme de logarithmes, plus facile à encadrer.

Combien de feuilles a au plus un arbre binaire de hauteur h ?

$2^{h}$ 2^(h) : le nombre de nœuds double au plus à chaque niveau.

Les pièges qui coûtent des points

Croire que la borne s'applique à tous les tris, y compris ceux qui ne comparent pas.
Oublier l'arrondi à l'entier supérieur du logarithme.
Confondre borne inférieure (au moins) et coût d'un algorithme particulier.

Revoir les notions

Autres questions : algorithmes et complexité

Toutes les questions maths-nsi →

Préparer l'oral, pas seulement le contenu

Gestion des 20 minutes de préparation, usage du tableau, posture debout, réponses au jury : la méthode complète, conforme aux règles de la session 2027.

Méthode : traiter une question de Grand oral →

Continuer la préparation

Le Grand oral 2027 →Méthode : traiter une question →Toutes les questions, par combinaison →Questions de maths seules →Questions maths-physique-chimie →Questions maths-SES →Questions maths-SVT →Questions maths-SI →Questions maths-HGGSP →Questions maths-anglais →