Loading
Loading
Ce thème compare trois grandes stratégies algorithmiques au programme de terminale. « Diviser pour régner » découpe un problème en sous-problèmes indépendants (tri fusion, recherche dichotomique) ; la programmation dynamique mémorise les sous-problèmes qui se chevauchent (Fibonacci mémoïsé, rendu de monnaie) ; la recherche textuelle localise un motif dans un texte, l'algorithme de Boyer-Moore accélérant la recherche naïve par des décalages. L'objectif central est d'écrire ces algorithmes et de comparer leur coût.
5sectionsca. 22min de lecture4compétencesNiveauBase 1 · Standard 3 · Approfondissement 1Vérifié · 06/2026
Lesetiefe: Approfondi
Schriftgröße: Standard
Le triptyque diviser / régner / combiner
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.
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].
Si le tableau contient un seul élément, le maximum est cet élément : on le renvoie directement, sans division.
On coupe le tableau en deux moitiés de tailles aussi égales que possible : gauche = [3, 9] et droite = [1, 7].
On calcule récursivement le maximum de chaque moitié. max([3, 9]) = 9 et max([1, 7]) = 7.
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
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 : arbre de division puis de fusion
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.
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
Coût comparé : tri fusion (n log n) contre tri naïf (n²)
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.
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.
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.
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.
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.
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.
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.
On recommence avec g = 4, d = 6, m = (4+6)//2 = 5. On compare 40 à t[5] = 40 : égalité.
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
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)
Sous-problèmes qui se chevauchent et mémoïsation
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)).
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)
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.
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.
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.
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.
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.
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.
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.
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.
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
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 : table dynamique et échec du glouton
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.
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.
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.
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.
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.
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
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)
Boyer-Moore : comparaison de droite à gauche et décalage
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.
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.
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.
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.
i = 3 : texte[3..5] = « ABA » = motif. Toutes les lettres coïncident : occurrence trouvée à l'indice 3.
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
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)
Références et sources