EazyReviz

L'essentiel en 30 secondes

Diviser pour régner $=$ décomposer un problème en $sous-problèmes$ indépendants, les résoudre récursivement, puis combiner $(ex$ : tri fusion). La programmation dynamique optimise les problèmes avec $sous-problèmes$ chevauchants en stockant les résultats déjà calculés (mémoïsation). La recherche textuelle naïve teste le motif $à$ chaque position du texte en $O(n\times m)$ .

Notions clés

Diviser pour régner: Paradigme en 3 étapes : diviser le problème, résoudre les sous-problèmes (récursion), combiner les solutions.
Tri fusion (merge sort): Divise la liste en deux moitiés, trie récursivement chaque moitié, fusionne les deux listes triées. O(n log n) garanti.
Programmation dynamique: Résout un problème en stockant les solutions des sous-problèmes (table ou mémoïsation) pour éviter les recalculs.
Mémoïsation: Version top-down de la programmation dynamique : on garde un cache (dict) des résultats déjà calculés.
Recherche textuelle naïve: Pour chaque position $i$ du texte, on compare caractère par caractère avec le motif. $O(n \times m)$ dans le pire cas.

Formules

Tri fusion

`def tri_fusion(lst):\n if len(lst) <= 1:\n return lst\n m = len(lst) // 2\n g = tri_fusion(lst[:m])\n d = tri_fusion(lst[m:])\n return fusion(g, d)\n\ndef fusion(g, d):\n res = []\n i = j = 0\n while i < len(g) and j < len(d):\n if g[i] <= d[j]:\n res.append(g[i]); i += 1\n else:\n res.append(d[j]); j += 1\n return res + g[i:] + d[j:]`

Condition : Complexité O(n log n) en temps, O(n) en espace auxiliaire

Fibonacci avec mémoïsation

`def fib(n, memo={}):\n if n <= 1:\n return n\n if n not in memo:\n memo[n] = fib(n-1, memo) + fib(n-2, memo)\n return memo[n]`

Condition : Sans mémo : O(2^n). Avec mémo : O(n). Gain considérable.

Recherche textuelle naïve

`def recherche(texte, motif):\n positions = []\n for i in range(len(texte) - len(motif) + 1):\n if texte[i:i+len(motif)] == motif:\n positions.append(i)\n return positions`

Condition : $O(n \times m)$ dans le pire cas, avec $n = len(texte)$ et $m = len(motif)$

A retenir

Diviser pour régner = sous-problèmes INDÉPENDANTS. Prog. dynamique = sous-problèmes CHEVAUCHANTS.
Le tri fusion est toujours en $O(n$ log $n)$ , contrairement au tri rapide qui est en $O(n^2)$ dans le pire cas.
La mémoïsation transforme un algorithme exponentiel en algorithme polynomial quand les sous-problèmes se recouvrent.

Erreurs classiques

Erreur : Confondre diviser pour régner et programmation dynamique

Correction : DPR : sous-problèmes indépendants (tri fusion). PD : sous-problèmes qui se chevauchent (Fibonacci).

Erreur : Oublier la fusion dans le tri fusion

Correction : Diviser ne suffit pas : il faut fusionner les sous-listes triées avec la fonction fusion() dédiée.

Erreur : Ne pas gérer la borne supérieure dans la recherche textuelle

Correction : La boucle va de 0 à len(texte) - len(motif), inclus. Sinon, dépassement d'indice.

Astuce méthode