Fiche de révision : diviser pour régner, programmation dynamique et graphes

Les coûts à savoir citer, avec leur condition

• • Recherche dichotomique : tableau TRIÉ obligatoire, $\lfloor \log_{2} n \rfloor + 1$ comparaisons, soit 10 pour mille éléments.
• • Tri fusion : $n \log_{2} n$ GARANTI, stable, mais mémoire supplémentaire linéaire.
• • Tri rapide, en approfondissement : $n \log_{2} n$ EN MOYENNE, $n^{2}$ au pire, en place, non stable. Au programme, l'exemple de diviser pour régner est le tri fusion.
• • Parcours de graphe : $O(n + m)$ avec des listes d'adjacence, $O(n^{2})$ avec une matrice.

Dans une question de coût, écrire la condition en même temps que le résultat : « $n \log_{2} n$ en moyenne » vaut le point, « $n \log_{2} n$ » seul ne le vaut pas toujours.

Lire une récurrence de coût

• • La récurrence se lit sur l'algorithme : combien d'appels, sur quelle taille, plus quel travail de recombinaison.
• • $C(n) = 2C(n/2) + n$ décrit le tri fusion : deux moitiés, plus une fusion linéaire, d'où $n \log_{2} n$.
• • $C(n) = C(n/2) + 1$ décrit la dichotomie : une seule moitié, plus une comparaison, d'où $\log_{2} n$.
• • Méthode de l'arbre : au niveau $k$ il y a $a^{k}$ sous-problèmes de taille $n/b^{k}$ ; on somme le travail par niveau, puis on multiplie par le nombre de niveaux.

Glouton, dynamique, et ce qui les sépare

• • Un algorithme GLOUTON fait le choix localement le meilleur et ne revient jamais dessus. Il est rapide et souvent FAUX.
• • Un glouton doit être DÉMONTRÉ : sans preuve, il n'est qu'une heuristique, et le sujet demande un contre-exemple.
• • La programmation dynamique s'applique quand le problème vérifie le PRINCIPE D'OPTIMALITÉ : une solution optimale est faite de solutions optimales de ses sous-problèmes.
• • Elle range chaque valeur dans une table remplie de bas en haut, ce qui garantit que chaque sous-problème n'est résolu qu'une fois.

Le sac à dos, et son coût trompeur

• • Relation : $V(i, c) = \max(V(i-1, c),\ v_{i} + V(i-1, c - p_{i}))$ quand l'objet $i$ tient dans la capacité $c$, et $V(i-1, c)$ sinon.
• • La table a $n$ lignes et $C+1$ colonnes : le coût est $nC$.
• • Ce coût est PSEUDO-POLYNOMIAL : il dépend de la VALEUR de la capacité, pas seulement du nombre d'objets, alors que la capacité s'écrit avec $\log_{2} C$ bits.
• • La reconstruction de la solution se lit à rebours dans la table, en comparant chaque case à celle du dessus.

Pour aller plus loin, hors programme : Dijkstra

• • Le programme demande de parcourir un graphe, d'y repérer un cycle et d'y chercher un chemin ; il ne nomme pas l'algorithme de Dijkstra, qui n'est pas exigible. Il éclaire le routage OSPF.
• • À chaque tour, on sélectionne le sommet NON TRAITÉ de plus petite distance provisoire, jamais le voisin le plus proche du dernier sommet traité.
• • On relâche ensuite chaque arête sortante : si passer par le sommet choisi raccourcit, on met à jour la distance et le prédécesseur.
• • Les poids doivent être POSITIFS : un poids négatif peut améliorer un sommet déjà traité, ce que l'algorithme n'envisage plus.
• • Un sujet qui présente un poids négatif attend seulement le refus motivé : l'algorithme ne réexamine jamais un sommet déjà fixé.