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] CORRIGÉ EXERCICES TERMINALE ES ALGORITHME DE [PDF] CORRIGÉ EXERCICES TERMINALE ES ALGORITHME DE](https://pdfprof.com/Listes/26/19200-26exosTES-Dijkstra-cor.pdf.pdf.jpg)
CORRIGÉ EXERCICES TERMINALE ES ALGORITHME DE DIJKSTRA
EXERCICE 6 : Laurent et la distribution du courrier Laurent s"occupe de distribuer le courrier dans les bureaux d"une grande entreprise. Le graphe ci-dessous représente les différents parcours qu"il peut faire pour distribuer le courrier dans les bureaux A, B, C, D, E, F et G. Le poids de chaque arête indique le nombre d"obstacles (portes, escaliers, machines à café.) qui nuisent à la distribution du courrier. Laurent se voit confier par le bureau A un colis à livrer au bureau G. Indiquer un parcours qui permette à Laurent de partir du bureau A pour arriver au bureau G en rencontrant le minimum d"obstacles. Donc le parcours qui permet à Laurent de partir du bureau A pour arriver au bureau G en rencontrant le minimum d"obstacles est A - E - D - F - G.EXERCICE 7
: Trajet en trains Une région est munie d"un réseau de trains, représenté par le graphe ci-contre. ΓLes stations sont symbolisées par les sommets
A, B, C, D, E, F et G. Chaque arête représente une ligne reliant deux gares. Les temps de parcours (correspondance comprise) en minutes entre chaque sommet ont été rajoutés sur le graphe.1. Déterminer le plus court chemin en minutes, reliant
la gare B à la gare G. Justifier la réponse grâce à un algorithme.2. Quelle est la longueur en minutes de ce chemin ?
Le plus court chemin en minutes, reliant la gare B à la gare G est B - C - D - F - G, et la durée est de 36 minutes.A B C D E F G
0∞ ∞ ∞ ∞ ∞ ∞
x 5,A ∞10,A 6,A∞ ∞ x x 10,B 10,A 6,A x x 10,B 9,E x 11,E x x 10,B x x 10,D 13,D x x x x x 10,D 13,D ou 13,C x x x x x x 12,FA B C D E F G
∞0∞ ∞ ∞ ∞ ∞4,B x 7,B 18,B 21,B
x x 7,B 18,B 21,B x x x 17,C 21,B 32,F x x x x 21,B 29,D 48,D x x x x x 29,D 38,E x x x x x x 36,F EXERCICE 8 : Durée et coût de trajets autoroutiersLe tableau ci-dessous donne les durées et coût (péage) des trajets autoroutiers entre les principales villes du Sud de
la France : Bordeaux Clermont Lyon Marseille Montpellier Brive Toulouse Valence Biarritz Pau Grenoble numéro 1 6 9 8 7 4 5 9 2 3 11Bordeaux16,80 18,00 € 5,60 € 25 €
Clermont 13,80 8,60 € 11,90
Lyon 1h587,10 € 12,10 €
Marseille10,80 16,20 €
Montpellier 3h26 1h47 19,60 € 17,80 €
Brive 2h08 2h1015,10 €
Toulouse 2h24 2h28 2h09 11,60
Valence 1h13 2h08 1h588,80 €
Biarritz 2h179,50
Pau 2h102h08 1h32
Grenoble 1h201h05
1. Les graphes associés à ce tableau (durée en minutes et prix des péages) :
Le chemin que doit prendre un
automobiliste pour minimiser le coût des péages de Grenobleà Biarritz :
2 - 1 - 4 - 6 - 10 - 11 ;
Le coût de ce trajet : 60,20 €.
Le chemin que doit prendre un
automobiliste pour minimiser le coût des péages de Valenceà Bordeaux : 1 - 4 - 6 - 10 - 9
Le coût de ce trajet : 49,60 €.
Le chemin que doit prendre un automobiliste pour minimiser la durée du trajet de Grenoble à Biarritz :
2 - 3 - 5 - 7 - 9 - 11 ; La
durée de ce trajet : 551 minutes = 9h11.Le chemin que doit prendre
un automobiliste pour minimiser la durée du trajet deValence à Bordeaux :
1 - 5 - 7 - 9 ;
La durée de ce trajet : 410
minutes = 6h50.2. Le tableau des degrés :
Bordeaux Clermont Lyon Marseille Montpellier Brive Toulouse Valence Biarritz Pau Grenoble4 3 2 2 4 3 4 5 2 3 2
Il n"existe pas de chaîne eulérienne puisqu"il y a 4 sommets de degré impair.3. Il n"existe pas de cycle eulérien pour les mêmes raisons.
EXERCICE 8 : Randonnée
Un guide de randonnée en montagne
décrit les itinéraires possibles autour d"un pic rocheux.La description des itinéraires est
donnée par le graphe ci-contre.Les sommets de ce graphe
correspondent aux lieux remarquables.Les arêtes de ce graphe représentent
les sentiers possibles entre ces lieux avec les temps de parcours en minutes pour chacun des sentiers.Légende :
1 : Départ 2 : Passerelle 3 : Roche percée
4 : Col des 3 vents 5 : Pic rouge 6 : Refuge
7 : Col vert 8 : Pont Napoléon 9 : Cascade des anglais 10 : Arrivée
1. Un itinéraire allant de D à A passant par tous les sommets du graphe une seule fois mais n"empruntant pas
forcément tous les sentiers : 1 - 3 - 2 - 4 - 5 - 6 - 8 - 7 - 9 - 10.2. Tableau des degrés :
Sommets 1 2 3 4 5 6 7 8 9 10
Degrés 3 4 4 4 4 3 3 4 3 2
Il n"existe pas d"itinéraire allant de D à A utilisant tous les sentiers une seule fois, puisqu"il n"y a pas de chaîne
eulérienne, car il y a quatre sommets de degré impair.3. Pour déterminer l"itinéraire allant de D à A le plus court en temps, on utilise l"algorithme de Dijkstra à l"aide d"un
tableau :On trouve l"itinéraire :
1 - 3 - 6 - 5 - 7 - 9 - 10.
La durée est de 130 minutes.
1 2 3 4 5 6 7 8 9 10
0∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞
x 35,1 15,1 90,1 x 35,1 x 90,1 ∞40,3∞105,3∞ ∞ x x x 90,1 85,2 40,3 ∞105,3∞ ∞ x x x 90,1 80,6 x ∞95,6∞ ∞ x x x 90,1 x x 90,5 95,6 x x x x x x 90,5 95,6 135,4 x x x x x x x 95,6 110,7 x x x x x x x x 110,7 135,8 x x x x x x x x x 130,9quotesdbs_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