#Slides : algorithmes avancésCopier le lien

Un point par thème, à projeter avant l'atelier correspondant.

#Programmation dynamiqueCopier le lien

• Deux ingrédients : sous-structure optimale + chevauchement de sous-problèmes.
• Descendant (mémoïsation) pour prototyper, ascendant (tabulation) pour livrer.
• L'état d'abord, la récurrence ensuite, l'ordre de calcul enfin.
• Réduction d'espace : tableaux glissants quand la récurrence regarde une bande fixe.
• Complexités types : sac à dos O(n × W), monnaie O(montant × pièces), LCS O(m × n).

#Algorithmes gloutonsCopier le lien

• Choix local, jamais révisé ; la question est la preuve, pas le code.
• Argument d'échange : toute solution optimale se transforme en la solution gloutonne sans perte.
• Intervalles : tri par fin croissante, optimal (preuve en deux phrases).
• Monnaie : optimal pour certains systèmes seulement (4 et 6 : glouton 3 pièces, optimal 2).

#Plus courts cheminsCopier le lien

• Dijkstra : poids non négatifs, O((V+E) log V) ; arrêt possible à l'extraction de la cible.
• Entrées périmées dans le tas plutôt que décrément de clé.
• Bellman-Ford : poids négatifs, O(V·E), détection de cycle négatif par passe finale.
• Floyd-Warshall : toutes les paires en O(V³) ; critique à la boucle externe.
• A* : f = g + h ; h admissible garantit l'optimalité, h consistante évite les réouvertures.

#Graphes : parcours et arbres couvrantsCopier le lien

• BFS : couches de distance, plus court chemin non pondéré ; DFS : tri topologique, cycles, composantes.
• Kruskal : tri des arêtes + union-find, O(E log E) ; Prim : tas d'arêtes frontière, O(E log V).

#Tri rapideCopier le lien

• Partition autour d'un pivot ; invariant : petits à gauche, grands à droite.
• Moyenne O(n log n), pire cas O(n²) sur pivot systématiquement extrême.
• Durcissements : médiane de trois, coupure insertion, récursion sur le petit côté d'abord.
• Non stable : préférer Timsort pour des clés composites.

#Codage de HuffmanCopier le lien

• Fusion gloutonne des deux plus faibles fréquences ; code préfixe par construction.
• Optimal parmi les codes préfixes : échange (les deux plus rares sont frères en bas) + induction.

#MétaheuristiquesCopier le lien

• Génétiques : encodage, adaptation, sélection, croisement, mutation ; aucun garantie d'optimalité.
• Trois compromis à régler : taille de population, taux de mutation, pression de sélection.
• Toujours comparer à une heuristique dédiée sur le même budget.

#LimitesCopier le lien

• NP-difficulté : pas d'algorithme polynomial connu, l'heuristique devient légitime.
• Retour arrière puis branch-and-bound : explorer avec bornes pour élaguer.
• Garanties d'approximation quand elles existent : les énoncer explicitement.