TD et TP — Synthèse

La ressource avance d'un sujet par semaine, avec un TD et un TP assortis. Voici le déroulé, les exercices qui reviennent et les pièges de chaque séance.

Les 7 TD

1. Chemins dans les graphes — énumérer les chemins entre deux sommets, leur longueur (nombre d'arêtes = nombre de sommets − 1), chemins eulériens (chaque arête une fois) et hamiltoniens (chaque sommet une fois). Modélisations : le « dîner des langues » devient une recherche de cycle hamiltonien, et l'échange de cavaliers un simple graphe de dix cases.
2. Matrice d'adjacence et centralité — produit booléen de matrices (M², M³ = existence de chemins de longueur 2, 3), réseau social R : excentricité et centre d'un graphe, trouvés par M≤k ; puis le produit usuel de matrices pour compter chaînes et cycles de longueur 3.
3. Listes de successeurs, arbres, parcours — représenter un graphe par ses listes, reconnaître les arbres (racine, prédécesseurs), dérouler le parcours en largeur en groupe : trace ligne à ligne, état de la file, arbre de parcours.
4. Plus court chemin, Dijkstra — retrouver les prédécesseurs à partir des distances et surligner l'arbre des plus courts chemins ; le jeu de piste montre qu'un arbre calculé depuis un seul sommet ne suffit pas (il faut relancer Dijkstra) ; cycle absorbant (un graphe à poids −1 où la distance devient arbitraire) ; exercice inverse : retrouver les poids et distances manquants à partir des tables.
5. Bellman, ordonnancement — plus courts puis plus longs chemins à la main (traces en tableau), puis la méthode potentiel-tâches sur neuf tâches A à I : graphe sans arêtes inutiles, dates au plus tôt et au plus tard, chemin critique, marge de chaque tâche ; en fin de séance, l'organisation d'une conférence (12 tâches, du 23 au 26 mai) à modéliser de zéro.
6. Flots — argumenter qu'un flot de valeur 30 est impossible (coupe), construire un flot complet par parcours en profondeur avec ordre de visite imposé, puis Ford-Fulkerson à partir d'un flot fourni : graphe de flot résiduel à compléter, chaîne améliorante, flot maximal et coupe minimale saturée.
7. Modélisation par graphe de configurations — dérouler le parcours en profondeur et comparer ses arbres à ceux du TD 3 ; casse-tête des seaux (4 litres avec 3 L et 5 L) et échange de cavaliers (configurations (b1, b2, n1, n2)).

Les 4 TP

1. Plus court chemin — prise en main de Grapp : Grapp server &, load, list, draw, format YAML diwgraph (indentation et espace après les deux points !), load -reload. Puis modélisations : l'implantation d'un entrepôt (ville centrale au sens de l'excentricité, pondérée par les populations), le robot qui traverse un terrain accidenté (poids = énergie, capacité de batterie, point de recharge), et Mélinda qui optimise sa bourse (des poids négatifs pour les gains : la course rapporte 6 po, l'auberge rend 10 po). En fin de séance, tests auto-correctifs Dijkstra sur Moodle.
2. Bellman, ordonnancement — 1 h 30 sur papier : les dix tâches « sport-études », dates au plus tôt (algorithme de Bellman), date de fin, dates au plus tard, tâches critiques, effectif minimal par Gantt ; puis l'assouplissement d'antériorités (D avancé à 50 % suffit pour B, F à 75 % pour G) et la nouvelle date de fin ; enfin la planification de la SAé d'itinéraires. Sur machine : gen-yaml pour fabriquer les trames, optimal-path -optimize Min/Max -operation Add/Mult, et Michel Strogoff dont l'erreur est de maximiser la somme de chances de survie au lieu du produit.
3. Flots — maximum-flow -algorithm Ford-Fulkerson -source o -sink p sur un premier réseau ; le réseau d'eau (réserves a-d, villes j, k, l) qui n'est pas un réseau valide avant l'ajout de source et puits, puis l'étude des canalisations à refaire ; le réseau routier (1700 véhicules/heure, +300 espérés) où l'on scinde chaque commune pour intégrer les débits urbains ; le réseau internet (fiabilité : arêtes de capacité 1 pour compter les câbles à couper, capacité de traitement d'un routeur) ; et l'affectation des 100 familles dans les 100 appartements par flot biparti. Tests Moodle Ford-Fulkerson en fin de séance.
4. Configurations — load -implicit sur une classe Java étendant AbstractImplicitGraph (compilation avec grapp.jar sur le classpath) ; complétion du loup-chèvre-chou (initialNodes, sommet, configurationPerdante, lautreRive, successors), puis saute-mouton paramétré par TAILLE, seaux et cavaliers. Le réflexe à retenir : parcours en largeur pour obtenir la solution la plus courte, find-path pour extraire le chemin, draw pour visualiser.

Le DS d'entraînement

1 h 30, seules les notes de cours sont autorisées, calculatrice interdite ; environ deux tiers pour la compétence 2 (algorithmes), un tiers pour la compétence 5 (conduite de projet), questions à étoile à traiter en dernier. Quatre exercices : reconnaître les arbres ; le réseau de transport des déchets toxiques A à D vers les usines G à K (flot réalisable, puis contrainte de transport sécurisé vers l'usine I — justifier la quantité traitable par la coupe minimale) ; un Dijkstra sur réseau routier dont les tables de distances et prédécesseurs sont fournies pour toutes les sources (Zoé, ses parents, la ville de rencontre) ; et l'ordonnancement « sport-études » complet (graphe, dates, chemin critique, Gantt et effectif minimal, assouplissements).

---