ECOLE NORMALE SUPÉRIEURE DE اﻟﻤﺪرﺳﺔ اﻟﻌﻠﯿﺎ ﻸﺳﺎﺗﺬة اﻟﺘﻌﻠﯿﻢ اﻟﺘﻘﻨﻲ
L'ENSEIGNEMENT
TECHNIQUE DE MOHAMMEDIA
UNIVERSITÉ HASSAN II DE CASABLANCA
ENSET اﻟﻣﺣﻣدﯾﺔ
ﺟﺎﻣﻌﺔ اﻟﺤﺴﻦ اﻟﺜﺎﻧﻲ ﺑﺎﻟﺪار اﻟﺒﯿﻀﺎﺀ
1
Examen Rattrapage de Recherche Opérationnelle
Durée : 2 heures
Exercice 1 : Algorithme à découvrir.
Le but de cet exercice est de découvrir ce que fait l’algorithme, Mystère et Boule de
Gomme, ci-dessous.
1. Appliquer l’algorithme, Mystère et Boule de Gomme, au graphe à la figure 1.
2. Que contient pour un sommet ? A quoi sert le tableau ? que représentent les
sorties et de cet algorithme pour un graphe donné ?
3. Expliquez pourquoi on ne peut pas garantir que l’algorithme termine pour
n’importe quel graphe. Donnez un exemple d’un graphe pour lequel
l’algorithme ne termine pas.
4. Décrire des changements raisonnables à apporter à l’algorithme pour que
celui-ci termine toujours.
ECOLE NORMALE SUPÉRIEURE DE اﻟﻤﺪرﺳﺔ اﻟﻌﻠﯿﺎ ﻸﺳﺎﺗﺬة اﻟﺘﻌﻠﯿﻢ اﻟﺘﻘﻨﻲ
L'ENSEIGNEMENT
TECHNIQUE DE MOHAMMEDIA
UNIVERSITÉ HASSAN II DE CASABLANCA
ENSET اﻟﻣﺣﻣدﯾﺔ
ﺟﺎﻣﻌﺔ اﻟﺤﺴﻦ اﻟﺜﺎﻧﻲ ﺑﺎﻟﺪار اﻟﺒﯿﻀﺎﺀ
1
Figure 1.
Problème: Arborescence des Plus Courts Chemins et Arbre Couvrant de Poids
Minimum.
A. Le graphe non orienté pondéré donné ci-dessous montre les différentes
possibilités de connecter 10 machines entre elles. Le poids d’une arête
désigne le coût des ressources nécessaires pour connecter deux machines.
Figure 2
1) On veut connecter ces 10 machines avec le minimum de ressources. A
quel type de problème formel peut-on associer cette situation ? Préciser
alors l’algorithme qui peut résoudre ce problème.
2) Appliquer l’algorithme adéquat, selon vous, au graphe de la figure 2
modélisant le problème évoqué en question 1 (Commencer avec le
sommet A).
3) A quoi correspond la solution retournée par l’algorithme que vous avez
appliqué en question 2. Dessiner graphiquement cette solution.
B. Considérer le graphe orienté pondéré de la figure 3.
ECOLE NORMALE SUPÉRIEURE DE اﻟﻤﺪرﺳﺔ اﻟﻌﻠﯿﺎ ﻸﺳﺎﺗﺬة اﻟﺘﻌﻠﯿﻢ اﻟﺘﻘﻨﻲ
L'ENSEIGNEMENT
TECHNIQUE DE MOHAMMEDIA
UNIVERSITÉ HASSAN II DE CASABLANCA
ENSET اﻟﻣﺣﻣدﯾﺔ
ﺟﺎﻣﻌﺔ اﻟﺤﺴﻦ اﻟﺜﺎﻧﻲ ﺑﺎﻟﺪار اﻟﺒﯿﻀﺎﺀ
1
Figure 3
1) Rappeler les conditions d’applicabilité des algorithmes de Bellman-Kalaba et
Dijkstra et simuler leurs exécutions sur le graphe de la figure 3.
2) En déduire les arborescences associées respectivement aux simulations des
deux algorithmes.
3) Ordonner le graphe de la figure 3 par niveaux.