Aller au contenu principal

Stratégies fondamentales

Progression

#Stratégies fondamentales de l’algorithmique

La plupart des algorithmes qui jalonnent un cursus d’informatique relèvent de trois grandes stratégies : diviser pour régner, l’approche gloutonne et la programmation dynamique. Ce chapitre détaille chacune d’elles en partant d’un exemple concret, puis en identifiant les conditions qui garantissent leur efficacité.

#1. Diviser pour régner

Tri fusion, multiplication de Karatsuba, transformée de Fourier rapide… Tous partagent la même structure :

  1. Diviser le problème en sous-problèmes de taille comparable.
  2. Résoudre récursivement chaque sous-problème.
  3. Combiner les solutions partielles.

Nous analysons tri fusion étape par étape. La récurrence obtenue (T(n) = 2 T(n/2) + n) est résolue avec le Master theorem pour montrer la complexité O(n log n). L’atelier invite à implémenter tri fusion en limitant les allocations (buffer partagé) et à comparer empiriquement avec tri insertion sur de petits tableaux presque triés : l’occasion de discuter des cas où diviser pour régner n’est pas la meilleure option.

#2. Algorithmes gloutons

Un algorithme glouton choisit, à chaque étape, l’option localement optimale en espérant qu’elle est compatible avec l’optimum global. Cette stratégie échoue souvent si la structure sous-jacente ne la soutient pas ; elle réussit en revanche sur des problèmes qui admettent une structure de matroïde ou qui vérifient la propriété d’échange. Nous étudions trois cas : l’ordonnancement d’intervalles (triées par échéance croissante), l’arbre de Huffman et l’algorithme de Prim pour les arbres couvrants de poids minimum. Chaque exemple illustre comment prouver que la stratégie gloutonne est sûre (argument d’échange) et comment l’implémenter efficacement (tas binaire pour Prim, file de priorité pour Huffman).

#3. Programmation dynamique

La dynamique résout des problèmes par décomposition en sous-problèmes qui se chevauchent. Le sac à dos 0/1 sert d’introduction : nous dérivons la relation de récurrence, construisons un tableau 2D, puis optimisons l’espace en travaillant sur une seule dimension. Nous abordons ensuite un exemple sur les graphes (plus court chemin avec Bellman-Ford) et un exemple de biologie (alignement de séquences). Chaque fois, nous insistons sur la phase d’analyse préalable : identifier le paramètre d’état, clarifier l’ordre de remplissage et prouver la correction en s’appuyant sur l’invariant du tableau.

#Atelier

  1. Mettez en œuvre la programmation dynamique sur Knapsack puis optimisez l’empreinte mémoire en n’utilisant qu’un tableau 1D.
  2. Comparez Dijkstra (glouton) et Bellman-Ford (dynamique) sur un graphe dense et sur un graphe clairsemé ; tracez le nombre d’itérations et de relaxations pour alimenter la discussion.
  3. Pour le tri fusion, implémentez une version in place en limitant les copies et mesurez l’impact sur le temps d’exécution.

En maîtrisant ces trois stratégies, vous disposez d’un vocabulaire algorithmique complet. Le reste du module réinvestit ces techniques pour analyser la complexité et comparer les performances des différentes solutions.