#Algorithmes avancésCopier le lien

Ce module ne Collectionne pas des recettes : il apprend à 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 en graphe et appliquer des briques éprouvées (parcours, plus courts chemins, arbres couvrants).

Prérequis : structures de données de base (listes, piles, files, tables de hachage, tas) du parcours L2 ; notation asymptotique O, Ω, Θ ; écrire et exécuter du Python simple.

Objectifs d'apprentissage : modéliser un problème en choisissant l'état ou le graphe pertinent ; prouver la correction d'un schéma algorithmique (argument d'échange, induction sur les sous-problèmes) ; estimer complexité en temps et en mémoire ; reconnaître les limites (poids négatifs, NP-difficulté) et passer à l'heuristique.

Contexte pédagogique : niveau L3 (Valrose, UCA). Le fil directeur est la capacité à modéliser, à prouver et à mesurer ; les chapitres alternent preuves sur le papier et implémentations Python mesurables.

#Deux familles récurrentes, 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 construis le tout »), puis on décide de calculer en mémoïsant (descendant, depuis le problème vers les cas de base) ou en tabulant (ascendant, depuis les cas de base). La vraie difficulté : choisir le bon état et l'ordre de calcul.

L'approche gloutonne choisit à chaque pas l'option localement meilleure et prouve que ces choix mènent à l'optimum global (argument d'échange, structure de matroïde). Quand la preuve tient, c'est simple et rapide ; quand elle ne tient pas, le résultat peut être sous-optimal sans que rien ne le signale.

#Les graphes comme langage communCopier le lien

Représenter un problème en nœuds et arêtes donne accès à une boîte à outils standard : plus courts chemins (Dijkstra si poids non négatifs, Bellman-Ford sinon, Floyd-Warshall pour toutes les paires), arbres couvrants minimaux (Kruskal, Prim), parcours systématiques (BFS, DFS). Le choix dépend de la nature des poids, des cycles négatifs et de la densité du graphe.

#Mini-atelier d'entréeCopier le lien

1. Formulez la récurrence du sac à dos 0/1, implémentez la tabulation ascendante, puis mesurez l'effet de doubler la capacité sur le temps (la complexité attendue est en O(n × W)).
2. Résolvez l'ordonnancement d'intervalles par tri des fins croissantes ; justifiez l'optimalité en deux phrases avec un argument d'échange.
3. Implémentez Dijkstra avec une file de priorité, puis remplacez-la par une recherche linéaire du minimum : comparez les deux sur un graphe dense.

Vérification pour l'atelier 2 : le tri par fin croissante puis sélection gloutonne donne toujours un nombre d'intervalles maximal ; sur l'exemple du chapitre Gloutons, la sortie est (1, 4), (5, 7), (8, 11), (12, 16), soit quatre intervalles.

#À retenirCopier le lien

Glouton si un argument d'échange tient ; programmation dynamique si les sous-problèmes se recoupent ; sinon explorer (retour arrière, branch-and-bound) avec heuristiques et bornes, ou passer à des métaheuristiques quand l'espace devient trop vaste.