Aller au contenu principal

Stratégies fondamentales

Progression

#title: "Stratégies algorithmiques fondamentales" description: "Diviser pour régner, algorithmes gloutons, programmation dynamique"

#Stratégies algorithmiques fondamentales

Au-delà des algorithmes spécifiques, il existe des paradigmes généraux qui guident la conception de solutions efficaces. Maîtriser ces stratégies permet d'aborder méthodiquement des problèmes nouveaux.

#Diviser pour régner

#Principe

La stratégie diviser pour régner (divide and conquer) consiste à :

  1. Diviser le problème en sous-problèmes plus petits
  2. Régner en résolvant récursivement les sous-problèmes
  3. Combiner les solutions des sous-problèmes

#Schéma de récurrence

La complexité suit généralement une récurrence :

où = nombre de sous-problèmes, = facteur de division.

#Exemples classiques

Tri fusion :

  • Divise en 2 parties égales
  • Combine en

Recherche binaire :

  • Divise en 2, résout un seul sous-problème

Multiplication de Karatsuba : Multiplier deux nombres de chiffres en au lieu de .

Algorithme de Strassen : Multiplication matricielle en au lieu de .

#Algorithmes gloutons

#Principe

Un algorithme glouton (greedy) construit une solution pas à pas, faisant à chaque étape le choix localement optimal sans revenir en arrière.

#Quand ça marche ?

Un algorithme glouton est correct si :

  1. Propriété de choix glouton : Un choix optimal local fait partie d'une solution optimale globale
  2. Sous-structure optimale : La solution optimale contient des solutions optimales des sous-problèmes

#Exemples classiques

Problème du rendu de monnaie : Avec le système européen 200 cents, on rend toujours la plus grande pièce possible.

Attention : Ne fonctionne pas avec tous les systèmes ! Contre-exemple : 4 pour rendre 6 cents.

Algorithme de Huffman : Compression optimale en fusionnant toujours les deux nœuds les moins fréquents.

Algorithme de Kruskal : Arbre couvrant de poids minimum : ajouter l'arête de poids minimum qui ne crée pas de cycle.

Ordonnancement : Minimiser le retard total : trier les tâches par date limite croissante.

Problème de sélection d'activités

Maximiser le nombre d'activités compatibles (qui ne se chevauchent pas).

Étape 1 / 4

#Programmation dynamique

#Principe

La programmation dynamique résout un problème en :

  1. Identifiant des sous-problèmes qui se chevauchent
  2. Stockant leurs solutions pour éviter les recalculs
  3. Combinant les solutions de manière bottom-up ou top-down

#Différence avec diviser pour régner

| Diviser pour régner | Programmation dynamique | |---------------------|-------------------------| | Sous-problèmes disjoints | Sous-problèmes chevauchants | | Pas de mémoïsation | Mémoïsation essentielle | | Top-down naturel | Bottom-up ou top-down |

#Méthodologie

  1. Caractériser la structure d'une solution optimale
  2. Définir récursivement la valeur d'une solution optimale
  3. Calculer la valeur bottom-up (ou top-down avec mémoïsation)
  4. Reconstruire la solution si nécessaire

#Exemple : Fibonacci

Approche naïve récursive :

Avec mémoïsation :

pythonpython
1def fib_memo(n, memo={}):2    if n in memo:3        return memo[n]4    if n <= 1:5        return n6    memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)7    return memo[n]

Bottom-up tabulaire : temps, espace

pythonpython
1def fib_iter(n):2    if n <= 1:3        return n4    a, b = 0, 15    for _ in range(n - 1):6        a, b = b, a + b7    return b

#Problèmes classiques

Sac à dos (Knapsack) :

Complexité : où = capacité (pseudo-polynomial).

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

Distance d'édition (Levenshtein) :

Minimum d'insertions, suppressions, substitutions pour transformer une chaîne en une autre.

#Comparaison des paradigmes

| Critère | Diviser/Régner | Glouton | Prog. Dynamique | |---------|----------------|---------|-----------------| | Sous-problèmes | Disjoints | Un seul | Chevauchants | | Optimalité | Garantie | À prouver | Garantie | | Implémentation | Récursive | Itérative | Tableau ou récursion | | Complexité | Souvent O(n log n) | Souvent O(n log n) | Souvent O(n²) ou O(nW) |

#Exercices

  1. Appliquez le paradigme diviser pour régner au problème du maximum d'un sous-tableau (Kadane).
  2. Prouvez que l'algorithme glouton pour le problème des intervalles est optimal.
  3. Implémentez le problème du sac à dos 0/1 par programmation dynamique.