Algorithmique : recherche textuelle, programmation dynamique, diviser pour régner

Les notions à connaître

Diviser pour régner

Paradigme algorithmique en 3 étapes : (1) Diviser le problème en sous-problèmes indépendants plus petits, (2) Régner en résolvant récursivement chaque sous-problème, (3) Combiner les solutions. Ex : tri fusion, recherche dichotomique, exponentiation rapide.

Tri fusion (merge sort)

Divise la liste en deux moitiés, trie récursivement chaque moitié, fusionne les deux listes triées. Complexité TOUJOURS $O(n \log n)$ (meilleur, moyen et pire cas). Stable (préserve l'ordre des éléments égaux). Espace auxiliaire $O(n)$.

Programmation dynamique

Optimise les problèmes ayant des sous-problèmes chevauchants et une sous-structure optimale. Deux approches : top-down (mémoïsation avec cache) ou bottom-up (tabulation avec tableau). Évite les recalculs redondants.

Mémoïsation

Approche top-down de la prog. dynamique : on garde un dictionnaire (cache) des résultats déjà calculés. Avant de calculer f(n), on vérifie si f(n) est dans le cache. Transforme $O(2^n)$ en $O(n)$ pour Fibonacci.

Tabulation

Approche bottom-up de la prog. dynamique : on remplit un tableau du plus petit sous-problème au plus grand. Pas de récursion, donc pas de risque de RecursionError. Ex : tab[0]=0, tab[1]=1, tab[i]=tab[i-1]+tab[i-2].

Recherche textuelle naïve

Pour chaque position i du texte (de 0 à n-m), comparer le motif caractère par caractère. Complexité $O(n \times m)$ dans le pire cas (n=len(texte), m=len(motif)).

Algorithme de Boyer-Moore (simplifié)

Optimise la recherche textuelle en comparant le motif de droite à gauche et en sautant des positions grâce à une table de décalage. Complexité moyenne sous-linéaire $O(n/m)$.

Sous-structure optimale

Propriété clé de la prog. dynamique : la solution optimale du problème contient les solutions optimales des sous-problèmes. Ex : le plus court chemin de A à C passant par B = plus court $A \to$ B + plus court $B \to$ C.

Les erreurs à éviter en nsi

• ✗ Confondre diviser pour régner et programmation dynamique

  ✓ DPR : sous-problèmes indépendants (tri fusion). PD : sous-problèmes qui se chevauchent (Fibonacci). La PD stocke les résultats.

• ✗ Oublier la fusion dans le tri fusion

  ✓ Diviser ne suffit pas : il faut fusionner les sous-listes triées avec une fonction fusion() qui interclasse en $O(n)$.

• ✗ Ne pas gérer la borne supérieure dans la recherche textuelle

  ✓ La boucle va de 0 à len(texte) - len(motif) inclus. Sinon, on dépasse et on manque ou on crée une erreur.

• ✗ Utiliser l'approche gloutonne pour le rendu de monnaie avec un système non canonique

  ✓ Avec les pièces {1, 3, 4} pour rendre 6 : glouton donne 4+1+1 (3 pièces), optimal est 3+3 (2 pièces). Utiliser la PD.

• ✗ Oublier le cas de base dans le tri fusion : liste de taille 0 ou 1

  ✓ if len(lst) <= 1: return lst. Sans ce cas de base, la récursion ne s'arrête jamais.

Sais-tu répondre à ces questions ?

Les corrigés détaillés sont dans le quiz du chapitre.

1. Quelle est la complexité dans le pire cas de la recherche naïve d'un motif de taille m dans un texte de taille n ?
2. Quel est le principe fondamental de la programmation dynamique ?
3. Combien de fois le motif 'AB' apparaît-il dans le texte 'ABABCABAB' ?
4. On calcule la suite de Fibonacci avec programmation dynamique : def fi$b_dp(n):$ tab = [0] * (n + 1) tab[1] = 1 for i in range(2, n + 1): tab[i] = tab[i - 1] + tab[i - 2] return tab[n] Quelle est la complexité temporelle de cette approche ?
5. L'algorithme de Boyer-Moore améliore la recherche textuelle grâce à une heuristique. Quelle est son idée principale ?