Pourquoi couper un problème en deux permet-il de le résoudre beaucoup plus vite ?

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.

J'ai été frappé en NSI par l'idée du tri fusion : au lieu de trier une liste, on trie deux listes deux fois plus petites, puis on les fusionne. Cela semblait reporter le problème plutôt que le résoudre. Pourtant, ce tri est bien plus rapide. Je voulais comprendre pourquoi, et la réponse est une suite définie par récurrence que l'on peut résoudre exactement.

L'enjeu et les notions du programme

Traduire un algorithme récursif en une relation de récurrence, la résoudre et la démontrer par récurrence.

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

1. 1. Introduction

   1 min

   La méthode « diviser pour régner » découpe un problème en sous-problèmes plus petits, les résout récursivement, puis combine les résultats. Problématique : comment calculer le coût d'une telle méthode, et pourquoi est-il si faible ?

2. 2. Mathématiques : résoudre la récurrence

   4 min

   Notons $C(n)$C(n) le nombre d'opérations pour trier $n$n éléments. Trier deux moitiés coûte $2C\left(\frac{n}{2}\right)$2C (n/2), les fusionner coûte au plus $n$n. D'où $C(n)=2C\left(\frac{n}{2}\right)+n$C(n)=2C (n/2)+n et $C(1)=0$C(1)=0.

   On pose $n=2^k$n=2^(k) et $u_k=C(2^k)$uₖ=C(2^(k)) : $u_k=2u_{k-1}+2^k$uₖ=2uₖ₋₁+2^(k). En divisant par $2^k$2^(k) : $\frac{u_k}{2^k}=\frac{u_{k-1}}{2^{k-1}}+1$uₖ/2^(k)=uₖ₋₁/(2^(k-1))+1. La suite $v_k=\frac{u_k}{2^k}$vₖ=uₖ/2^(k) est arithmétique de raison 1 et $v_0=0$v₀=0, donc $v_k=k$vₖ=k et $u_k=k{2}^k$uₖ=k 2^(k).

   Conclusion : $C(n)=n{\log }_{2}n$C(n)=nlog₂ n. Démonstration par récurrence : vrai pour $k=0$k=0 ; si $u_{k-1}=(k-1)2^{k-1}$uₖ₋₁=(k-1)2^(k-1), alors $u_k=2(k-1)2^{k-1}+2^k=k{2}^k$uₖ=2(k-1)2^(k-1)+2^(k)=k 2^(k).

   Pour $n=1024=2^{10}$n=1 024=2¹⁰ : $C=10240$C=10 240, contre $\frac{1024\times 1023}{2}=523776$1024×1023/2=523 776 pour le tri par sélection, cinquante fois plus.

3. 3. NSI : programmer la fusion

   3 min

   La fonction fusion parcourt deux listes triées avec deux indices et place à chaque étape le plus petit des deux éléments en tête : au plus $n$n comparaisons. La fonction tri_fusion s'appelle elle-même sur les deux moitiés, avec pour cas de base une liste de longueur 0 ou 1.

   Le gain vient de ce que la fusion de deux listes triées est linéaire, alors que trier directement est quadratique. Le prix à payer est une mémoire supplémentaire pour les listes intermédiaires. La même méthode accélère la recherche dichotomique, l'exponentiation rapide ou la multiplication de grands nombres.

4. 4. Conclusion

   1,5 min

   Couper en deux fonctionne parce que les sous-problèmes sont beaucoup moins chers que le problème entier et que la recombinaison est linéaire : la récurrence $C(n)=2C(n/2)+n$C(n)=2C(n/2)+n donne $n{\log }_{2}n$nlog₂n. J'ouvre sur les cas où le découpage ne paie pas, quand la recombinaison coûte trop cher.

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.

Conclusion : la réponse à la question

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.

Les pièges qui coûtent des points

• Oublier le coût de la fusion dans la récurrence.
• Confondre log₂ n niveaux et n niveaux.
• Présenter la formule sans la démontrer.

Revoir les notions

• Suites : récurrence et limites (Terminale spé maths) →
• Suites arithmétiques et géométriques (Première spé maths) →

Autres questions : algorithmes et complexité

• Pourquoi trier un million de nombres peut-il prendre dix minutes ou un centième de seconde selon l'algorithme ?
• Peut-on inventer un algorithme de tri encore plus rapide, ou existe-t-il une limite infranchissable ?
• Un ordinateur mille fois plus rapide permet-il de résoudre des problèmes mille fois plus grands ?
• Rendre la monnaie avec le moins de pièces possible : faut-il toujours prendre la plus grosse pièce ?

Toutes les questions maths-nsi →