Scribd
Importer
0 vues2 pages

serie2M1IDIAG

Le document présente une série d'exercices sur la théorie des graphes, en utilisant les algorithmes de Dijkstra et de Bellman pour résoudre des problèmes de cheminement et de coût. Les exercices incluent la recherche de chemins les plus courts dans des graphes avec des arcs de longueurs négatives, ainsi que l'optimisation des coûts de construction d'une autoroute. Un dernier exercice aborde la maximisation des gains d'un trader sur le marché des devises en utilisant un graphe pour modéliser les échanges.

Transféré par

mohamedgassenboughalmi
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
0 vues2 pages

serie2M1IDIAG

Le document présente une série d'exercices sur la théorie des graphes, en utilisant les algorithmes de Dijkstra et de Bellman pour résoudre des problèmes de cheminement et de coût. Les exercices incluent la recherche de chemins les plus courts dans des graphes avec des arcs de longueurs négatives, ainsi que l'optimisation des coûts de construction d'une autoroute. Un dernier exercice aborde la maximisation des gains d'un trader sur le marché des devises en utilisant un graphe pour modéliser les échanges.

Transféré par

mohamedgassenboughalmi
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

Ecole Supérieure de Commerce de Tunis M1 IDIAG

Génie Algorithmique: (Théorie des graphes)


Enseignante : Dalila TAYACHI
SERIE 2. Problèmes de cheminements

Exercice 1. Appliquer l’algorithme de Dijkstra pour obtenir les plus courts chemins de 1 à
tous les autres sommets du graphe suivant :

3
2 4 3
8
8
2 1 1
1 1
1 3

3 1 1 1 7
5 6

 Trouver une instance de graphe qui a des arcs de longueurs négatives et ne possède
pas de circuit négatif, sur laquelle l’algorithme de Dijkstra ne donne pas satisfaction

Exercice 2. Trouver à partir de l’algorithme de Dijkstra le chemin le plus court de a à z.

7
b d
1 2
10
2 3
a z
4
2 c e
1

Exercice 3. Considérons le projet de construction d’une autoroute entre les villes 1 et 8.


Les arcs représentent les différents tronçons possibles de l’autoroute. Chaque arc est valué
par le coût total de réalisation du tronçon correspondant.

1
3 2
3 5
5
7 6
1 4 5
3 7

2 8 5
7 6 8
4

4 9

En utilisant l’algorithme de Bellman, déterminer le tracé dont le coût total de construction est
minimum et celui dont le coût total de construction est maximum.

Exercice 4. Un trader se trouve devant la possibilité d’intervenir, sans aucun frais fixe, sur
le marché des devises en $, ¥, £, €. A un moment donné, il observe les taux de change
suivants :
€ $ £ ¥
€ - 1.256 0.673 127

$ 0.796 - 0.536 109

£ 1.486 1.867 - 203

¥ 0.0073 0.092 0.005 -

Disposant d’un capital initial en euros, le trader cherche à déterminer les séquences
d’échanges permettant de faire fructifier au mieux ce montant à un horizon k (c'est-à-dire
qu’on se donne au plus k échanges au terme desquels on souhaite disposer d’une somme en
euros qui soit la plus grande possible). On suppose que les taux de change sont stables sur
la période considérée.
 Définir un graphe sans circuit qui permette de formuler ce problème comme un
problème de chemin de valeur maximale, pour un horizon k donné (préciser ce que
représentent les arcs du graphe, les valeurs des arcs et comment on définit la valeur
d’un chemin).
 Appliquer l’algorithme de Bellman pour résoudre ce problème pour k=3.

Vous aimerez peut-être aussi