OEF ordonnancement
--- Introduction ---

Ce module regroupe pour l'instant 15 exercices sur les problèmes d'ordonnancement et les graphes orientés sans circuit (niveaux, chemin minimal, problèmes de modélisation).

Algorithme de calcul des niveaux

Voici un graphe orienté sans circuit . On désire classer les sommets selon leur niveau en faisant toutes les étapes de l'algorithme.

Etape : Chercher les sommets de niveau . Calculer le nombre de précédents de chaque sommet dans le graphe obtenu à partir de en enlevant les sommets dont le niveau a déjà été trouvé puis donner la liste des sommets de niveau :

Points
Nombre de précédents dans
Sommet(s) de niveau :
Sommet(s) de niveau :

Entrée et sortie

Voici un graphe orienté sans circuit. On lui rajoute une entrée alpha et une sortie omega. Quels sont les suivants de alpha ? Quels sont les précédents de omega ? (il s'agit d'en prendre le moins possible).

Dictionnaire et niveau

Soit un graphe défini par le dictionnaire des . Calculer la matrice booléenne des suivants du graphe (on séparera les éléments d'une ligne par des virgules).

SommetsSes
  
La matrice booléenne des suivants est

.

Sa matrice transposée est la matrice

.

Calculer le niveau de chacun des sommets :
Sommet
Niveau

Placer les sommets

Soit un graphe sans circuit défini par le dictionnaire des . On lui rajoute une entrée alpha et une sortie omega. Compléter le graphe par niveau tracé à côté :

SommetsSes
  

Elimination

Voici la matrice booléenne des précédents d'un graphe orienté sans circuits.

Remplissez le tableau des précédents et des précédents des précédents (si un élément n'en a pas, mettre une étoile : *).

SommetsPrécédents Précédents des précédents
       
On obtient le tableau

SommetsPrécédents Précédents des précédents
     
Lorsqu'on étudie un problème d'ordonnancement, on peut éliminer une arête si un chemin existe. Donner le tableau des précédents obtenus en éliminant les informations inutiles détectées par ce calcul :
SommetsPrécédents
   
Donner la matrice du nouveau graphe obtenu :

Liaisons

 
euro
h.  
Donner une solution parmi les plus économiques en nommant le nom des villes par leur initiale et en commençant par et en finissant par à . Quel prix faut-il prévoir ? Donner une solution parmi les plus rapides en nommant le nom des villes par leur initiale et en commençant par et en finissant par à . Quelle est la durée du trajet (sans compter les escales) ?

Longueur minimale et maximale

 
 

Plus grande distance

 
 
:

Classer les sommets par niveau I

Voici un graphe orienté sans circuit. Classer les sommets selon leur niveau :
Sommet(s) de niveau :
Sommet(s) de niveau :

Classer les sommets par niveau II

Voici un graphe orienté sans circuit. Classer les sommets selon leur niveau :
Sommet(s) de niveau :
Sommet(s) de niveau :

Graphe sans circuits et niveau

Voici un graphe orienté sans circuit. Calculer le niveau de chacun des sommets

Sommet a
Niveau

Niveaux sur le graphe

Voici un graphe orienté sans circuit. Remplir les cases avec le niveau de chacun des sommets :

Ordonnancement d'un projet

Etape 1 : Calculer la date au plus tôt de début de chaque tâche.

Etape 2 : La durée minimale du projet est donc de semaines

Etape 3 : Calculer la date au plus tard de début de chaque tâche.

Etape 4 : Donner la liste des tâches critiques (s'il n'y en a pas, écrire vide ):

     
Sommet
Début au plus tôt
Début au plus tard

Ordonnancement d'un projet, marges

Etape 1 : Calculer la date au plus tôt de début de chaque tâche.

Etape 2 : La durée minimale du projet est donc de semaines

Etape 3 : Calculer la date au plus tard de début de chaque tâche.

Etape 3 : Calculer la marge de chaque tâche.

Etape 4 : Donner la liste des tâches critiques (s'il n'y en a pas, écrire vide ):

     
Sommet
Début au plus tôt
Début au plus tard
Marge

Ordonnancement d'un projet modélisé

Etape 1 : Calculer la date au plus tôt de début de chaque tâche.

Etape 2 : La durée minimale du projet est donc de semaines

Etape 3 : Calculer la date au plus tard de début de chaque tâche.

Etape 4 : Donner la liste des tâches critiques (s'il n'y en a pas, écrire vide ):

     
Sommet
Début au plus tôt
Début au plus tard

Cette page n'est pas dans son apparence habituelle parce que WIMS n'a pas pu reconnaître votre navigateur de web.

Pour accéder aux services de WIMS, vous avez besoin d'un navigateur qui connait les formes. Afin de tester le navigateur que vous utilisez, veuillez taper le mot wims ici : puis appuyez sur ``Entrer''.

Veuillez noter que les pages WIMS sont générées interactivement; elles ne sont pas des fichiers HTML ordinaires. Elles doivent être utilisées interactivement EN LIGNE. Il est inutiles pour vous de les ramassez par un programme robot.

Description: collection d'exercices sur les graphes sans circuits et les méthodes d'ordonnancement. This is the main site of WIMS (WWW Interactive Multipurpose Server): interactive exercises, online calculators and plotters, mathematical recreation and games

Keywords: wims, mathematics, mathematical, math, maths, interactive mathematics, interactive math, interactive maths, mathematic, online, calculator, graphing, exercise, exercice, puzzle, calculus, K-12, algebra, mathématique, interactive, interactive mathematics, interactive mathematical, interactive math, interactive maths, mathematical education, enseignement mathématique, mathematics teaching, teaching mathematics, algebra, geometry, calculus, function, curve, surface, graphing, virtual class, virtual classes, virtual classroom, virtual classrooms, interactive documents, interactive document, operational research, graph, algorithmic, circuit,graphe,ordonnancement, potentiel, tache,pert,recherche opérationnelle