Algorithmique : recherche textuelle, programmation dynamique, diviser pour régner
L'essentiel en 30 secondes
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 (meilleur, moyen et pire cas). Stable (préserve l'ordre des éléments égaux). Espace auxiliaire .
- 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 en 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é dans le pire cas (n=len(texte), m=len(motif)).
- Algorithme de Boyer-Moore (simplifié)
- Recherche un motif en le comparant au texte de droite à gauche. Le motif est d'abord prétraité, une seule fois : pour chaque caractère du motif sauf le dernier, on note la distance entre sa dernière occurrence et la fin du motif (table de décalage). Après chaque essai, on lit le caractère du texte placé en face de la dernière lettre du motif et on décale le motif d'autant (de toute la longueur du motif si ce caractère n'est pas dans la table). C'est la version simplifiée, dite de Horspool. L'étude du coût n'est pas exigible ; en pratique, on fait souvent bien moins de comparaisons qu'avec la recherche naïve.
- 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 B + plus court 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 .
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.
- 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 ?
- Quel est le principe fondamental de la programmation dynamique ?
- Combien de fois le motif 'AB' apparaît-il dans le texte 'ABABCABAB' ?
- On calcule la suite de Fibonacci avec programmation dynamique : def fi 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 ?
- L'algorithme de Boyer-Moore améliore la recherche textuelle grâce à une heuristique. Quelle est son idée principale ?
Et maintenant ?
Lire ne suffit pas : c'est en cherchant qu'on retient.
Cette fiche fait partie d'EazyReviz Pro
La fiche complète de ce chapitre est réservée aux abonnés Pro. Crée d'abord ton compte gratuit : il ouvre les premiers chapitres de chaque matière.