#Stratégies algorithmiques fondamentalesCopier le lien

Prérequis: récursion et récurrences (Master Theorem), tris (chapitre précédent), notations O/Θ.

Objectifs:

• Identifier le paradigme adapté à un problème nouveau, avec des critères décidables.
• Énoncer pour chaque paradigme ce qui doit être prouvé pour garantir l'optimalité.
• Connaître les exemples canoniques et la structure de leurs preuves.

Un algorithme résout un problème; un paradigme est une manière de construire la solution. Trois grands paradigmes couvrent l'essentiel des algorithmes efficaces, et chacun a sa condition d'application, qui se vérifie plutôt qu'elle ne se devine.

#Diviser pour régnerCopier le lien

#SchémaCopier le lien

1. Diviser l'instance en sous-instances plus petites.
2. Régner: résoudre récursivement chaque sous-instance (cas de base pour les petites).
3. Combiner les solutions partielles.

Coût générique:

où a est le nombre de sous-problèmes, n/b leur taille, f(n) le coût de division et combinaison. Le Master Theorem tranche (voir chapitre Complexité des algorithmes).

Condition d'application: les sous-problèmes sont indépendants (aucun chevauchement). C'est ce qui distingue ce paradigme de la programmation dynamique.

#Exemples canoniquesCopier le lien

• Tri fusion: a = 2, b = 2, f(n) = Θ(n) → Θ(n log n). La combinaison (fusion) fait tout le travail.
• Recherche binaire: a = 1, b = 2, f(n) = Θ(1) → Θ(log n). On ne suit qu'une seule branche.
• Karatsuba (grands entiers): découpe chaque nombre en deux moitiés; la méthode scolaire (4 produits) se remplace par 3 produits bien choisis: a = 3, b = 2 → Θ(n^(log₂ 3)) ≈ Θ(n^(1.58)), mieux que Θ(n²).
• Strassen (matrices): 7 produits au lieu de 8: a = 7, b = 2 → Θ(n^(log₂ 7)) ≈ Θ(n^(2.81)), battant le Θ(n³) scolaire. En pratique, les constantes ne le rendent rentable que pour de grandes matrices.

#Trace: recherche binaire dans [1, 2, ..., 100], cible 73Copier le lien

Invariant: la cible, si présente, est toujours dans l'intervalle courant. Six comparaisons, soit ⌈log₂ 100⌉ = 7 au plus: chaque test divise l'espace par deux.

#Algorithmes gloutonsCopier le lien

#SchémaCopier le lien

Construire la solution pas à pas: à chaque étape, faire le choix localement optimal selon un critère, et ne jamais revenir dessus.

Le paradigme est séduisant parce qu'il est simple et rapide. Il est correct uniquement sous deux conditions à prouver:

1. Propriété du choix glouton: il existe une solution optimale qui commence par le choix glouton. (Preuve type: argument d'échange: partir d'une solution optimale et y substituer le choix glouton sans dégrader le coût.)
2. Sous-structure optimale: une fois le choix glouton fait, le reste de la solution optimale est une solution optimale du sous-problème restant.

Sans ces preuves, un glouton est une heuristique: il peut être faux, pas seulement lent.

#Contre-exemple: rendu de monnaieCopier le lien

Avec les pièces européennes 200, rendre toujours la plus grande pièce possible est optimal. Avec 4 et 6 à rendre: le glouton donne 4 + 1 + 1 (trois pièces), l'optimal est 3 + 3 (deux pièces). Même stratégie, système différent: l'optimalité n'appartient pas à l'algorithme mais au couple (algorithme, système), d'où l'obligation de la preuve.

#Exemples canoniques prouvésCopier le lien

• Sélection d'activités: parmi des activités qui se chevauchent, maximiser le nombre d'activités retenues. Glouton: prendre celle qui termine le plus tôt, retirer les incompatibles, répéter. Preuve par échange: toute solution optimale peut voir sa première activité remplacée par celle qui finit plus tôt sans rien casser.
• Huffman: fusionner itérativement les deux symboles de plus faible fréquence; optimal pour le codage préfixe sans perte.
• Kruskal (arbre couvrant minimal): ajouter l'arête de poids minimal qui ne crée pas de cycle. Prouvé par la propriété de coupe.
• Ordonnancement pour minimiser le retard: trier les tâches par date limite croissante.

#Trace: sélection d'activitésCopier le lien

#Programmation dynamiqueCopier le lien

#SchémaCopier le lien

1. Identifier des sous-problèmes qui se chevauchent (le même sous-problème revient plusieurs fois dans la récursion naïve).
2. Définir la valeur d'une solution optimale récursivement sur ces sous-problèmes (sous-structure optimale).
3. Calculer chaque sous-problème une seule fois: de haut en bas avec mémoïsation, ou de bas en haut en remplissant une table.
4. Reconstruire la solution (pas seulement sa valeur) en relisant la table si besoin.

Condition d'application: sous-problèmes chevauchants et sous-structure optimale. Sans chevauchement, c'est du diviser pour régner, et la table n'apporte rien.

#Différence avec diviser pour régnerCopier le lien

#Trace: Fibonacci, l'implémentation naïveCopier le lien

, et l'arbre d'appels de F(5):

1                    F(5)2                  /      \3              F(4)        F(3)4             /    \      /    \5          F(3)  F(2)  F(2)  F(1)6          /  \   ...   ...7       F(2) F(1)

F(3) est calculé deux fois, F(2) trois fois, et le phénomène s'amplifie: le coût naïf est (φ ≈ 1.618), exponentiel, alors qu'il n'existe que n sous-problèmes distincts.

Mémoïsation (top-down): chaque F(k) n'est calculé qu'une fois, les suivants se servent du cache: O(n) temps, O(n) espace pour le cache et la pile.

1def fib_memo(n, memo=None):2    if memo is None:3        memo = {0: 0, 1: 1}4    if n not in memo:5        memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)6    return memo[n]

Bottom-up (tabulaire), puis optimisation d'espace: seuls les deux derniers états servent.

1def fib_iter(n):2    a, b = 0, 13    for _ in range(n):4        a, b = b, a + b5    return a                # O(n) temps, O(1) espace

Même récurrence, deux ordres de calcul, un seul sous-problème par valeur de k: c'est tout le paradigme.

#Exemples canoniquesCopier le lien

Sac à dos 0/1. Objets avec poids et valeurs , capacité W. Sous-problème: = meilleure valeur avec les i premiers objets et capacité w.

prendre ou ne pas prendre l'objet i. Table (n+1) × (W+1): O(nW) temps et espace, O(W) espace si l'on ne garde qu'une ligne. Ce coût est dit pseudo-polynomial: il est polynomial en la valeur numérique de W, exponentiel en le nombre de chiffres de W; c'est ce détail qui empêche le sac à dos d'être dans P au sens de la théorie des problèmes, alors qu'il se résout bien en pratique pour des capacités raisonnables.

Plus longue sous-séquence commune (LCS).

Table n × m: O(nm) temps et espace. De git diff à la comparaison d'ADN.

Distance d'édition (Levenshtein). Minimum d'insertions, suppressions, substitutions pour transformer une chaîne en une autre: même table que LCS, récurrence enrichie du cas substitution. O(nm).

Sous-séquence croissante maximale (LIS/PMI). Récurrence directe en O(n²); avec une structure auxiliaire (table des queues par longueur, recherche dichotomique), O(n log n).

#Comparaison des paradigmesCopier le lien

#Exercice 1: monnaie, quand le glouton échoueCopier le lien

Soit le système 10. Rendez 14 avec le glouton (plus grande pièce d'abord), puis optimalement. Prouvez que le résultat glouton n'est pas optimal, et donnez la table DP qui conduit à l'optimum.

Correction: glouton: 10 + 1 + 1 + 1 + 1 = 14 en cinq pièces. Optimal: 7 + 7, deux pièces. Le glouton n'est pas optimal: solution exhibée, contre-exemple suffit (inutile de chercher une preuve générale là où un contre-exemple tranche). Table DP M[w] = nombre minimal de pièces pour w, , M[0] = 0: M[14] = 1 + min(M[13], M[7], M[4]) = 1 + min(5, 1, 4) = 2, atteint par deux pièces de 7. La table explore tous les systèmes de pièces d'un coup: c'est la robustesse de la DP contre le caractère exact du glouton qui dépend du système.

#Exercice 2: nombre de chemins dans une grilleCopier le lien

Une grille n × m, on part d'en haut à gauche et on avance uniquement vers la droite ou vers le bas. Comptez les chemins vers en bas à droite: (a) par récursion naïve, (b) par DP. Comparez les coûts.

Correction: soit C(i, j) le nombre de chemins de (i, j) vers l'arrivée: , avec C = 1 sur la dernière ligne et la dernière colonne (un seul chemin tout droit). (a) La récursion naïve recalcule massivement les mêmes cases; le nombre d'appels suit le nombre de chemins eux-mêmes, exponentiel (de l'ordre de ). (b) Chaque case ne dépend que de deux voisines déjà calculées si l'on remplit depuis l'arrivée: table n × m remplie en O(nm), chaque cellule en O(1). Les deux retournent le même entier (vérifiable sur des petites grilles: 3 × 3 donne 6 chemins: ): correction identique, complexités exponentiellement différentes. C'est l'exemple le plus net du chapitre: mêmes sous-problèmes, avec ou sans table, deux mondes de coût.