Comment un logiciel trouve-t-il un mot dans un livre entier sans comparer chaque lettre ?

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'utilise tous les jours la fonction « rechercher » de mon traitement de texte et elle répond instantanément, même dans des documents de centaines de pages. En NSI, nous avons étudié l'algorithme de Boyer-Moore. J'ai trouvé contre-intuitif qu'on puisse chercher plus vite en lisant le motif à l'envers, et j'ai voulu mesurer ce gain.

L'enjeu et les notions du programme

Dénombrer les comparaisons d'un algorithme dans le pire et le meilleur cas, et comprendre comment un prétraitement accélère la recherche.

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

1. 1. Introduction

   1 min

   Chercher un motif de $m$m lettres dans un texte de $n$n lettres est une opération omniprésente : moteurs de recherche, éditeurs, analyse de l'ADN. Problématique : combien de comparaisons faut-il, et peut-on éviter de tout lire ?

2. 2. Mathématiques : compter les comparaisons

   4 min

   Méthode naïve : on place le motif à chacune des $n-m+1$n-m+1 positions et on compare lettre à lettre. Au pire (texte AAAA…A, motif AAAAB), on fait $m$m comparaisons à chaque position : $(n-m+1)m$(n-m+1)m. Pour $n=10^6$n=10⁶ et $m=5$m=5, environ $5\times 10^6$5×10⁶.

   En moyenne, sur un texte varié, la première comparaison échoue souvent : avec 26 lettres équiprobables, elle réussit avec une probabilité $\frac{1}{26}$1/26. Le nombre moyen de comparaisons par position est proche de $1+\frac{1}{26}+\frac{1}{26^2}+\cdots \approx 1,04$1+1/26+1/26²+…≈1,04 : la méthode naïve lit à peu près une fois chaque position.

   Boyer-Moore compare le motif de droite à gauche. Si la lettre du texte en face de la dernière lettre du motif n'apparaît pas dans le motif, on peut décaler le motif de $m$m positions d'un coup. Dans le meilleur cas, on ne lit qu'une lettre sur $m$m : environ $\frac{n}{m}=2\times 10^5$n/m=2×10⁵ comparaisons.

3. 3. NSI : la table des sauts

   3 min

   Avant la recherche, on construit une table qui donne, pour chaque lettre, sa dernière position dans le motif. Ce prétraitement coûte $m$m opérations, négligeables. Pendant la recherche, en cas d'échec, la table indique de combien décaler le motif pour aligner la lettre lue avec son occurrence dans le motif.

   Plus le motif est long et l'alphabet varié, plus les sauts sont grands : c'est l'un des rares algorithmes qui deviennent plus rapides quand le motif s'allonge. Sur l'ADN (4 lettres seulement), les sauts sont plus courts et l'on utilise d'autres méthodes.

4. 4. Conclusion

   1,5 min

   Un logiciel trouve un mot sans comparer chaque lettre grâce aux sauts de Boyer-Moore : au mieux, il ne lit qu'une lettre sur $m$m. Le dénombrement des comparaisons montre l'intérêt d'un prétraitement. J'ouvre sur les index des moteurs de recherche, qui préparent le texte plutôt que le motif.

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

• Confondre le pire cas et le cas moyen.
• Oublier le coût du prétraitement (faible, mais réel).
• Croire que Boyer-Moore lit le texte de droite à gauche : c'est le motif qu'il compare à l'envers.

Revoir les notions

• Combinatoire et dénombrement (Terminale spé maths) →
• Variables aléatoires (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 ?
• Pourquoi couper un problème en deux permet-il de le résoudre beaucoup plus vite ?
• 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 ?

Toutes les questions maths-nsi →