NSI (terminale) · Chapitre 16 · Exercice d'entraînement
Meilleur et pire cas
Calculabilité, décidabilité et paradigmes de programmation · L'algorithme de Boyer--Moore · niveau 3 (difficile)
Énoncé
Meilleur et pire cas. On dispose de la fonction boyer_moore_compte(texte, motif), qui applique Boyer--Moore (règle du mauvais caractère, comparaisons de droite à gauche, décalage de après une occurrence trouvée) et renvoie le couple (positions trouvées, nombre de comparaisons de caractères), et d'une fonction naive_compte(texte, motif) analogue pour la recherche naïve (comparaisons de gauche à droite). Le texte est formé de lettres A.
- Pour chacun des motifs
AAA,BAA,AABetXYZ, prévoir par le raisonnement le nombre de comparaisons de chaque algorithme. - Lequel de ces motifs met Boyer--Moore dans son pire cas ? Est-il alors moins bon que la recherche naïve ?
- Généraliser : pour un texte de longueur et un motif de longueur dont aucun caractère n'apparaît dans le texte, combien de comparaisons Boyer--Moore fait-il, environ ? Et la recherche naïve ?
Un exercice à chercher : son corrigé n'est pas publié. Sur Adloun, le tuteur guide par questions, sans donner la réponse.