Exercice 1 - Boyer-Moore · Bac Numérique et Sciences Informatiques Asie 2025 (jour 1)
Thème : Recherche textuelle et algorithme de Boyer-Moore · Tiré du sujet Jour 1 (2025)
Énoncé
EXERCICE 1 (6 points)
Cet exercice porte sur la décidabilité, l'algorithmique et la programmation en Python.
En Python, on peut utiliser le triple guillemet pour écrire une chaîne de caractères sur plusieurs lignes. Par exemple, on peut définir une variable programme1 qui contient la chaîne de caractères correspondant à un petit programme Python de la manière suivante:
1 programme1 = """
2 x = 10
3 y = 10
4 while x > 0:
5 x = x - 1
6 y = y + 1
7 """
De même, on peut définir la variable programme2:
1 programme2 = """
2 def boucle_infinie():
3 while True:
4 pass # Ne rien faire
5 boucle_infinie()
6 """
On suppose disposer d'une fonction recherche(mot, texte) qui renvoie True si une chaîne de caractères mot est présente dans une chaîne de caractères texte et False sinon.
5.
Expliquer succinctement le principe de l'algorithme de Boyer-Moore qui permet d'implémenter cette fonction recherche.
Corrigé
Corrigé proposé par AprenAI (non officiel)
5. Expliquer succinctement le principe de l'algorithme de Boyer-Moore qui permet d'implémenter cette fonction recherche.
Réponse : L'algorithme de Boyer-Moore repose sur deux principes fondamentaux : 1. Comparaison de droite à gauche : pour un alignement donné du motif avec le texte, les caractères sont comparés en partant de la fin du motif vers le début. 2. Sauts et décalages optimisés (règle du mauvais caractère) : en cas de discordance entre un caractère du motif et un caractère du texte, l'algorithme utilise une table prétraitée pour décaler le motif de plusieurs positions d'un coup (au lieu d'avancer d'une seule case), alignant le caractère fautif du texte avec sa dernière occurrence dans le motif, voire en sautant tout le motif s'il n'y apparaît pas.
L’explication pas à pas, faite avec l’IA, est réservée aux membres Premium. Premium
Résous-le ici : correction automatique, indices et corrigé détaillé.