⌨ Spécialité NSI · Numérique et sciences informatiques Terminale Générale · Chapitre 7

Programmation dynamique et recherche textuelle

Principe de la programmation dynamique (sous-problèmes qui se recoupent, mémoïsation, tableau ascendant), rendu de monnaie optimal, comptage de chemins ; recherche d'un motif dans un texte : algorithme naïf et algorithme de Boyer-Moore-Horspool.

1. Programmation dynamique

Définition

La programmation dynamique résout un problème en combinant les solutions de sous-problèmes qui se recoupent, chacun n'étant calculé qu'une seule fois : soit en mémorisant les résultats d'une fonction récursive (mémoïsation, approche descendante), soit en remplissant un tableau du plus petit au plus grand sous-problème (approche ascendante).

somme spièces min00112231415262pièces {1, 3, 4} : m(s) = 1 + min(m(s − 1), m(s − 3), m(s − 4))m(6) = 2 (3 + 3), là où le glouton donne 3 pièces (4 + 1 + 1)
Programmation dynamique : on remplit un tableau des solutions des sous-problèmes, du plus petit au plus grand.

Méthode · Rendu de monnaie optimal

def rendu_min(s, pieces):
    m = [0] + [float("inf")] * s
    for x in range(1, s + 1):
        for p in pieces:
            if p <= x and m[x - p] + 1 < m[x]:
                m[x] = m[x - p] + 1
    return m[s]

rendu_min(6, [1, 3, 4])   # 2

Contrairement à l'algorithme glouton, la programmation dynamique donne toujours le nombre minimal de pièces.

Exemple · Chemins dans une grille

Nombre de chemins de la case en haut à gauche à la case $(i, j)$ en n'allant qu'à droite ou en bas : $c(i, j) = c(i - 1, j) + c(i, j - 1)$, avec $c = 1$ sur la première ligne et la première colonne. Pour une grille $3 \times 3$ cases : $c(2, 2) = 6$.

2. Recherche textuelle

Propriété · Algorithme naïf

On place le motif (longueur $m$) à chaque position du texte (longueur $n$) et on compare caractère par caractère : jusqu'à environ $n \times m$ comparaisons.

LE␣CHAT␣CHANTECHANT↑ T ≠ ␣ (espace absent du motif) : décalage de 5CHANTtrouvé à la position 8 →
Recherche d'un motif (« CHANT ») : l'algorithme de Boyer-Moore compare de droite à gauche et décale le motif le plus possible.

Propriété · Boyer-Moore-Horspool

On compare le motif de droite à gauche ; en cas d'échec, on regarde le caractère du texte aligné avec la dernière lettre du motif et on décale le motif d'après une table de décalages pré-calculée (distance de la dernière occurrence de ce caractère à la fin du motif, ou longueur du motif s'il en est absent). On saute ainsi de nombreuses positions : l'algorithme est très rapide en pratique.

Activité · Table des décalages

MatérielPython.
ConsigneCalculer la table de décalages de Horspool pour le motif « CHANT ».
Résultat
def table(motif):
    m = len(motif)
    return {motif[i]: m - 1 - i for i in range(m - 1)}

table("CHANT")   # {'C': 4, 'H': 3, 'A': 2, 'N': 1}

Un caractère absent (par exemple « E ») donne un décalage de $5$.

BilanPlus le motif est long, plus les sauts sont grands : la recherche peut être plus rapide qu'une simple lecture du texte.

⚠️ Une erreur dans ce cours ? Signalez-la

S'entraîner

Exercices corrigés

🎓 20 exercices corrigés et un quiz vous attendent dans ce chapitre.

Créez votre compte gratuit pour voir les corrections, faire les quiz et suivre votre progression.

2

Remplir la table

★★☆

La table ci-dessous donne le nombre minimal de pièces $m(s)$ pour rendre la somme $s$ avec les pièces $\{1, 3, 4\}$, pour $s$ de $0$ à $6$. La compléter jusqu'à $s = 8$.

somme spièces min00112231415262pièces {1, 3, 4} : m(s) = 1 + min(m(s − 1), m(s − 3), m(s − 4))
Nombre minimal de pièces m(s) pour rendre la somme s avec les pièces {1, 3, 4}.
🔒 Correction réservée aux membres Créer un compte gratuit →
4

Exécuter rendu_min

★★☆

Que renvoie rendu_min(10, [1, 5, 6]) avec la fonction ci-dessous ? Que donnerait l'algorithme glouton (qui prend toujours la plus grande pièce possible) ?

def rendu_min(s, pieces):
    m = [0] + [float("inf")] * s
    for x in range(1, s + 1):
        for p in pieces:
            if p <= x and m[x - p] + 1 < m[x]:
                m[x] = m[x - p] + 1
    return m[s]
🔒 Correction réservée aux membres Créer un compte gratuit →
5

Retrouver les pièces

★★★

Comment modifier la fonction rendu_min ci-dessous pour connaître les pièces utilisées ?

def rendu_min(s, pieces):
    m = [0] + [float("inf")] * s
    for x in range(1, s + 1):
        for p in pieces:
            if p <= x and m[x - p] + 1 < m[x]:
                m[x] = m[x - p] + 1
    return m[s]
🔒 Correction réservée aux membres Créer un compte gratuit →
7

Chemins dans une grille

★★☆

Combien de chemins dans une grille de $4 \times 4$ cases pour aller de la case $(0,0)$ à la case $(3,3)$ en n'allant qu'à droite ou en bas ? (On pourra utiliser $c(i, j) = c(i - 1, j) + c(i, j - 1)$, avec $c = 1$ sur la première ligne et la première colonne.)

🔒 Correction réservée aux membres Créer un compte gratuit →
8

Programmer les chemins

★★★

Dans une grille, on va de la case $(0, 0)$ à la case $(i, j)$ en n'allant qu'à droite ou en bas ; le nombre de chemins vérifie $c(i, j) = c(i - 1, j) + c(i, j - 1)$, avec $c = 1$ sur la première ligne et la première colonne. Écrire une fonction chemins(n, p) qui renvoie le nombre de chemins jusqu'à la case $(n - 1, p - 1)$.

🔒 Correction réservée aux membres Créer un compte gratuit →
9

Coût

★★☆

Quel est le coût de rendu_min(s, pieces) ci-dessous avec $k$ pièces ?

def rendu_min(s, pieces):
    m = [0] + [float("inf")] * s
    for x in range(1, s + 1):
        for p in pieces:
            if p <= x and m[x - p] + 1 < m[x]:
                m[x] = m[x - p] + 1
    return m[s]
🔒 Correction réservée aux membres Créer un compte gratuit →
12

Table de décalages

★★☆

Calculer la table de Horspool pour le motif « RIRE » (pour chaque lettre du motif sauf la dernière, le décalage est la distance de sa dernière occurrence à la fin du motif ; un caractère absent donne un décalage égal à la longueur du motif).

🔒 Correction réservée aux membres Créer un compte gratuit →
14

Lecture de la figure

★★☆

On cherche le motif « CHANT » dans le texte « LE CHAT CHANTE » avec l'algorithme de Boyer-Moore-Horspool (comparaison de droite à gauche). Dans la figure ci-dessous, pourquoi le motif est-il décalé de $5$ positions d'un coup ?

LE␣CHAT␣CHANTECHANT↑ première comparaison : T face à ␣CHANTaprès un décalage de 5 →
Recherche du motif « CHANT » dans « LE CHAT CHANTE » : position du motif avant et après le décalage.
🔒 Correction réservée aux membres Créer un compte gratuit →
19

Triangle de Pascal

★★☆

Dans une grille, on note $c(i, j)$ le nombre de chemins de la case $(0, 0)$ à la case $(i, j)$ en n'allant qu'à droite ou en bas : $c(i, j) = c(i - 1, j) + c(i, j - 1)$, avec $c = 1$ sur la première ligne et la première colonne. Quel lien avec le triangle de Pascal ?

🔒 Correction réservée aux membres Créer un compte gratuit →
20

Vrai ou faux

★★☆

a) La programmation dynamique recalcule les sous-problèmes. b) Boyer-Moore compare de droite à gauche. c) La recherche naïve peut coûter $n \times m$ comparaisons.

🔒 Correction réservée aux membres Créer un compte gratuit →

Vérifier

Avez-vous bien compris ?

Répondez au quiz : la correction s'affiche immédiatement.