#Algorithmes avancésCopier le lien

Le but n’est pas d’apprendre des “recettes” par cœur, mais de reconnaître la forme d’un problème pour choisir la bonne idée: prendre un bon choix local à chaque étape (glouton), recomposer des sous‑problèmes (programmation dynamique), ou modéliser dans un graphe et appliquer des briques bien connues.

Contexte pédagogique: niveau L3 (Valrose — UCA). Le fil directeur est la capacité à modéliser un problème, à prouver la correction d’un schéma algorithmique et à estimer sa complexité.

#Deux modèles récurrents, deux façons de penserCopier le lien

La programmation dynamique raconte une histoire de sous‑problèmes qui se recoupent. On formule une récurrence (“si je connais ces morceaux, je peux construire le tout”), puis on décide de calculer en mémoïsant (top‑down) ou en tabulant (bottom‑up). La vraie difficulté est de choisir le bon état et l’ordre de calcul.

L’approche gloutonne, elle, choisit à chaque pas le meilleur “localement” et prouve que ces choix mènent à l’optimum global (argument d’échange, structure de matroïde). Quand c’est vrai, c’est simple et rapide; quand ça ne l’est pas, le résultat peut être sous‑optimal.

#Les graphes comme langage universelCopier le lien

Représenter un problème sous forme de nœuds et d’arêtes permet d’appliquer des algorithmes standard: plus courts chemins (Dijkstra si poids non négatifs; Bellman‑Ford sinon), arbres couvrants (Kruskal/Prim), flots maximum (Ford‑Fulkerson/Edmonds‑Karp). Le choix dépend de la nature des poids, de la présence de cycles négatifs et de la densité du graphe.

#Mini‑atelierCopier le lien

1. Formulez une récurrence pour le sac à dos 0/1 et implémentez une tabulation bottom‑up; mesurez l’impact de la taille de la table.
2. Résolvez l’ordonnancement d’intervalles par tri des fins croissantes et justifiez l’optimalité en deux phrases.
3. Implémentez Dijkstra avec une file de priorité, puis remplacez‑la par une liste non triée: comparez.

#À retenirCopier le lien

“Glouton si un argument d’échange tient; DP si sous‑problèmes se recoupent; sinon, explorez (backtracking/branch‑and‑bound) avec heuristiques et bornes.”