Révisions Algorithmique : Techniques de Programmation

Diviser pour Régner

Diviser pour régner est une technique de conception d'algorithmes qui consiste à résoudre un problème en le divisant en sous-problèmes plus petits, plus faciles à résoudre. Les solutions des sous-problèmes sont ensuite combinées pour obtenir la solution du problème initial.

Les étapes principales de la technique "Diviser pour Régner" sont :

1. Diviser : Le problème initial est divisé en sous-problèmes plus petits de même nature.
2. Régner : Les sous-problèmes sont résolus récursivement. Si un sous-problème est suffisamment petit, il est résolu directement.
3. Combiner : Les solutions des sous-problèmes sont combinées pour obtenir la solution du problème initial.

Exemples de Diviser pour Régner

Quelques exemples classiques d'algorithmes qui utilisent la technique diviser pour régner :

• Tri fusion (Merge Sort) : Un tableau est divisé en deux moitiés, chaque moitié est triée récursivement, puis les deux moitiés triées sont fusionnées.
• Tri rapide (Quick Sort) : Un élément (pivot) est choisi dans le tableau. Le tableau est partitionné en deux sous-tableaux : les éléments inférieurs au pivot et les éléments supérieurs au pivot. Les sous-tableaux sont triés récursivement.
• Recherche dichotomique (Binary Search) : Un tableau trié est divisé en deux moitiés. Si l'élément recherché est inférieur à l'élément du milieu, la recherche continue dans la première moitié. Sinon, la recherche continue dans la deuxième moitié.

Exemple de code Python (Tri Fusion):

def tri_fusion(tableau):
  if len(tableau) <= 1:
    return tableau
  
  milieu = len(tableau) // 2
  gauche = tableau[:milieu]
  droite = tableau[milieu:]
  
  gauche = tri_fusion(gauche)
  droite = tri_fusion(droite)
  
  return fusionner(gauche, droite)


def fusionner(gauche, droite):
  resultat = []
  i, j = 0, 0
  while i < len(gauche) and j < len(droite):
    if gauche[i] <= droite[j]:
      resultat.append(gauche[i])
      i += 1
    else:
      resultat.append(droite[j])
      j += 1
      
  resultat += gauche[i:]
  resultat += droite[j:]
  return resultat

Programmation Dynamique

La programmation dynamique est une technique de conception d'algorithmes qui consiste à résoudre un problème en le décomposant en sous-problèmes qui se chevauchent, et en stockant les solutions de ces sous-problèmes pour éviter de les recalculer plusieurs fois.

La programmation dynamique est particulièrement utile pour les problèmes d'optimisation, où l'on cherche à trouver la meilleure solution parmi un ensemble de solutions possibles.

Deux approches principales sont utilisées en programmation dynamique :

• Approche descendante (mémoïsation) : On résout le problème récursivement, en stockant les résultats intermédiaires dans un tableau ou un dictionnaire pour éviter de les recalculer.
• Approche ascendante (tabulation) : On remplit un tableau de manière itérative, en calculant les solutions des sous-problèmes de plus en plus grands, jusqu'à obtenir la solution du problème initial.

Exemples de Programmation Dynamique

Quelques exemples classiques d'algorithmes qui utilisent la programmation dynamique :

• Suite de Fibonacci : Le calcul du n-ième nombre de Fibonacci peut être optimisé en stockant les nombres de Fibonacci déjà calculés.
• Problème du sac à dos : Trouver la combinaison d'objets de valeur maximale que l'on peut mettre dans un sac à dos de capacité limitée.
• Plus longue sous-séquence commune (Longest Common Subsequence, LCS) : Trouver la plus longue séquence d'éléments qui est une sous-séquence de deux séquences données.

Exemple de code Python (Suite de Fibonacci avec mémoïsation):

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

Exemple de code Python (Suite de Fibonacci avec tabulation):

def fibonacci_tabulation(n):
  tableau = [0] * (n+1)
  tableau[0] = 0
  tableau[1] = 1
  for i in range(2, n+1):
    tableau[i] = tableau[i-1] + tableau[i-2]
  return tableau[n]

Quand Utiliser Diviser pour Régner ou la Programmation Dynamique ?

Diviser pour régner est bien adapté aux problèmes qui peuvent être naturellement divisés en sous-problèmes indépendants. Chaque sous-problème est résolu indépendamment, ce qui rend cette technique adaptée aux architectures parallèles.

La programmation dynamique est plus adaptée aux problèmes où les sous-problèmes se chevauchent. En stockant les solutions des sous-problèmes, on évite de les recalculer, ce qui peut améliorer significativement l'efficacité de l'algorithme.

Le choix entre ces deux techniques dépend donc de la structure du problème à résoudre.

Ce qu'il faut retenir

• Diviser pour régner consiste à diviser un problème en sous-problèmes, à les résoudre récursivement et à combiner les solutions.
• Tri fusion, tri rapide et recherche dichotomique sont des exemples d'algorithmes "diviser pour régner".
• La programmation dynamique résout des problèmes en stockant les solutions des sous-problèmes qui se chevauchent.
• La mémoïsation (approche descendante) et la tabulation (approche ascendante) sont deux approches de la programmation dynamique.
• La suite de Fibonacci, le problème du sac à dos et la LCS sont des exemples d'algorithmes de programmation dynamique.