CORRIGÉ EXERCICES TERMINALE ES ALGORITHME DE
CORRIGÉ. EXERCICES. TERMINALE ES. ALGORITHME DE DIJKSTRA. EXERCICE 6 : Laurent et la distribution du courrier. Laurent s'occupe de distribuer le courrier dans
TD n°2 - Terminale ES Spé Les Graphes Graphes pondérés et
Les exercices identifiés par le symbole (c) sont intégralement corrigés en En utilisant l'algorithme de Dijkstra déterminer le trajet le moins cher. A. B.
Algorithme de Dijkstra
21 oct. 2008 Le but de cette présentation est de faire fonctionner l'algorithme de Dijkstra sur des exemples concrets. Exemple 1.
TP 6 - Corrigé Algorithme de Dijkstra
2 return graphe[noeud]. Spéciale BCPST 2. 4. Marc Pegon. Page 5. TP 6 - Corrigé. Algorithme de Dijkstra. 2015-2016. Q6 Ci-dessous le contenu des différentes
Algorithme de Dijkstra
Refaire entièrement le cas de l'exemple vous même. 2. Sur le même graphe construire le tableau et déterminer le chemin le plus court entre A et F. Exercice
Optimisation
Exercice 2 (Algorithme de Dijkstra) Appliquer l'algorithme de Dijkstra aux graphes suivant pour calculer les chemins de poids minimum depuis le sommet A
1 Plus court chemin
1.2) En utilisant l'algorithme de Dijkstra rappelé à la fin du document (Algorithme 1) Le but de cet exercice est de résoudre le problème suivant : étant ...
Diapositive 1
Exercice: Algorithme de Dijkstra s a d b e c. 1. 7. 3. 3. 1. 3. 8. 1. 6. Avec l chemin entre deux sommets et qui tente de corriger le problème présenté ...
Travaux Diriges RO03
Expliquer cela à l'aide d'un graphe à 10 sommets . 2. Exercice 2. Soit G = (XU)
Conception dalgorithmes Principes et 150 exercices non corrigés
Erickson). Computer Science is no more about computers than astronomy is about telescopes. (E. W. Dijkstra). However beautiful the strategy you should
[PDF] CORRIGÉ EXERCICES TERMINALE ES ALGORITHME DE
CORRIGÉ EXERCICES TERMINALE ES ALGORITHME DE DIJKSTRA EXERCICE 6 : Laurent et la distribution du courrier Laurent s'occupe de distribuer le courrier
[PDF] Algorithme de Dijkstra - Normale Sup
21 oct 2008 · l'algorithme de Dijkstra sur des exemples concrets Exemple 1 Cherchons les plus courts chemins d'origine A dans ce graphe:
[PDF] TD n°2 - Terminale ES Spé - Les Graphes
Les exercices identifiés par le symbole (c) sont intégralement corrigés en fin de TD pour les autres Graphes pondérés et algorithme de Dijkstra
[PDF] TP 6 - Corrigé Algorithme de Dijkstra - Marc Pegon
prendre garde au fait qu'on ne peut pas tester directement si la file est vide et considérer que la distance à un noeud est infinie s'il n'a pas d'entrée dans
[PDF] Optimisation
Exercice 2 (Algorithme de Dijkstra) Appliquer l'algorithme de Dijkstra aux graphes suivant pour calculer les chemins de poids minimum depuis le sommet A
[PDF] GRAPHES - EXERCICES CORRIGES Compilation réalisée à partir
Compilation réalisée à partir d'exercices de BAC TES 4) On utilise l'algorithme du plus court chemin de Dijkstra pour déterminer une chaîne qui minimise
[PDF] Corrigé TD N° 2
Le graphe de l'exercice est planaire car on peut le représenter de la façon Pour cela on peut appliquer l'algorithme de DIJKSTRA il est applicable car
[PDF] Algorithmes de plus court chemin
L'algorithme de Dijkstra gère un ensemble (virtuel) Exercice: Algorithme de Dijkstra chemin entre deux sommets et qui tente de corriger
[PDF] Travaux Diriges RO03 - UTC - Moodle
Exercice 1 Les algorithmes de DIJKSTRA et BELLMAN sont-ils applicables? Justifier A) Application de l'algorithme de Dijkstra;
[PDF] SUJET + CORRIGE
SUJET + CORRIGE Exercice 2: Parcours en profondeur de graphes le résultat (u d et u pere pour chaque sommet) de l'algorithme Dijkstra-acyclique
![[PDF] SUJET CORRIGE [PDF] SUJET CORRIGE](https://pdfprof.com/Listes/26/19200-26corrige.pdf.pdf.jpg)
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
Chemin critique :(0;1;2;3;4;5)de longueur17.
Page 4 sur 4
quotesdbs_dbs2.pdfusesText_2[PDF] dima dima math 2 bac pdf
[PDF] dima maroc video
[PDF] dimanche sport tunisie
[PDF] dimanche sport tunisie email
[PDF] dimension terrain de badminton en pied
[PDF] dimensionnement d'un bac ? graisse
[PDF] dimensionnement escalier béton armé
[PDF] dimensionnement piège ? cailloux
[PDF] dimensionnement protection cathodique
[PDF] dimensionnement ventilation groupe électrogène
[PDF] din 910 pdf
[PDF] din en 10204
[PDF] dipe 5 lyon
[PDF] diploma equivalence france usa