[PDF] CORRIGÉ EXERCICES TERMINALE ES ALGORITHME DE

View - Download CORRIGÉ EXERCICES TERMINALE ES ALGORITHME DE

Previous PDF

Next PDF

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,F

A 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 autoroutiers

Le 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 11

Bordeaux16,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 de

Valence à 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 Grenoble

4 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,1quotesdbs_dbs2.pdfusesText_2

[PDF] algorithme de dijkstra explication

[PDF] algorithme de reconnaissance dempreinte digitale

[PDF] algorithme écrit en langage naturel

[PDF] algorithme en langage naturel

[PDF] algorithme exercice corrigé 1ere année st pdf

[PDF] algorithme fonction exercice corrigé pdf

[PDF] algorithme informatique exercices corrigés

[PDF] algorithme informatique exercices corrigés pdf

[PDF] algorithme informatique pdf

[PDF] algorithme intubation difficile 2015

[PDF] algorithme intubation difficile sfar

[PDF] algorithme pour calculer les termes dune suite

[PDF] algorithme première es

[PDF] algorithme seconde algobox

[PDF] algorithme seconde calculatrice