Le problème du plus court chemin : exercices- corrigé
Le problème du plus court chemin /exercices/corrigé/p1 Le problème du plus court chemin : exercices- corrigé I 0 0 1 0 2 0 3 0 4 0 1 2 1 1 2 2 2 1 3 2 3 1 Les sommets correspondent à l'état du stock à la fin de chaque période : par hypothèse, il peut être de 0, 1 ou 2 Les arcs sont associés aux décisions Initialement, le stock est
TD n o 8 - Recherche de plus courts chemins 1 Lalgorithme de
Les notations sont les suivantes : π[v] contient le prédécesseur de v sur le chemin (NIL s'il n'y en a pas), δ(u,v) est le poids du plus court chemin de u vers v ( ∞s'il n'existe pas), d[v] est une ariablev qui est une borne supérieure du poids du plus court chemin de s vers v (cf question 4) On dé nit le poids d'un chemin p = hv 0,v
TD d’algorithmique avanc ee Corrig e du TD 11 : Plus courts
Comme nous l’avons remarqu e en cours, tout sous-chemin d’un plus court chemin est lui-m^eme un plus court chemin et le probl eme des plus courts chemins v eri e bien la propri et e de sous-structure optimale : nous pouvons donc essayer de le r esoudre par programmation dynamique 1 On note d(m)
Plus courts chemins: algorithme de Floyd-Warshall
du plus court chemin entre i et j (s’il existe, D ij = +1sinon) et R ij est une table de routage Exercice 1: Algorithme de Warshall Dans un premier temps, on s’int eresse a calculer la cl^oture transitive, c’est a dire d eterminer s’il existe un chemin allant de i a j pour tout couple de sommets (i;j) 2X2 Les chemins de G peuvent
Résolution des problèmes de plus court chemin – exercices
Résolution des problèmes de plus court chemin – exercices- corrigé I Le graphe qui permet de modéliser ce problème est analogue à celui vu dans le cours C'est un graphe de 7 sommets numérotés de 0 à 6
SUJET + CORRIGE
Exercice 4: Variantes plus court chemin à origine unique (8 points) L’algorithmedeDijkstra Initialisation (G, s){ // G(S,A,w) oriente pour u dans S faire
Algorithmique — L3 — TD 9 Plus courts chemins : la méthode
Exercice 5 : Quelle est la complexité de cet algorithme (au mieux, au pire, en moyenne)? Exercice 6 : A quoi sert la dernière boucle? Donnez un exemple de graphe où la valeur FAUX est retournée Exercice 7 : Prouvez l’invariant S’il existe un plus court chemin de s à u de k arcs,
Correction sujet du bac en mathématiques, Inde, Pondichéry 2018
reemaths r Corrigé - Bac - Mathématiques - 2018 Déterminons le chemin le plus court qui permet à Louis de relier son domicile à son travail: Notons que: Louis souhaite aller de A à G Après recours à l’algorithme de Dijkstra, nous trouvons comme trajet que Louis doit suivre pour aller de A à G, tout en minimisant la distance ( chemin
Algorithmes de Graphes, HLIN501 Ann ee 2016-2017 L3 Info, L3
- Exercice 4 - Vrai/Faux Con rmer (et prouver) ou in rmer (et donner un contre-exemple) les propri et es suivantes : a Un sous-chemin d’un plus court chemin est un plus court chemin b Si r est un sommet d’un graphe orient e D pond er e par des longueurs positives toutes distinctes,
Universit´e Paris 7 - Master 1 Informatique - Intelligence
Exercice 1 Algorithmes de recherche (8 points) Consid´erez la carte suivante Le but est de trouver le chemin le plus court de A vers I A D E C H F G B I 5 5 6 2 5
[PDF] exercice corrigé pourcentage 4ème PDF Cours,Exercices ,Examens
[PDF] exercice corrigé pression artérielle PDF Cours,Exercices ,Examens
[PDF] exercice corrigé prisme optique PDF Cours,Exercices ,Examens
[PDF] exercice corrigé probabilité conditionnelle PDF Cours,Exercices ,Examens
[PDF] exercice corrigé probabilité loi binomiale PDF Cours,Exercices ,Examens
[PDF] exercice corrigé probabilité loi normale PDF Cours,Exercices ,Examens
[PDF] exercice corrigé probabilité seconde PDF Cours,Exercices ,Examens
[PDF] exercice corrigé probabilité terminale s PDF Cours,Exercices ,Examens
[PDF] exercice corrigé probabilité tirage sans remise PDF Cours,Exercices ,Examens
[PDF] exercice corrigé probabilité variable aléatoire continue PDF Cours,Exercices ,Examens
[PDF] exercice corrigé proportionnalité 6ème PDF Cours,Exercices ,Examens
[PDF] exercice corrigé puissance 4eme PDF Cours,Exercices ,Examens
[PDF] exercice corrigé pythagore PDF Cours,Exercices ,Examens
[PDF] exercice corrigé pythagore et thales PDF Cours,Exercices ,Examens
Master BioInformatiqueAnnée :2011/2012Session de avril 2012
PARCOURS :Master 1
UE J1BS8203 :Méthodes et outils pour la biologie des systèmesÉpreuve :Examen
Date :Mardi 10 avril 2012
Heure :10 heures
Durée :2 heures
Documents : autorisés
Épreuve de M. AlainGriffaultSUJET + CORRIGE
Avertissement
La plupart des questions son tindé-
pendantes.L"espace laissé p ourles rép onsesest
suffisant (sauf si vous utilisez ces feuilles comme brouillon, ce qui est fortement déconseillé).QuestionPointsScoreAutomates de recherche de motifs4
Parcours en profondeur de graphes4
Graphes pondérés4
Variantes plus court chemin à origine unique8
Total:20
Exercice 1: Automates de recherche de motifs (4 points) (a) (2 p oints)P ourles mots sur l"alphab et =fa;bg, dessinez l"automate de recherche du motifaabab.Solution:012345ab
a bba abb ab aFigure1 - Recherche deaabab(b)(2 p oints)On dit d"un motif Pqu"il estnon recouvrablesi(PkwPq))(k= 0^k=q), c"est à dire
que si leskpremières lettres du motif forment un suffixe desqpremières lettres de ce même motif,
alors soitk= 0, soitk=q. Donnez la particularité de l"automate d"un motif non recouvrable.Solution:Toutes les arcsretourreviennent à l"état initial.Exercice 2: Parcours en profondeur de graphes (4 points)
Donnez un graphe orienté G tel qu"il existe deux sommetsuetvvérifiant : -u;v -u:debut < v:debut -vn"est pas un descendant deudans la foret en profondeur obtenue lors du parcours en profondeur.Solution:suv
Figure2 - Parcours en profondeur dans l"ordre(s;u;v) UE J1BS8203 : Méthodes et outils pour la biologie des systèmes Session 1, Année 2011/2012Exercice 3: Graphes pondérés (4 points)
Vous admettrez la propriété suivante :
Propriété 1SoitG(S;A;w)un graphe non orienté pondéré avecw:A!N. SoientTAetT0Adeuxarbres couvrants de poids minimal. SoientLT= (a0;:::;an)etLT0= (a00;:::;a0n)les listes triées par poids
croissant des arêtes deTetT0. Alors :8i2[0::n];w(ai) =w(a0i). Informellement, la liste ordonnée des poids
des arêtes constituant un arbre couvrant est unique.SoitG(S;A;w)un graphe non orienté pondéré. Montrer que pour chaque arbre couvrant de poids minimal
TdeG, il existe un moyen pour que l"algorithme de Kruskal retourne comme résultatT. Solution:SoitG(S;A;w)un graphe non orienté pondéré avecw:A!N. SoitTAun arbrecouvrant de poids minimal. SoitLT= (a0;:::;an)la liste triée par poids croissant des arêtes deT.
SoitLATla liste triée par poids croissant des arêtes deAT. SoitLla liste triée par poids croissant des arêtes deTobtenue par fusion des listesLTetLAT, en donnant priorité aux éléments deLTen cas d"égalité.Il suffit d"appliquer l"algorithme de Kruskal en utilisant la liste triéeL.Exercice 4: Variantes plus court chemin à origine unique (8 points)
L"algorithme de Dijkstra
I n i t i a l i s a t i o n (G, s ){ // G(S,A,w) oriente pour u dans S faire { u . dI n i t i a l i s a t i o n (G, s );
FPage 2 sur 4
UE J1BS8203 : Méthodes et outils pour la biologie des systèmes Session 1, Année 2011/2012SoitG(S;A;w)un graphe orienté pondéréacyclique. Il est alors possible d"améliorer l"algorithme de Dijkstra
pour calculer une arborescence des plus courts chemins. Dijkstraacyclique (G){ // G(S,A,w) oriente acyclique LRelacher (u , v ,w);
(a) (2 p oints)Donnez le résultat ( u.detu.perepour chaque sommet) de l"algorithmeDijkstra-acyclique sur le graphe suivant.0123455 3267 4 212
2 Figure3 - Un graphe orienté pondéré acycliquesommet012345 u.d0531075 u.perenil00222 (b) (2 p oints)Donnez la complexité de l"algorithme Dijkstra-acyclique.
Solution:
La complexité du tri top ologiqueest (jSj+jAj)(vu en cours). La complexité de l"initialisation est (jSj)(une boucle pour).Le nom brede passage dans le tant queestjSj.
Le nom brede passage dans la b ouclein ternepourestjAj.La complexité totale est donc :(jSj+jAj).Une variante de cet algorithme est utilisable pour calculer les chemins critiques dans un grapheG(S;A;w)
lorsque : Les arcs représen tentles tâc hesà faire. Les p ondérationsrep résententle temps nécessaire p oureffectuer la tâc he.les arcs a1= (u;v)eta2= (v;w)représentent deux tâches qui doivent être effectuées dans l"ordrea1;a2.
Unchemin critiqueest unplus longchemin dans le graphe, qui correspond au temps maximum requis poureffectuer une séquence ordonnée de tâches. Le poids d"un chemin critique est une borne inférieure du temps
total nécessaire à l"exécution de toutes les tâches. (c)(2 p oints)A daptezles algorithmes préc édentsp ourcalculer les c heminscritiques d"un graphe orien té
pondéré acyclique.Solution:Deux solutions :
1.Les distance sson tinitialisée sà 1,
InitialisationCheminCritique (G, s ){ // G(S,A,w) oriente pour u dans S faire { u . d < MAXINT; //i n f i n i u . pere7 4 212
2 Figure4 - Un graphe orienté pondéré acycliquesommet012345 u.d057141517 u.perenil01234