Exercice 1 sur 8
QCMDans quel sens l’algorithme de Boyer-Moore compare-t-il le motif au texte, à une position donnée ?
Aide d’ULU pour cet exerciceNumérique et sciences informatiques (NSI) · Terminale
Exercices : recherche textuelle : l’algorithme de Boyer-Moore
22 exercices avec correction détaillée, en 3 séries. Aucune inscription : ta progression reste sur ton appareil.
ULUMINE · Numérique et sciences informatiques (NSI) · Terminale
Recherche textuelle : l’algorithme de Boyer-Moore — S’entraîner
Feuille d’exercices
Prénom : ……………………………Date : ……………………Score : ……… / 8
Les fonctions recherche_naive, table_decalages et boyer_moore sont celles du cours. Les positions commencent à 0.
Exercice 1 — Coche la bonne réponse.
Dans quel sens l’algorithme de Boyer-Moore compare-t-il le motif au texte, à une position donnée ?
- De gauche à droite
- De droite à gauche
- Du milieu vers les bords
- Dans un ordre aléatoire
Exercice 2
Dans la table des décalages du motif CHIEN, quel est le décalage associé à la lettre H ?
Écris tes calculs :
Réponse : ………………
Exercice 3
Dans la table des décalages du motif CHIEN, quel est le décalage associé à la lettre Z ?
Écris tes calculs :
Réponse : ………………
Exercice 4
Que renvoie recherche_naive("ABRACADABRA", "ABRA") ? Écris la liste Python.
Exercice 5 — Coche « Vrai » ou « Faux ».
Dans le pire cas, l’algorithme naïf effectue de l’ordre de n × m comparaisons (texte de longueur n, motif de longueur m).
VraiFaux
Exercice 6
Combien de positions i l’algorithme boyer_moore examine-t-il pour rechercher CHIEN dans « UN CHAT ET UN CHIEN » ?
Écris tes calculs :
Réponse : ………………
Exercice 7 — Complète les trous.
Complète.
Pour le motif ABBA (m = 4), la table des décalages donne A → et B → . Une lettre absente du motif, comme C, donne un décalage de .
Exercice 8
Explique avec tes mots pourquoi, lorsque la lettre du texte alignée avec la fin du motif n’apparaît pas du tout dans le motif, on peut décaler le motif de toute sa longueur sans risquer de manquer une occurrence.
ulumine.com — exercices corrigés gratuits
ULUMINE · Numérique et sciences informatiques (NSI) · Terminale
Recherche textuelle : l’algorithme de Boyer-Moore — S’entraîner
Corrigé détaillé — pour les parents et les enseignants
Exercice 1
Réponse : De droite à gauche
On commence par la dernière lettre du motif. Une différence trouvée tout de suite permet souvent un grand saut.
Exercice 2
Réponse : 3
m = 5 et H est à l’indice 1 : 5 − 1 − 1 = 3. Décaler de 3 place le H du motif sous le H lu dans le texte.
Exercice 3
Réponse : 5
Z n’apparaît pas dans le motif : aucune position du motif ne peut se trouver sous ce Z, on décale de toute la longueur, 5.
Exercice 4
Réponse : [0, 7]
ABRA apparaît au début (position 0) et à la fin (position 7, car 11 − 4 = 7).
Exercice 5
Réponse : Vrai
Il y a n − m + 1 positions et jusqu’à m comparaisons par position. Par exemple pour chercher AAAB dans AAAAAAAA…
Exercice 6
Réponse : 5
Comme dans le cours, i prend les valeurs 0, 3, 8, 13 et 14. L’algorithme naïf, lui, examine les 15 positions de 0 à 14.
Exercice 7
Réponse : 3 · 1 · 4
On ne considère que ABB (sans la dernière lettre). Dernière occurrence de A : indice 0, décalage 4 − 1 − 0 = 3. Dernière occurrence de B : indice 2, décalage 4 − 1 − 2 = 1.
Exercice 8
Exemple de réponse : Toute occurrence du motif qui recouvrirait cette lettre du texte devrait avoir, à cet endroit, une lettre du motif égale à elle. Comme cette lettre n’apparaît pas dans le motif, aucune position du motif recouvrant cette case ne peut convenir. Les positions possibles commencent donc après cette lettre, c’est-à-dire m positions plus loin.
C’est la justification de la règle « décalage = m pour une lettre absente » ; la même idée justifie les autres décalages de la table.
- Une occurrence recouvrant la lettre devrait contenir cette lettre.
- La lettre n’est pas dans le motif : contradiction.
- On peut donc reprendre juste après la lettre, soit un décalage de m.
Les fonctions recherche_naive, table_decalages et boyer_moore sont celles du cours. Les positions commencent à 0.
Exercices corrigés : 0 / 8
- Aide d’ULU pour cet exercice
Exercice 2 sur 8
CalculDans la table des décalages du motif CHIEN, quel est le décalage associé à la lettre H ?
Aide d’ULU pour cet exerciceExercice 3 sur 8
CalculDans la table des décalages du motif CHIEN, quel est le décalage associé à la lettre Z ?
Aide d’ULU pour cet exerciceExercice 4 sur 8
Réponse à écrireQue renvoie recherche_naive("ABRACADABRA", "ABRA") ? Écris la liste Python.
Aide d’ULU pour cet exerciceExercice 5 sur 8
Vrai ou fauxDans le pire cas, l’algorithme naïf effectue de l’ordre de n × m comparaisons (texte de longueur n, motif de longueur m).
Aide d’ULU pour cet exerciceExercice 6 sur 8
CalculCombien de positions i l’algorithme boyer_moore examine-t-il pour rechercher CHIEN dans « UN CHAT ET UN CHIEN » ?
Aide d’ULU pour cet exerciceExercice 7 sur 8
Texte à trousComplète.
Aide d’ULU pour cet exerciceExercice 8 sur 8
Question ouverteExplique avec tes mots pourquoi, lorsque la lettre du texte alignée avec la fin du motif n’apparaît pas du tout dans le motif, on peut décaler le motif de toute sa longueur sans risquer de manquer une occurrence.
Aide d’ULU pour cet exercice
À découvrir aussi
Terminale · Numérique et sciences informatiques (NSI)
La récursivité
Fonctions récursives en Python : cas de base, appels récursifs, pile d’appels, terminaison et comparaison avec l’itératif. Cours et exercices de NSI Terminale.
Terminale · Numérique et sciences informatiques (NSI)
La programmation orientée objet
Classes, objets, attributs et méthodes en Python : constructeur __init__, self, interface et références. Cours et exercices de programmation objet en NSI Terminale.
Terminale · Numérique et sciences informatiques (NSI)
Listes, piles, files et dictionnaires
Interface et implémentation des structures linéaires : listes chaînées, piles (LIFO), files (FIFO) et dictionnaires en Python. Cours et exercices de NSI Terminale.