LDAP: couldn't connect to LDAP server
Différences
Ci-dessous, les différences entre deux révisions de la page.
Les deux révisions précédentes Révision précédente Prochaine révision | Révision précédente | ||
tc_info:tp6 [2018/11/23 10:10] – pprea | tc_info:tp6 [2019/09/28 16:34] (Version actuelle) – edauce | ||
---|---|---|---|
Ligne 1: | Ligne 1: | ||
+ | ====== TP4 ====== | ||
+ | |||
+ | Le but de ce TP est d' | ||
+ | |||
+ | |||
+ | |||
+ | < | ||
+ | Le fait de tester toutes vos créations n'est plus explicitement demandé car cela doit **encore & toujours** être fait. | ||
+ | </ | ||
+ | |||
+ | Les graphes seront représentés " | ||
+ | |||
+ | <code python> | ||
+ | |||
+ | CAPACITE = " | ||
+ | FLUX = " | ||
+ | |||
+ | the_graph = {1: {2: {CAPACITE: 5, FLUX: 2}, 3: | ||
+ | 2: {3: {CAPACITE: 7, FLUX: 1}, 4: {CAPACITE: 8, FLUX: 1}}, | ||
+ | 3: {5: {CAPACITE: 4, FLUX: 2}}, | ||
+ | 4: {6: {CAPACITE: 3, FLUX: 2}}, | ||
+ | 5: {4: {CAPACITE: 6, FLUX: 1}, 6: {CAPACITE: 8, FLUX: 1}}, | ||
+ | 6: {} | ||
+ | } | ||
+ | </ | ||
+ | |||
+ | Dessinez le graphe ci-dessus. | ||
+ | |||
+ | Implémentez l' | ||
+ | |||
+ | <code python> | ||
+ | import math | ||
+ | |||
+ | INFINI = math.inf | ||
+ | CAPACITE = " | ||
+ | FLUX = " | ||
+ | |||
+ | |||
+ | def mise_a_zero_flot(graph): | ||
+ | for sommet in graph: | ||
+ | for voisin in graph[sommet]: | ||
+ | graph[sommet][voisin][FLUX] = 0 | ||
+ | |||
+ | |||
+ | def construction_graphe_ecart(graphe_antisymetrique): | ||
+ | graphe_ecart = {} | ||
+ | for sommet in graphe_antisymetrique: | ||
+ | graphe_ecart[sommet] = {} | ||
+ | for sommet in graphe_antisymetrique: | ||
+ | for voisin in graphe_antisymetrique[sommet]: | ||
+ | capacite = graphe_antisymetrique[sommet][voisin][CAPACITE] | ||
+ | flux = graphe_antisymetrique[sommet][voisin][FLUX] | ||
+ | if capacite > flux: | ||
+ | graphe_ecart[sommet][voisin] = capacite - flux | ||
+ | if flux > 0: | ||
+ | graphe_ecart[voisin][sommet] = flux | ||
+ | return graphe_ecart | ||
+ | |||
+ | |||
+ | def construction_chemin_via_dfs(graphe_ecart, | ||
+ | sommets_marques = {} | ||
+ | antecedents = {} | ||
+ | pile = [source] | ||
+ | for sommet in graphe_ecart: | ||
+ | antecedents[sommet] = None | ||
+ | while pile != []: | ||
+ | sommet = pile.pop() | ||
+ | if sommet not in sommets_marques: | ||
+ | sommets_marques[sommet] = True | ||
+ | for voisin in graphe_ecart[sommet]: | ||
+ | if voisin not in sommets_marques: | ||
+ | antecedents[voisin] = sommet | ||
+ | pile.append(voisin) | ||
+ | if sommet == puits: | ||
+ | return construction_effective_chemin(sommet, | ||
+ | |||
+ | |||
+ | def construction_effective_chemin(sommet, | ||
+ | chemin = [] | ||
+ | while sommet is not None: | ||
+ | chemin.append(sommet) | ||
+ | sommet = antecedents[sommet] | ||
+ | chemin.reverse() | ||
+ | return | ||
+ | |||
+ | |||
+ | def min_sur_chemin(chemin, | ||
+ | minimum = INFINI | ||
+ | for i in range(len(chemin) - 1): | ||
+ | courant = chemin[i] | ||
+ | suivant = chemin[i + 1] | ||
+ | if graphe_ecart[courant][suivant] < minimum: | ||
+ | minimum = graphe_ecart[courant][suivant] | ||
+ | return minimum | ||
+ | |||
+ | |||
+ | def ajout_flot(valeur, | ||
+ | for i in range(len(chemin) - 1): | ||
+ | courant = chemin[i] | ||
+ | suivant = chemin[i + 1] | ||
+ | if suivant in graphe_antisymetrique[courant]: | ||
+ | graphe_antisymetrique[courant][suivant][FLUX] += valeur | ||
+ | else: | ||
+ | graphe_antisymetrique[suivant][courant][FLUX] -= valeur | ||
+ | |||
+ | </ | ||
+ | |||
+ | Dans la fonction construction_graphe_ecart, | ||
+ | |||
+ | |||
+ | Dans un deuxième temps, on l' | ||
+ | <code python> | ||
+ | CLEOPATRE = " | ||
+ | IPHIGENIE = " | ||
+ | JULIETTE = " | ||
+ | FANNY = " | ||
+ | CHIMENE = " | ||
+ | |||
+ | ACHILLE = " | ||
+ | CESAR = " | ||
+ | RODRIGUE = " | ||
+ | ROMEO = " | ||
+ | MARIUS = " | ||
+ | |||
+ | LES_COUPLES = [(CLEOPATRE, | ||
+ | | ||
+ | | ||
+ | </ | ||
+ | |||
+ | On résoudra après le problème de "la bataille de la Marne", | ||
+ | * Au temps 0, on a autant de taxis que nécessaire dans la ville 14 (" | ||
+ | * Au temps 50, il faut qu'il y en ait le plus possible dans la ville 0 ("La Marne" | ||
+ | * Chaque ville (intermédiaire) a 10 places de parking (Paris en a autant que nécessaire). | ||
+ | * Les routes sont données dans le tableau suivant : | ||
+ | |||
+ | |||
+ | <code python> | ||
+ | LES_ROUTES = [{' | ||
+ | {' | ||
+ | {' | ||
+ | {' | ||
+ | {' | ||
+ | {' | ||
+ | {' | ||
+ | {' | ||
+ | {' | ||
+ | {' | ||
+ | {' | ||
+ | {' | ||
+ | {' | ||
+ | {' | ||
+ | {' | ||
+ | {' | ||
+ | {' | ||
+ | {' | ||
+ | {' | ||
+ | {' | ||
+ | {' | ||
+ | {' | ||
+ | {' | ||
+ | {' | ||
+ | {' | ||
+ | {' | ||
+ | {' | ||
+ | {' | ||
+ | {' | ||
+ | {' | ||
+ | {' | ||
+ | {' | ||
+ | {' | ||
+ | {' | ||
+ | {' | ||
+ | {' | ||
+ | {' | ||
+ | {' | ||
+ | {' | ||
+ | {' | ||
+ | {' | ||
+ | {' | ||
+ | </ | ||
+ | |||
+ | <note important> | ||
+ | Les routes sont à double sens (il ne faut pas se fier aux appellations " | ||
+ | </ | ||
+ | |||
+ | On pourra commencer par une instance plus petite, par exemple en ne considérant que les villes jusqu' | ||
+ | |||
+ | <code python> | ||
+ | LES_ROUTES = [{' | ||
+ | {' | ||
+ | {' | ||
+ | {' | ||
+ | {' | ||
+ | {' | ||
+ | {' | ||
+ | {' | ||
+ | {' | ||
+ | {' | ||
+ | {' | ||
+ | {' | ||
+ | {' | ||
+ | {' | ||
+ | {' | ||
+ | {' | ||
+ | {' | ||
+ | {' | ||
+ | {' | ||
+ | {' | ||
+ | {' | ||
+ | {' | ||
+ | {' | ||
+ | {' | ||
+ | {' | ||
+ | {' | ||
+ | </ | ||
+ | |||
+ | voire même plus petit. |