#Algorithmes avancés
Stratégies de résolution et d’optimisation: programmation dynamique, gloutons, graphes avancés.
#Objectifs
- Identifier la structure d’un problème (optimal substructure, sous‑problèmes qui se recoupent).
- Choisir une stratégie adaptée: glouton, programmation dynamique, recherche informée.
- Analyser la complexité temps/mémoire et les compromis précision/rapidité.
#Notions clés
- Programmation dynamique: top‑down (mémoïsation) vs bottom‑up (tabulation).
- Glouton: choix local optimal, critères d’optimalité (échange, matroïdes).
- Graphes: plus courts chemins (Dijkstra, Bellman‑Ford), flots, arbres couvrants.
#Exemples classiques
- Sac à dos 0/1 (DP), interval scheduling (glouton), arbre de Huffman (glouton), chaînes de Markov (DP), A* (recherche informée).
#À retenir
- “Glouton si l’échange est possible; sinon DP si sous‑problèmes se recoupent; sinon backtracking/branch‑and‑bound.”