TP Python – Dates au plus tôt et au plus tard en Python

BTS SIO SISR 1re année – Mathématiques pour l'informatique – S17

Note

Comment ce TP fonctionne. Chaque exercice a un éditeur Python intégré à la page (il s'exécute dans ton navigateur, rien à installer). Avant de lancer, écris sur ta feuille ce que tu anticipes (« J'anticipe »). Puis lance et compare. Le bouton Valider exécute des tests : un test réussi ne dispense pas de comprendre pourquoi.

Un graphe valué est un dictionnaire {(origine, arrivée): valeur} ; un projet est un dictionnaire {tâche: (durée, [prédécesseurs])}.

Exercice A – Dijkstra

Écris dijkstra(arcs, source, sommets) qui renvoie (distance, predecesseur) (deux dictionnaires), puis reconstruire(predecesseur, cible) qui renvoie la liste des sommets du chemin de la source à cible. Pour « l'infini », utilise float("inf").

J'anticipe. Dans le graphe du cours, quelle valeur attends-tu pour T ? Par quels sommets passe le chemin ?

###

arcs = {("S", "A"): 4, ("S", "B"): 2, ("B", "A"): 1, ("A", "C"): 5, ("B", "C"): 8, ("B", "D"): 10, ("C", "D"): 2, ("C", "T"): 6, ("D", "T"): 3}bksl-nld, p = dijkstra(arcs, "S", ["S", "A", "B", "C", "D", "T"])bksl-nlassert d == {"S": 0, "A": 3, "B": 2, "C": 8, "D": 10, "T": 13}bksl-nlassert reconstruire(p, "T") == ["S", "B", "A", "C", "D", "T"]bksl-nlassert reconstruire(p, "S") == ["S"]bksl-nlw = {("A", "B"): 7, ("A", "C"): 9, ("A", "F"): 14, ("B", "C"): 10, ("B", "D"): 15, ("C", "D"): 11, ("C", "F"): 2, ("D", "E"): 6, ("F", "E"): 9}bksl-nld2, p2 = dijkstra(w, "A", ["A", "B", "C", "D", "E", "F"])bksl-nlassert d2 == {"A": 0, "B": 7, "C": 9, "D": 20, "E": 20, "F": 11}bksl-nlassert reconstruire(p2, "E") == ["A", "C", "F", "E"]bksl-nlassert dijkstra({("A", "B"): 1}, "A", ["A", "B", "C"])[0]["C"] == float("inf")bksl-nlbksl-nl ∞/∞

def dijkstra(arcs, source, sommets):bksl-nl inf = float("inf")bksl-nl distance = {}bksl-nl predecesseur = {}bksl-nl for v in sommets:bksl-nl distance[v] = infbksl-nl predecesseur[v] = Nonebksl-nl distance[source] = 0bksl-nl fixes = []bksl-nl while len(fixes) < len(sommets):bksl-nl x = Nonebksl-nl for v in sommets:bksl-nl if v not in fixes and (x is None or distance[v] < distance[x]):bksl-nl x = vbksl-nl if distance[x] == inf:bksl-nl breakbksl-nl fixes.append(x)bksl-nl for (a, b) in arcs:bksl-nl # À compléter : si a est x, b n'est pas fixé et distance[x] + valeur < distance[b],bksl-nl # mettre à jour distance[b] et predecesseur[b]bksl-nl passbksl-nl return (distance, predecesseur)bksl-nlbksl-nldef reconstruire(predecesseur, cible):bksl-nl chemin = [cible]bksl-nl # À compléter : remonter les prédécesseurs jusqu'à la source (prédécesseur None)bksl-nl chemin.reverse()bksl-nl return cheminbksl-nlbksl-nl

Exercice B – Dates au plus tôt

Écris dates_au_plus_tot(taches) qui renvoie un dictionnaire tâche → date au plus tôt. Tant que toutes les dates ne sont pas calculées, traite les tâches dont tous les prédécesseurs ont une date.

Je comprends. Pourquoi la boucle while s'arrête-t-elle quand le projet n'a pas de circuit ? Et sinon ?

###

projet = {"A": (3, []), "B": (2, ["A"]), "C": (6, ["B"]), "D": (4, ["A"]), "E": (5, ["D"]), "F": (4, ["C", "E"]), "G": (3, ["B"]), "H": (2, ["F", "G"])}bksl-nlassert datespy-undaupy-undpluspy-undtot(projet) == {"A": 0, "B": 3, "C": 5, "D": 3, "E": 7, "F": 12, "G": 5, "H": 16}bksl-nlmig = {"A": (2, []), "B": (4, []), "C": (3, ["A", "B"]), "D": (2, ["C"]), "E": (5, ["B"]), "F": (1, ["D", "E"])}bksl-nlassert datespy-undaupy-undpluspy-undtot(mig) == {"A": 0, "B": 0, "C": 4, "D": 7, "E": 4, "F": 9}bksl-nlassert datespy-undaupy-undpluspy-undtot({"X": (1, ["Y"]), "Y": (1, ["X"])}) is Nonebksl-nlassert datespy-undaupy-undpluspy-undtot({"X": (5, [])}) == {"X": 0}bksl-nlbksl-nl ∞/∞

def datespy-undaupy-undpluspy-undtot(taches):bksl-nl t = {}bksl-nl restantes = list(taches)bksl-nl while len(restantes) > 0:bksl-nl pret = Nonebksl-nl for x in restantes:bksl-nl ok = Truebksl-nl for p in taches[x][1]:bksl-nl if p not in t:bksl-nl ok = Falsebksl-nl if ok:bksl-nl pret = xbksl-nl breakbksl-nl if pret is None:bksl-nl return None # circuit : aucune tâche ne peut commencerbksl-nl date = 0bksl-nl for p in taches[pret][1]:bksl-nl pass # À compléter : date = max(date, t[p] + durée de p)bksl-nl t[pret] = datebksl-nl restantes.remove(pret)bksl-nl return tbksl-nlbksl-nl

Exercice C – Marges et chemin critique

Écris analyse(taches) qui renvoie (duree_projet, marges_totales, critiques) : la durée minimale, le dictionnaire des marges totales, et la liste triée des tâches critiques. Les dates au plus tôt sont fournies par dates_au_plus_tot.

###

projet = {"A": (3, []), "B": (2, ["A"]), "C": (6, ["B"]), "D": (4, ["A"]), "E": (5, ["D"]), "F": (4, ["C", "E"]), "G": (3, ["B"]), "H": (2, ["F", "G"])}bksl-nlassert analyse(projet) == (18, {"A": 0, "B": 1, "C": 1, "D": 0, "E": 0, "F": 0, "G": 8, "H": 0}, ["A", "D", "E", "F", "H"])bksl-nlmig = {"A": (2, []), "B": (4, []), "C": (3, ["A", "B"]), "D": (2, ["C"]), "E": (5, ["B"]), "F": (1, ["D", "E"])}bksl-nlassert analyse(mig) == (10, {"A": 2, "B": 0, "C": 0, "D": 0, "E": 0, "F": 0}, ["B", "C", "D", "E", "F"])bksl-nlassert analyse({"X": (5, [])}) == (5, {"X": 0}, ["X"])bksl-nlassert analyse({"X": (5, []), "Y": (2, [])})[1] == {"X": 0, "Y": 3}bksl-nlbksl-nl ∞/∞

def datespy-undaupy-undpluspy-undtot(taches):bksl-nl t = {}bksl-nl restantes = list(taches)bksl-nl while len(restantes) > 0:bksl-nl pret = Nonebksl-nl for x in restantes:bksl-nl ok = Truebksl-nl for p in taches[x][1]:bksl-nl if p not in t:bksl-nl ok = Falsebksl-nl if ok:bksl-nl pret = xbksl-nl breakbksl-nl if pret is None:bksl-nl return Nonebksl-nl date = 0bksl-nl for p in taches[pret][1]:bksl-nl if t[p] + taches[p][0] > date:bksl-nl date = t[p] + taches[p][0]bksl-nl t[pret] = datebksl-nl restantes.remove(pret)bksl-nl return tbksl-nlbksl-nldef analyse(taches):bksl-nl """Renvoie (durée du projet, marges totales, liste triée des tâches critiques)."""bksl-nl t = datespy-undaupy-undpluspy-undtot(taches)bksl-nl duree = 0bksl-nl for x in taches:bksl-nl pass # À compléter : durée = max de (t[x] + durée de x)bksl-nl successeurs = {}bksl-nl for x in taches:bksl-nl successeurs[x] = []bksl-nl for x in taches:bksl-nl for p in taches[x][1]:bksl-nl successeurs[p].append(x)bksl-nl tard = {}bksl-nl restantes = list(taches)bksl-nl tours = 0bksl-nl while len(restantes) > 0 and tours < 100:bksl-nl tours = tours + 1bksl-nl for x in restantes:bksl-nl if all(s in tard for s in successeurs[x]):bksl-nl fin = dureebksl-nl for s in successeurs[x]:bksl-nl pass # À compléter : fin = le plus petit des tard[s]bksl-nl tard[x] = fin - taches[x][0]bksl-nl restantes.remove(x)bksl-nl breakbksl-nl marges = {}bksl-nl for x in taches:bksl-nl marges[x] = 0 # À compléter : tard[x] - t[x]bksl-nl critiques = [] # À compléter : tâches de marge nulle, triéesbksl-nl return (duree, marges, critiques)bksl-nlbksl-nl