Décomposition d’un problème en sous-problèmes

Notions	Commentaires
Algorithme glouton fournissant une solution exacte.	On peut traiter comme exemples d’algorithmes exacts : codage de Huffman, sélection d’activité, ordonnancement de tâches unitaires avec pénalités de retard sur une machine unique.
Exemple d’algorithme d’approximation fourni par la méthode gloutonne.	On peut traiter par exemple : couverture des sommets dans un graphe, problème du sac à dos en ordonnant les objets.
Diviser pour régner. Rencontre au milieu. Dichotomie.	On peut traiter un ou plusieurs exemples comme : tri par partition-fusion, comptage du nombre d’inversions dans une liste, calcul des deux points les plus proches dans une ensemble de points; recherche d’un sous-ensemble d’un ensemble d’entiers dont la somme des éléments est donnée; recherche dichotomique dans un tableau trié. On présente un exemple de dichotomie où son recours n’est pas évident : par exemple, la couverture de 𝑛 points de la droite par 𝑘 segments égaux de plus petite longueur.
Programmation dynamique. Propriété de sous-structure optimale. Chevauchement de sous-problèmes. Calcul de bas en haut ou par mémoïsation. Reconstruction d’une solution optimale à partir de l’information calculée.	On souligne les enjeux de complexité en mémoire. On peut traiter un ou plusieurs exemples comme : problème de la somme d’un sous-ensemble, ordonnancement de tâches pondérées, plus longue sous-suite commune, distance d’édition (Levensh-tein).

L’objectif est de donner des outils de conception d’algorithmes et de parvenir à ce que les étudiants puissent, dans une situation simple, sélectionner une stratégie pertinente par eux-mêmes et la mettre en œuvre de façon autonome. Dans les cas les plus complexes, les choix et les recommandations d’implémentation sont guidés. Les listes d’exemples cités en commentaires ne sont ni impératives ni limitatives.