ENPC - Objets et Patterns - Devoir de programmation

But du programme

Il s'agit de modéliser une version simplifiée du réseau de lignes de métro de la RATP que tout le monde connaît. Pour les tests grandeurs nature, les optimistes pourront y ajouter le réseau RER... Étant données les différentes stations considérées et les lignes qui les relient, l'objectif du programme est de fournir l'itinéraire le moins coûteux d'une station à une autre. "Moins coûteux" pourra signifier, selon la requête de l'utilisateur et selon les possibilités offertes par le programme, soit un nombre minimal de stations intermédiaires, soit un nombre de changement minimal, soit une distance ou un temps de parcours minimal, soit encore une combinaison de tous ces critères.

Comment s'y prendre

Il paraît raisonable de penser que cette modélisation prendra la forme d'un graphe, dans lequel chaque sommet du graphe correspond à une station de métro et chaque arc représente la portion d'une ligne reliant une station à une autre. Toute information relative au "coût" d'un arc devra être stockée.

L'objectif dans un premier temps est bien de modéliser le graphe et d'être capable, étant donné deux noms de stations fournies par un utilisateur, de lui fournir, en mode texte par exemple, l'itinéraire optimal pour aller de l'une à l'autre. On pourra même se limiter à une notion de côut réductrice pour simplifier l'algorithme (à condition de laisser la possibilité de l'y ajouter ultérieurement).

Les deux principaux intérêts que vous devrez porter à la réalisation de cette "base" du devoir de programmation sont, d'une part, la rigueur dans la modélisation et la structure objet de votre programme (hierarchie de classes, package, découpage cohérent, résistance aux modifications et améliorations, etc...) et, d'autre part, l'implantation et l'utilisation des algorithmes de manipulation de graphes. N'hésitez pas à simplifier le problème pour obtenir un protoype qui fonctionne, avant d'y réintroduire les difficultés progressivement.

Ensuite

Ensuite, et seulement ensuite, vous pourrez approfondir le travail dans une ou plusieurs directions de votre choix, afin d'apporter un "plus" à votre travail. Voici quelques piste parmi lesquelles vous pouvez choisir des idées d'amélioration de votre devoir "de base".

Ce qu'il faut rendre

Vous devrez rendre, par mail à Etienne.Duris[at]univ-mlv.fr et au plus tard le vendredi 14 mars 2003, les documents suivants:

Pour plus d'informations sur les archives, voir cet exemple.


Etienne.Duris[at]univ-mlv.fr - © École Nationale des Ponts et Chaussées - Février 2003 - http://www-igm.univ-mlv.fr/~duris/ENPC/