Diviser pour régner et programmation dynamique

Diviser pour régner : principe et schéma général#

Baseeduscol-programme-nsi-terminale

Le triptyque diviser / régner / combiner

Fig. 1Diviser pour régner en trois temps : DIVISER le problème en sous-problèmes plus petits, les RÉGNER (résoudre récursivement), puis COMBINER leurs solutions (étape mise en évidence) pour reconstruire la solution du problème de départ.

La méthode « diviser pour régner » (en anglais divide and conquer) résout un problème en trois temps : diviser le problème en sous-problèmes plus petits de même nature, régner en résolvant chaque sous-problème récursivement, puis combiner les solutions partielles en une solution du problème de départ.

La récursivité s'arrête sur un cas de base : lorsque la taille du problème devient assez petite (par exemple un tableau de 0 ou 1 élément), on renvoie directement la solution sans nouvelle division. Sans cas de base atteignable, l'algorithme ne se termine pas.

Les sous-problèmes engendrés sont indépendants : ils ne partagent pas de calcul commun. C'est exactement ce qui distingue « diviser pour régner » de la programmation dynamique (où les sous-problèmes, au contraire, se chevauchent).

Le coût se lit sur l'arbre de récursion : à chaque niveau on divise la taille (souvent par 2), donc l'arbre a une hauteur de l'ordre de log₂(n). Si le travail de division et de combinaison est linéaire à chaque niveau, le coût total est de l'ordre de n × log₂(n).

Exemples canoniques au programme : le tri fusion, la recherche dichotomique et la rotation d'une image (on tourne récursivement les quatre quartiers puis on les recompose).

Rappel de première : la récursivité (cas de base, cas récursif) et la notion de coût (complexité) sont des prérequis. En terminale, on les applique aux stratégies algorithmiques.

T(n) = 2\,T\!\left(\tfrac{n}{2}\right) + c\,n \quad\Longrightarrow\quad T(n) = O(n \log n)

Relation de récurrence typique de « diviser pour régner »

Deux sous-problèmes de taille n/2 (le 2·T(n/2)) plus un travail de division et de combinaison linéaire (le c·n) conduisent à un coût en n·log(n) : c'est le cas du tri fusion.

Exemple corrigé

Reconnaître le schéma sur le calcul du maximum

On veut le maximum d'un tableau t de longueur n par « diviser pour régner ». Préciser le cas de base, l'étape de division, l'étape « régner » et l'étape « combiner », puis dérouler sur t = [3, 9, 1, 7].

Cas de base
Si le tableau contient un seul élément, le maximum est cet élément : on le renvoie directement, sans division.
Diviser
On coupe le tableau en deux moitiés de tailles aussi égales que possible : gauche = [3, 9] et droite = [1, 7].
Régner (récursivité)
On calcule récursivement le maximum de chaque moitié. max([3, 9]) = 9 et max([1, 7]) = 7.
Combiner
L'étape « combiner » prend le plus grand des deux maxima partiels : max(9, 7) = 9.

Résultat : Le maximum est 9. Le découpage illustre le triptyque : division en deux moitiés, résolution récursive (régner), puis combinaison par un simple max(·, ·).

Erreurs fréquentes

Oublier l'étape combiner : « diviser pour régner » ne se limite pas à découper et résoudre, c'est la recombinaison des solutions partielles qui produit le résultat (la fusion dans le tri fusion).
Confondre « diviser pour régner » et programmation dynamique : ici les sous-problèmes sont indépendants ; il n'y a aucun intérêt à mémoïser car on ne recalcule jamais deux fois le même sous-problème.

Révision active

Décrire le découpage « diviser / régner / combiner » pour le calcul du maximum d'un tableau par dichotomie : que vaut le cas de base, comment divise-t-on, et qu'est-ce que l'étape « combiner » ?

Rappel actif

Rappelle-toi les points clés — puis révèle.

Sources : Programme de spécialité NSI — classe terminale (voie générale), BO spécial n° 8 du 25 juillet 2019 (Ministère de l'Éducation nationale) · Programmes et ressources en numérique et sciences informatiques — voie générale (Éduscol)

Tri fusion et recherche dichotomique comme « diviser pour régner »#

Standardeduscol-programme-nsi-terminale

Tri fusion : arbre de division puis de fusion

Fig. 2On divise [5, 2, 8, 1] jusqu'aux singletons (cas de base), puis on REMONTE en fusionnant deux listes triées à la fois pour obtenir [1, 2, 5, 8]. L'arbre a environ log₂(n) niveaux et chaque niveau coûte O(n) : d'où un coût total en O(n log n).

Tri fusion (merge sort). DIVISER : couper le tableau en deux moitiés. RÉGNER : trier récursivement chaque moitié. COMBINER : fusionner les deux moitiés triées en parcourant les deux en parallèle et en prenant à chaque pas le plus petit élément en tête. Cas de base : un tableau de 0 ou 1 élément est déjà trié.

La fusion de deux listes déjà triées de longueurs p et q se fait en O(p + q) : un seul parcours, sans comparaison superflue. C'est l'étape « combiner » qui fait tout le travail dans le tri fusion.

Coût du tri fusion : O(n log n), dans tous les cas (meilleur, moyen, pire). L'arbre de récursion a une hauteur d'environ log₂(n) niveaux et chaque niveau réalise un travail total de l'ordre de n (les fusions). C'est nettement mieux qu'un tri naïf en O(n²) dès que n est grand.

Recherche dichotomique (recherche par dichotomie) dans un tableau trié : comparer la cible à l'élément du milieu d'indice m ; si égal, c'est trouvé ; si la cible est plus petite, recommencer dans la moitié gauche, sinon dans la moitié droite. À chaque tour, l'intervalle de recherche est divisé par deux.

Coût de la dichotomie : O(log n) comparaisons au pire. Pour n = 1000, une dizaine de comparaisons suffisent ; pour n = 1 000 000, une vingtaine. Prérequis impératif : le tableau doit être trié (sinon le résultat est faux).

(Rappel de première) la recherche dichotomique a été introduite en classe de première ; en terminale, on la relit ici comme illustration de la méthode « diviser pour régner » (le programme demande d'illustrer cette méthode « sur le tri fusion ou la recherche dichotomique »). Le tri fusion, lui, est l'exemple canonique propre à la terminale.

C_{\text{fusion}}(n) = O(n \log n), \qquad C_{\text{dichotomie}}(n) = O(\log n)

Coûts au pire du tri fusion et de la recherche dichotomique

Le tri fusion coûte n·log(n) (log(n) niveaux, travail n par niveau) ; la recherche dichotomique coûte log(n) car l'intervalle de recherche est divisé par 2 à chaque tour.

m = \left\lfloor \frac{g + d}{2} \right\rfloor

Indice du milieu en recherche dichotomique

g et d sont les bornes gauche et droite de l'intervalle courant ; on compare la cible à l'élément d'indice m, puis on ne conserve qu'une moitié.

Recherche dichotomique pas à pas

Fig. 3Recherche de 29 dans le tableau trié [4, 11, 18, 23, 29, 40, 55]. À chaque tour on compare la cible au milieu m et on REJETTE la moitié inutile : l'intervalle est divisé par deux, d'où un coût en O(log₂ n). La case trouvée est mise en évidence.

Coût comparé : tri fusion (n log n) contre tri naïf (n²)

Exemple corrigé

Tri fusion de [5, 2, 8, 1]

Trier le tableau [5, 2, 8, 1] par tri fusion. Détailler l'arbre de division puis les fusions successives, et indiquer le nombre de niveaux de l'arbre.

Diviser jusqu'aux cas de base
On coupe en deux à chaque étape : [5, 2, 8, 1] -> [5, 2] et [8, 1] -> [5], [2], [8], [1]. Un tableau d'un seul élément est trié : ce sont les cas de base.
Fusionner le premier niveau
On fusionne deux listes triées d'un élément : fusion([5], [2]) compare 5 et 2, place 2 puis 5 ; fusion([8], [1]) place 1 puis 8.
Fusion finale
On fusionne [2, 5] et [1, 8] : on compare les têtes 2 et 1 (on prend 1), puis 2 et 8 (on prend 2), puis 5 et 8 (on prend 5), enfin 8.
Compter les niveaux
Pour n = 4, l'arbre a log₂(4) = 2 niveaux de division. Le coût total est de l'ordre de n·log₂(n) = 4 × 2 = 8 opérations de comparaison/copie.

Résultat : Le tableau trié est [1, 2, 5, 8]. L'arbre comporte 2 niveaux de division, ce qui illustre le coût en O(n log n) du tri fusion.

Exemple corrigé

Recherche dichotomique de 40

Dans le tableau trié [4, 11, 18, 23, 29, 40, 55] (indices 0 à 6), rechercher la valeur 40 par dichotomie. Donner la suite des indices g, d, m et le nombre de comparaisons.

Premier milieu
g = 0, d = 6, m = (0+6)//2 = 3. On compare 40 à t[3] = 23 : 40 > 23, donc la cible est dans la moitié droite.
Deuxième milieu
On recommence avec g = 4, d = 6, m = (4+6)//2 = 5. On compare 40 à t[5] = 40 : égalité.
Conclure
t[5] = 40 est la cible : on renvoie l'indice 5. Deux comparaisons ont suffi, conformément à l'ordre de log₂(7) ≈ 2,8.

Résultat : 40 est trouvé à l'indice 5 en 2 comparaisons. La recherche n'a exploré qu'une fraction du tableau, illustrant le coût logarithmique de la dichotomie.

Erreurs fréquentes

Appliquer la recherche dichotomique à un tableau non trié : l'algorithme renverra un résultat faux. Le tri préalable est une condition de correction, pas une option.
Dans la fusion, oublier de vider la moitié restante quand l'une des deux listes est épuisée avant l'autre : on perd alors des éléments et le tableau final est incomplet.

Révision active

Écrire la fonction fusion(a, b) qui fusionne deux listes triées en une liste triée, puis le tri fusion récursif. Dérouler l'arbre de division puis de fusion sur le tableau [5, 2, 8, 1] et compter le nombre de niveaux.

Rappel actif

Rappelle-toi les points clés — puis révèle.

Sources : Programme de spécialité NSI — classe terminale (voie générale), BO spécial n° 8 du 25 juillet 2019 (Ministère de l'Éducation nationale) · Programmes et ressources en numérique et sciences informatiques — voie générale (Éduscol)

Programmation dynamique : chevauchement et mémoïsation#

Standardeduscol-programme-nsi-terminale

Sous-problèmes qui se chevauchent et mémoïsation

Fig. 5Les sous-problèmes se CHEVAUCHENT : fib(3) (mis en évidence) est requis par fib(5) ET par fib(4). En mémoïsant chaque résultat dans une table, on ne le calcule QU'UNE fois — d'où un graphe d'appels où chaque nœud est unique, et un coût qui passe d'exponentiel à linéaire.

La programmation dynamique s'applique aux problèmes dont les sous-problèmes se chevauchent : un même sous-problème est rencontré plusieurs fois au cours de la résolution. L'idée fondatrice est de ne le résoudre qu'une seule fois, puis de réutiliser le résultat stocké.

*Mémoïsation (approche descendante, top-down)* : on garde l'algorithme récursif naturel, mais on ajoute une mémoire (dictionnaire ou tableau) ; avant tout calcul on regarde si le résultat est déjà mémorisé, et on ne le recalcule jamais.

*Table (approche ascendante, bottom-up)* : on remplit un tableau des plus petits sous-problèmes vers les plus grands, sans récursivité, jusqu'à atteindre la solution cherchée. Les deux approches ont la même complexité ; la table évite la pile d'appels.

Le gain est spectaculaire : le calcul naïf de Fibonacci recalcule sans cesse les mêmes valeurs et son coût est exponentiel ; mémoïsé, chaque fib(k) n'est calculé qu'une fois et le coût devient linéaire O(n). C'est l'exemple canonique du chevauchement.

Différence clé avec « diviser pour régner » : là, les sous-problèmes sont indépendants (aucun recalcul, donc mémoïser ne sert à rien) ; en programmation dynamique, ils se chevauchent (mémoïser est l'optimisation décisive). On échange de la mémoire contre du temps.

Exemples au programme : la suite de Fibonacci mémoïsée et le rendu de monnaie (développés ici). Le programme cite aussi l'alignement de séquences (approfondissement, non développé dans cette fiche) ; les deux premiers suffisent pour maîtriser la capacité attendue.

F(n) = \begin{cases} n & \text{si } n \leqslant 1 \\ F(n-1) + F(n-2) & \text{si } n \geqslant 2 \end{cases}

Définition récursive de la suite de Fibonacci

F(0)=0 et F(1)=1 sont les cas de base ; chaque terme dépend des deux précédents, d'où le chevauchement (F(n-1) recalcule lui-même F(n-2)).

C_{\text{naïf}}(n) = O(\varphi^{\,n}) \xrightarrow{\ \text{mémoïsation}\ } C_{\text{mémo}}(n) = O(n), \quad \varphi = \tfrac{1+\sqrt{5}}{2} \approx 1{,}618

De l'exponentiel au linéaire grâce à la mémoïsation

Le nombre d'appels du Fibonacci naïf croît comme φ puissance n (nombre d'or) ; en mémoïsant, chaque F(k) n'est évalué qu'une fois, d'où un coût linéaire.

Coût des appels : Fibonacci naïf (exponentiel) contre mémoïsé (linéaire)

Exemple corrigé

Du Fibonacci naïf au Fibonacci mémoïsé

La fonction naïve def fib(n): return n if n<2 else fib(n-1)+fib(n-2) est très lente. Compter le nombre d'appels pour fib(5), puis écrire la version mémoïsée et expliquer le gain.

Compter les appels de la version naïve
Le nombre d'appels de fib naïf vaut 2·F(n+1) − 1. Pour n = 5, F(6) = 8, soit 2×8 − 1 = 15 appels ; pour n = 10, F(11) = 89, soit 177 appels. La croissance est exponentielle.
Repérer le chevauchement
Dans l'arbre de fib(5), fib(3) est calculé deux fois, fib(2) trois fois, etc. Ce sont les mêmes sous-problèmes recalculés : c'est le signe qu'il faut mémoïser.
Écrire la version mémoïsée
On ajoute un dictionnaire memo. En Python : def fib(n, memo={0:0, 1:1}): if n not in memo: memo[n] = fib(n-1, memo) + fib(n-2, memo); return memo[n]. Avant de calculer, on lit la mémoire.
Expliquer le gain
Chaque fib(k) pour k de 0 à n n'est désormais calculé qu'une seule fois : il y a n+1 calculs distincts. Le coût passe de l'ordre de φ puissance n (exponentiel) à O(n) (linéaire).

Résultat : fib(5) demande 15 appels en naïf mais seulement quelques calculs distincts en mémoïsé. La mémoïsation rend le calcul linéaire en n : c'est l'exemple type de la programmation dynamique sur des sous-problèmes qui se chevauchent.

Schritt-für-Schritt Erklärung4 Schritte

1
Partons du Fibonacci naïf. Pour calculer fib(5), la fonction se rappelle elle-même sur fib(4) et fib(3) : et c'est déjà là que le problème commence.
2
Si l'on déroule l'arbre des appels, on voit que fib(3) apparaît plusieurs fois, fib(2) encore plus. Les mêmes sous-problèmes sont recalculés sans cesse : ils se chevauchent.
3
L'idée de la programmation dynamique : la première fois qu'on calcule fib de k, on range le résultat dans une table. La fois suivante, on le relit au lieu de le recalculer.
4
Résultat : chaque sous-problème n'est résolu qu'une fois. Le coût passe d'exponentiel à linéaire. On a échangé un peu de mémoire contre énormément de temps.
Appels de fib(n) en version naïve

Erreurs fréquentes

Appliquer la programmation dynamique à des sous-problèmes indépendants : sans chevauchement, la mémoïsation n'apporte aucun gain et alourdit inutilement le code.
Oublier d'initialiser correctement la mémoire (les cas de base) ou de lire la mémoire avant de calculer : la fonction recalcule alors tout et le coût exponentiel persiste malgré le dictionnaire.

Révision active

Écrire fib_memo(n) mémoïsé avec un dictionnaire, puis fib_table(n) ascendant avec un tableau. Vérifier que les deux donnent fib(10) = 55 et expliquer pourquoi chacun est en O(n) là où la version naïve est exponentielle.

Rappel actif

Rappelle-toi les points clés — puis révèle.

Sources : Programme de spécialité NSI — classe terminale (voie générale), BO spécial n° 8 du 25 juillet 2019 (Ministère de l'Éducation nationale) · Programmes et ressources en numérique et sciences informatiques — voie générale (Éduscol)

Rendu de monnaie : exemple de programmation dynamique#

Approfondissementeduscol-programme-nsi-terminale

Rendu de monnaie : table dynamique et échec du glouton

Fig. 7Système {1, 3, 4}. La programmation dynamique remplit m[a] = nombre minimal de pièces. Pour a = 6, la DP trouve 2 pièces (3 + 3, cellule mise en évidence) ; le glouton (prendre la plus grosse pièce) donne 4 + 1 + 1 = 3 pièces : il n'est PAS optimal sur ce système.

Problème du rendu de monnaie : étant donné un système de pièces et un montant, rendre ce montant avec le nombre minimal de pièces. C'est un exemple emblématique de programmation dynamique au programme.

Relation de récurrence : pour rendre le montant a, on essaie chaque pièce p de valeur ≤ a ; on prend cette pièce (1 pièce) plus le rendu optimal du reste a − p. Le minimum sur toutes les pièces donne le rendu optimal de a. On remplit la table m[0], m[1], …, m[montant] de manière ascendante.

Le chevauchement est manifeste : le sous-problème « rendre a − p » réapparaît pour de nombreuses valeurs de a, donc on le mémorise une fois pour toutes dans la table. C'est ce qui justifie l'emploi de la programmation dynamique.

L'algorithme glouton (prendre à chaque pas la plus grande pièce possible) est plus simple mais n'est pas toujours optimal : avec le système de pièces {1, 3, 4} pour rendre 6, le glouton donne 4 + 1 + 1 = 3 pièces, alors que l'optimum est 3 + 3 = 2 pièces. La programmation dynamique, elle, garantit l'optimum.

Le système de pièces usuel (euros : 1, 2, 5, 10, 20, 50…) est canonique : le glouton y est optimal. Mais ce n'est pas une propriété générale ; seul un algorithme exact (programmation dynamique) garantit le minimum quel que soit le système.

m[a] = \begin{cases} 0 & \text{si } a = 0 \\ 1 + \min_{\,p \leqslant a} m[a - p] & \text{si } a \geqslant 1 \end{cases}

Récurrence du rendu de monnaie (nombre minimal de pièces)

p parcourt les valeurs de pièces inférieures ou égales à a ; on ajoute 1 pièce (la pièce p) au rendu optimal du reste a − p, et on garde le minimum. m[0] = 0 est le cas de base.

Exemple corrigé

Rendre 6 avec le système {1, 3, 4}

Avec les pièces {1, 3, 4}, déterminer le nombre minimal de pièces pour rendre 6 par programmation dynamique. Remplir la table m[0..6], puis comparer au résultat de l'algorithme glouton.

Initialiser le cas de base
Rendre 0 ne demande aucune pièce : m[0] = 0. Pour chaque a ⩾ 1, on appliquera m[a] = 1 + min des m[a − p] pour p dans {1, 3, 4} avec p ⩽ a.
Remplir m[1] à m[5]
m[1] = 1 + m[0] = 1 ; m[2] = 1 + m[1] = 2 ; m[3] = 1 + min(m[2], m[0]) = 1 (une pièce de 3) ; m[4] = 1 + min(m[3], m[1], m[0]) = 1 (une pièce de 4) ; m[5] = 1 + min(m[4], m[2], m[1]) = 2.
Calculer m[6]
m[6] = 1 + min(m[6−1], m[6−3], m[6−4]) = 1 + min(m[5], m[3], m[2]) = 1 + min(2, 1, 2) = 1 + 1 = 2. La pièce choisie est 3, et m[3] = 1, donc 6 = 3 + 3.
Comparer au glouton
L'algorithme glouton prend la plus grande pièce ⩽ 6, c'est-à-dire 4, puis il reste 2, soit 1 + 1 : il rend 4 + 1 + 1 = 3 pièces. La programmation dynamique fait mieux avec 3 + 3 = 2 pièces.

Résultat : La table donne m[6] = 2 (6 = 3 + 3). L'algorithme glouton, lui, rend 3 pièces (4 + 1 + 1) : il n'est pas optimal sur ce système, ce que la programmation dynamique corrige.

Erreurs fréquentes

Croire que l'algorithme glouton donne toujours le nombre minimal de pièces : c'est faux pour certains systèmes (ex. {1, 3, 4} pour 6). Seule la programmation dynamique le garantit en toute généralité.
Mal initialiser la table : m[0] = 0 (rendre 0 demande 0 pièce) est le cas de base. Oublier cette initialisation ou ne pas traiter le cas « montant non rendable » conduit à des résultats faux.

Révision active

Avec le système de pièces {1, 3, 4}, calculer par programmation dynamique le nombre minimal de pièces pour rendre 6, en remplissant la table m[0] à m[6]. Comparer au résultat de l'algorithme glouton.

Rappel actif

Rappelle-toi les points clés — puis révèle.

Sources : Programme de spécialité NSI — classe terminale (voie générale), BO spécial n° 8 du 25 juillet 2019 (Ministère de l'Éducation nationale) · Programmes et ressources en numérique et sciences informatiques — voie générale (Éduscol)

Recherche textuelle : motif dans un texte et algorithme de Boyer-Moore#

Standardeduscol-programme-nsi-terminale

Boyer-Moore : comparaison de droite à gauche et décalage

Fig. 8Recherche du motif « EME » dans « UN_EXEMPLE_ ». On compare le motif de DROITE à GAUCHE ; quand le caractère du texte est absent du motif, on saute de toute la longueur du motif d'un coup (au lieu d'une position). Ces grands décalages rendent Boyer-Moore très rapide en pratique.

Recherche textuelle : localiser les occurrences d'un motif (une chaîne de longueur m) dans un texte (longueur n). C'est une opération de base (traitement de texte, recherche dans un navigateur, bio-informatique).

Recherche naïve : on aligne le motif à chaque position du texte et on compare caractère par caractère ; en cas d'échec on décale le motif d'une seule position. Coût au pire O(n × m) : on peut tester presque toutes les positions.

Algorithme de Boyer-Moore : on compare le motif au texte de droite à gauche ; en cas de discordance, on décale le motif de plusieurs positions d'un coup (au lieu d'une), en sautant les alignements qui ne peuvent pas correspondre. C'est l'optimisation de la recherche naïve au programme.

Le saut repose sur le caractère du texte qui a provoqué l'échec : s'il n'apparaît pas dans le motif, on peut décaler le motif entièrement au-delà ; s'il y apparaît, on l'aligne sur sa dernière occurrence dans le motif. En pratique, Boyer-Moore est souvent sous-linéaire (il n'examine pas tous les caractères du texte).

Comparaison des coûts : la recherche naïve teste chaque position en glissant de 1 ; Boyer-Moore saute des positions grâce aux décalages, ce qui le rend généralement plus rapide sur de longs textes — illustration directe de l'optimisation d'une recherche.

C_{\text{naïve}}(n, m) = O(n \times m), \qquad C_{\text{Boyer-Moore}} = \text{sous-linéaire en pratique}

Coûts de la recherche textuelle

n est la longueur du texte, m celle du motif. La recherche naïve peut comparer presque toutes les positions ; Boyer-Moore saute des positions grâce aux décalages et examine souvent moins de n caractères.

Exemple corrigé

Recherche naïve du motif « ABA » dans « ABCABABA »

Rechercher toutes les occurrences du motif « ABA » (m = 3) dans le texte « ABCABABA » (n = 8) par recherche naïve. Donner les positions de départ testées, les comparaisons décisives et les occurrences trouvées.

Aligner le motif en position 0
Texte « ABCABABA », motif « ABA » sous les indices 0-1-2. On compare : A=A, B=B, mais texte[2]='C' ≠ motif[2]='A'. Échec, on décale d'une position.
Positions 1 et 2
i = 1 : texte[1]='B' ≠ motif[0]='A', échec immédiat. i = 2 : texte[2]='C' ≠ 'A', échec immédiat. On continue à glisser d'une position.
Position 3 : première occurrence
i = 3 : texte[3..5] = « ABA » = motif. Toutes les lettres coïncident : occurrence trouvée à l'indice 3.
Position 5 : seconde occurrence
i = 4 : texte[4]='B' ≠ 'A', échec. i = 5 : texte[5..7] = « ABA » = motif : seconde occurrence à l'indice 5. Le coût au pire reste de l'ordre de n × m comparaisons.

Résultat : Le motif « ABA » apparaît aux indices 3 et 5. La recherche naïve a glissé d'une position à la fois ; Boyer-Moore, en comparant de droite à gauche, aurait pu sauter certaines de ces positions et faire moins de comparaisons.

Erreurs fréquentes

Croire que Boyer-Moore compare de gauche à droite : c'est l'inverse, la comparaison part de la fin du motif, et c'est précisément ce qui permet les grands décalages.
Penser que Boyer-Moore est toujours strictement plus rapide : son intérêt est statistique (sur de longs textes, alphabets variés). Sur des cas pathologiques, le coût peut rester élevé ; il faut parler d'efficacité en pratique.

Révision active

Rechercher le motif « EME » dans le texte « UN_EXEMPLE_ » par recherche naïve, en comptant les alignements et les comparaisons. Indiquer ensuite, avec Boyer-Moore, de combien on peut décaler le motif lorsque la comparaison de droite à gauche échoue sur un caractère absent du motif.

Rappel actif

Rappelle-toi les points clés — puis révèle.

Sources : Programme de spécialité NSI — classe terminale (voie générale), BO spécial n° 8 du 25 juillet 2019 (Ministère de l'Éducation nationale) · Programmes et ressources en numérique et sciences informatiques — voie générale (Éduscol)

Points clés

Reconnaître le schéma sur le calcul du maximum

Points clés

Tri fusion de [5, 2, 8, 1]

Recherche dichotomique de 40

Points clés

Du Fibonacci naïf au Fibonacci mémoïsé

Points clés

Rendre 6 avec le système {1, 3, 4}

Points clés

Recherche naïve du motif « ABA » dans « ABCABABA »

Sources

Diviser pour régner et programmation dynamique

Points clés

Reconnaître le schéma sur le calcul du maximum

Points clés

Tri fusion de [5, 2, 8, 1]

Recherche dichotomique de 40

Points clés

Du Fibonacci naïf au Fibonacci mémoïsé

Points clés

Rendre 6 avec le système {1, 3, 4}

Points clés

Recherche naïve du motif « ABA » dans « ABCABABA »

Sources