Question de mathsMathsRaisonnement et algorithmes

Comment trouver un mot parmi un million en une vingtaine d'essais ?

Dans une liste triée, couper la zone de recherche en deux à chaque comparaison trouve un élément parmi un million en au plus 20 étapes, car 2²⁰ dépasse le million ; le nombre d'étapes croît comme 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.

Pour chercher un mot dans un dictionnaire papier, je ne lis jamais les pages une par une : j'ouvre au milieu, puis je recommence dans la bonne moitié. En apprenant Python, j'ai découvert que les ordinateurs font exactement la même chose, et que cela change tout pour les très grandes listes. J'ai voulu mesurer ce gain avec les logarithmes.

L'enjeu et les notions du programme

Écrire et prouver un algorithme de recherche, et mesurer son efficacité à l'aide des suites géométriques et du logarithme.

Mathématiques

Algorithmique : boucle while, listes en Python (seconde, première)
Suites géométriques (première)
Logarithme népérien, $lo g_{2} n = \frac{l n n}{l n 2}$ log₂ n=(ln n)/(ln 2) (terminale)
Dichotomie et théorème des valeurs intermédiaires (terminale)

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

1. Introduction : chercher dans une liste
1,5 min
Dans une liste de $n$ n éléments non triée, il faut parfois tout parcourir : jusqu'à $n$ n comparaisons. Problématique : si la liste est triée, combien de comparaisons suffisent, et pourquoi ?
2. L'algorithme
3 min
On garde deux indices $g$ g et $d$ d qui encadrent la zone où le mot peut encore se trouver. On compare le mot cherché avec l'élément du milieu $m = ⌊ \frac{g + d}{2} ⌋$ m=lfloor(g+d)/2rfloor : s'il est égal, on a fini ; s'il est plus petit, on remplace $d$ d par $m - 1$ m-1 ; sinon $g$ g par $m + 1$ m+1. On s'arrête si $g > d$ g>d : le mot est absent.
Correction : l'invariant « si le mot est dans la liste, il est entre les indices $g$ g et $d$ d » est vrai au départ et conservé à chaque tour, parce que la liste est triée. Terminaison : la longueur $d - g + 1$ d-g+1 est un entier qui diminue strictement.
3. Combien d'étapes ?
3,5 min
Après chaque comparaison, la zone contient au plus la moitié des éléments restants. Après $k$ k comparaisons, il en reste au plus $\frac{n}{2 ^{k}}$ n/2^(k) : une suite géométrique de raison $\frac{1}{2}$ 1/2. On a fini dès que $\frac{n}{2 ^{k}} < 1$ n/2^(k)<1, c'est-à-dire $2^{k} > n$ 2^(k)>n, soit $k > \frac{l n n}{l n 2}$ k>(ln n)/ln2.
Pour $n = 1 0^{6}$ n=10⁶ : $2^{20} = 1048576 > 1 0^{6}$ 2²⁰=1 048 576>10⁶, donc 20 comparaisons suffisent, contre un demi-million en moyenne en lisant la liste. Pour $n = 1 0^{9}$ n=10⁹, environ 30 : multiplier la taille par mille n'ajoute qu'une dizaine d'étapes, car $2^{10} = 1024 \approx 1 0^{3}$ 2¹⁰=1 024≈10³.
C'est la même idée que la dichotomie pour résoudre $f (x) = 0$ f(x)=0 : chaque étape divise par deux la longueur de l'intervalle.
4. Conclusion
1,5 min
On trouve un mot parmi un million en 20 essais en coupant la zone en deux à chaque fois, à condition que la liste soit triée. Le coût passe de $n$ n à $lo g_{2} n$ log₂ n. J'ouvre sur le coût du tri lui-même : il faut trier une fois pour chercher ensuite très vite, comme le fait un moteur de recherche avec son index.

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.

apr \overset{e}{ˋ} s k \overset{e}{ˊ} tapes : au plus \frac{n}{2 ^{k}} \overset{e}{ˊ} l \overset{e}{ˊ} ments 2^{k} > n ⟺ k > \frac{ln n}{ln 2} après k étapes : au plus n/2^(k) éléments 2^(k)>n\Leftrightarrow k>(ln n)/(ln 2) 2^{10} = 1024 2^{20} = 1048576 > 1 0^{6} 2¹⁰=1 024 2²⁰=1 048 576>10⁶

Conclusion : la réponse à la question

La recherche par dichotomie trouve un élément d'une liste triée de $n$ n éléments en environ $lo g_{2} n$ log₂ n comparaisons : 20 pour un million, 30 pour un milliard. Elle illustre la puissance d'un algorithme dont on a prouvé la correction (un invariant) et mesuré le coût (une suite géométrique).

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.

Combien de comparaisons au plus pour un dictionnaire de 60 000 mots ?

$2^{16} = 65536 > 60000$ 2¹⁶=65 536>60 000 : 16 comparaisons suffisent.

Pourquoi la liste doit-elle être triée ?

Sinon, comparer avec l'élément du milieu ne dit pas dans quelle moitié chercher : l'invariant n'est plus conservé.

Pourquoi l'algorithme s'arrête-t-il toujours ?

La longueur $d - g + 1$ d-g+1 est un entier naturel qui diminue d'au moins 1 à chaque tour : une suite d'entiers naturels strictement décroissante est finie.

Écrivez la boucle principale en Python.

while g <= d: m = (g + d) // 2, puis on compare L[m] au mot et on met à jour g ou d.

Combien d'étapes de dichotomie pour encadrer une racine à 10⁻³ près sur [0 ; 1] ?

Il faut $\frac{1}{2 ^{k}} \leq 1 0^{- 3}$ 1/2^(k)≤10⁻³, soit $2^{k} \geq 1000$ 2^(k)≥1 000 : $k = 10$ k=10.

Peut-on faire mieux que log₂ n avec des comparaisons ?

Non en général : chaque comparaison donne une réponse à deux issues, donc $k$ k comparaisons distinguent au plus $2^{k}$ 2^(k) cas, et il faut $2^{k} \geq n$ 2^(k)≥ n.

Les pièges qui coûtent des points

Appliquer la dichotomie à une liste non triée.
Écrire $m = \frac{g + d}{2}$ m=(g+d)/2 sans partie entière : l'indice doit être un entier.
Confondre $lo g_{2} n$ log₂ n et $\frac{n}{2}$ n/2.

Revoir les notions

Autres questions : raisonnement et algorithmes

Toutes les questions de maths →

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 maths-physique-chimie →Questions maths-SES →Questions maths-SVT →Questions maths-NSI →Questions maths-SI →Questions maths-HGGSP →Questions maths-anglais →