Algorithmes intermédiaires (facultatif)
Le réseau de distribution : récursivité, DP, graphes, Dijkstra, complexité amortie
Dans ce chapitre, vous apprendrez à
- Penser récursivement et éviter de recalculer (programmation dynamique)
- Modéliser un problème comme un graphe et y chercher des chemins
- Estimer le coût réel d'une structure de données
Outils : Python
8 exercices
Chaque exercice est corrigé automatiquement, dans le navigateur. Les énoncés complets sont accessibles avec un compte.
À quoi ça sert dans la vraie vie
Beaucoup de problèmes réels sont des réseaux ou des choix en cascade, et il est hors de question d'essayer toutes les possibilités. - Les GPS. Trouver l'itinéraire le plus rapide parmi des millions de carrefours…
Poupées russes
Bienvenue dans le réseau de distribution LogiMax ! Vous êtes le nouvel ingénieur chargé d'optimiser les opérations. Premier problème : l'inventaire de l'entrepôt central. Les marchandises sont rangées dans des…
Chemin le moins cher
Les produits LogiMax traversent un réseau de relais organisé en grille. Chaque relais a un coût de transit (en euros). Un produit part du coin haut-gauche et doit arriver au coin bas-droite. À chaque…
Tour de colis
L'entrepôt LogiMax empile des colis sur des palettes. Pour la stabilité, chaque colis doit être strictement plus petit (en largeur ET en hauteur) que celui en dessous. On vous donne une liste de colis, chacun décrit…
Livraisons urgentes
Le poste de tri LogiMax ne libère jamais les commandes dans leur ordre d'arrivée : à tout instant, c'est la plus urgente qui part la première, et de nouvelles commandes tombent sans arrêt pendant qu'on expédie les…
Réseau de routes
Le réseau LogiMax est composé d'entrepôts reliés par des routes à sens unique. On vous donne la carte sous forme de liste d'adjacence : un dictionnaire où chaque clé est un entrepôt et la valeur est la liste des…
Plus court trajet
Maintenant, les routes LogiMax ont des distances ! Le réseau est donné comme un dictionnaire d'adjacence avec poids :
Entrepôt extensible
L'entrepôt LogiMax utilise un système d'étagères dynamiques. Au début, il y a de la place pour 1 colis. Quand l'étagère est pleine et qu'un nouveau colis arrive, on construit une étagère deux fois plus grande et…