Complexité Algorithmique: Algorithme Glouton et Programmation Dynamique

Ce document traite des concepts fondamentaux de la complexité algorithmique, en se concentrant sur deux méthodes principales : l’algorithme glouton et la programmation dynamique. Il s’adresse aux étudiants en informatique ou en mathématiques appliquées souhaitant comprendre ces techniques pour résoudre des problèmes d’optimisation.

Algorithme Glouton : Principe

L’algorithme glouton construit progressivement une solution en faisant à chaque étape un choix qui semble optimal localement. Dans certains cas, cette méthode conduit à la solution optimale globale, on parle alors d’algorithmes gloutons exacts. Dans d’autres cas, elle fournit une solution approchée, appelée heuristique gloutonne.

Exemple : Rendre la monnaie avec un algorithme glouton

Considérons un ensemble de pièces de monnaie avec des valeurs {a0, a1, ..., an−1} telles que 1 = a0 < a1 < ... < an−1. Le nombre de pièces de chaque valeur est illimité. Le problème est de rendre une somme c avec un nombre minimal de pièces.

La solution gloutonne consiste à prendre autant que possible la pièce de plus grande valeur inférieure ou égale à la somme restante, puis à répéter avec la somme restante.

Exemple : Gestion des films dans un cinéma

Un cinéma possède s salles et propose chaque semaine une liste de films, chacun défini par une date de début di, une date de fin fi, et un numéro de salle numSi. Un amateur souhaite voir le maximum de films compatibles (c’est-à-dire dont les intervalles ne se chevauchent pas).

Le problème est de sélectionner le plus grand nombre de films compatibles.

Modélisation

• A = {a1, a2, ..., an} : tableau des films
• Chaque film ai est caractérisé par di (date début), fi (date fin), numSi (numéro de salle)
• Deux films ai et aj sont compatibles si dj ≥ fi ou di ≥ fj

Algorithme glouton pour le choix des films

public Film[] choixFilm(Film[] A) {
  Film[] M; // films sélectionnés
  trier(A); // trier selon date de fin fi croissante
  M[0] = A[0];
  int nbfilm = 1;
  int i = 1;
  while (i < A.length) {
    if (A[i].d >= M[nbfilm - 1].f) {
      M[nbfilm] = A[i];
      nbfilm++;
    }
    i++;
  }
  return M;
}

On trie les films par date de fin croissante, puis on sélectionne successivement les films compatibles avec le dernier film choisi.

Cadre général d’un algorithme glouton

• Trouver un critère objectif clair
• Définir un critère de sélection localement optimal
• Implémenter l’algorithme, généralement simple et efficace

Programmation Dynamique : Principe

La programmation dynamique est une méthode d’optimisation introduite par Bellman dans les années 50, adaptée de la méthode diviser pour régner. Elle consiste à résoudre un problème en décomposant celui-ci en sous-problèmes interdépendants, en calculant les solutions de bas en haut (bottom-up) et en mémorisant les résultats pour éviter les calculs redondants.

Différence avec diviser pour régner

• Diviser pour régner : calculs récursifs de haut en bas
• Programmation dynamique : calculs itératifs de bas en haut

Étapes de la programmation dynamique

1. Obtenir une équation récursive liant la solution du problème à celles des sous-problèmes
2. Initialiser une table selon les conditions initiales de l’équation
3. Remplir la table en résolvant les sous-problèmes de taille croissante

Exemple : Suite de Fibonacci

La suite de Fibonacci est définie par :

F(0) = 1, F(1) = 1 et F(n) = F(n − 1) + F(n − 2)

Solution récursive (complexité exponentielle O(2^n))

public int Fibo(int n) {
  if (n <= 1)
    return 1;
  else
    return Fibo(n-1) + Fibo(n-2);
}

Solution itérative avec programmation dynamique (complexité O(n))

public int Fib(int n) {
  int[] F = new int[n+1];
  F[0] = 1; 
  F[1] = 1;
  for (int i = 2; i <= n; i++)
    F[i] = F[i-1] + F[i-2];
  return F[n];
}

Exemple : Nombre de combinaisons possibles

Le nombre de combinaisons de k éléments parmi n, noté C(n, k), peut être calculé par la relation :

C(n, k) = C(n−1, k−1) + C(n−1, k)

avec les conditions initiales :

• C(n, 0) = 1
• C(n, n) = 1

Solution récursive (complexité exponentielle O(2^n))

int function Combinaison(int n, int k) {
  if (k == 0 || k == n)
    return 1;
  else
    return Combinaison(n-1, k-1) + Combinaison(n-1, k);
}

Solution avec programmation dynamique (complexité O(nk))

int function Combinaison(int n, int k) {
  int B[][] = new int[n+1][k+1];
  for (int i = 0; i <= n; i++) {
    for (int j = 0; j <= Math.min(i, k); j++) {
      if (j == 0 || j == i)
        B[i][j] = 1;
      else
        B[i][j] = B[i-1][j-1] + B[i-1][j];
    }
  }
  return B[n][k];
}

Exercice : Calcul de la puissance d’un nombre

1. Écrire une fonction itérative puissanceIterative(a, n) qui calcule a^n en utilisant uniquement les opérateurs simples (+, −, *, /).
2. Écrire une fonction récursive puissanceRecursive(a, n) qui calcule a^n.
3. Comparer la complexité asymptotique des deux fonctions et déterminer laquelle est la plus performante.
4. Proposer une fonction puissanceDynamique(a, n) utilisant la programmation dynamique, basée sur la décomposition :

an = a^(n/2) * a^(n/2) si n est pair
an = a * a^(n-1) sinon
a^0 = 1
a^1 = a

5. Déterminer la complexité asymptotique de cette nouvelle fonction.

Glossaire des termes clés

• Algorithme glouton : méthode qui construit une solution en faisant à chaque étape le choix localement optimal.
• Programmation dynamique : méthode d’optimisation qui résout un problème en décomposant en sous-problèmes, en mémorisant les résultats pour éviter les calculs redondants.
• Diviser pour régner : méthode récursive qui divise un problème en sous-problèmes indépendants, résolus de haut en bas.
• Complexité exponentielle : complexité qui croît de façon exponentielle avec la taille de l’entrée, souvent notée O(2^n).
• Complexité linéaire : complexité proportionnelle à la taille de l’entrée, notée O(n).
• Sous-problème : problème plus petit issu de la décomposition d’un problème plus grand.
• Heuristique : méthode approximative qui ne garantit pas toujours la solution optimale.
• Équation récursive : relation qui exprime la solution d’un problème en fonction des solutions de ses sous-problèmes.

Points clés à retenir

• L’algorithme glouton est simple et efficace lorsque le choix local optimal conduit à la solution globale optimale.
• La programmation dynamique est adaptée aux problèmes où les sous-problèmes se recoupent et où la solution peut être construite de bas en haut.
• La programmation dynamique permet d’éviter les calculs redondants en mémorisant les résultats intermédiaires.
• La complexité des solutions récursives naïves est souvent exponentielle, alors que la programmation dynamique réduit cette complexité.
• La programmation dynamique nécessite l’identification d’une équation récursive et l’organisation des calculs dans une table.
• Les exemples classiques incluent la suite de Fibonacci et le calcul des combinaisons.