⌨ 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).

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.

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.

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.

Créer un compte gratuit Se connecter