Pendant les derniers jeux olympiques et paralympiques l'accessibilité du métro a été critiquée. Pour remédier à cela, nous vous demandons de sélectionner un ensemble de stations de métro à aménager en priorité afin de pouvoir accéder à tous les sites olympiques. L'objectif est de minimiser le nombre de stations à aménager afin de pouvoir répondre rapidement au besoin.
Le projet se déroulera en plusieurs étapes :
Concernant l’organisation :
Dans un premier temps on vous propose le problème suivant: Trouvez le plus petit ensemble de stations à aménager qui permettent que tous les sites olympiques soient à au plus x minutes de marche d'une station de métro accessible. (x étant un paramètre)
On vous suggère dans un second temps d'autres problèmes en bonus: trouvez les stations à aménager de sorte que dans le nouveau réseau comprenant les stations accessibles le chemin le plus court entre deux sites olympiques comprenne au plus x minutes de marche. (en tenant compte des changements de lignes)
Vous pourrez également proposer vos propres variantes du problèmes en justifiant pourquoi elles sont pertinentes.
Vous présenterez vos résultats de manière graphique afin de faciliter la compréhension de ce que vous proposez.
Pour réaliser ce projet, vous aurez besoin de la localisation des sites olympiques et des stations de métro qui sont disponibles en opendata.
Vous aurez aussi besoin du graphes du réseau routier/pétitionner de Paris, vous pouvez utiliser par exemple osmnx si vous choisissez de faire votre projet en python ou n'importe quel autre bibliothèque utilisant openstreetmap.
Pensez à commencer un rapport pour les prochains rendus.
ensemble_dominant(graphe G, dominant partiel S, entier k)
si k = 0 :
tester si S est un dominant
sinon :
u <- sommet de degré min parmi les sommets non dominés par S
pour tout v dans N[u] :
ensemble_dominant(G, S U {v}, k-1)
Pour ce rendu un petit rapport vous est demandé (txt ou pdf selon votre choix).
Pour chaque algo vous réaliserez des tests sur différentes instances afin de déterminer leur performances.
Le rendu final devra être envoyé au plus tard le 20/01.
Ce rendu reprend tous les points des précédents rendu, dans le rapport vous penserez bien à préciser les détails de vos implémentations, votre méthode de travail et d'évaluation des algorithmes (tests et benchmarks), vos optimisations des algorithmes demandés et les limites de votre projet.
Vous décrirez de manière précise comment exécuter votre projet sur les machines du CREMI avec des exemples. Le projet sera principalement évalué sur le rapport, tout ce qui n'est pas expliqué dans le rapport ne sera pas considéré
La soutenance aura lieu le 23/01 au CREMI (A28 salle 203). Celles-ci dureront 20 à 25 minutes.
Voici les horaires de passage pour chaque groupe :
Nous vous demandons d’entrer discrètement dans la salle 10 minutes avant votre horaire et de vous installer sur un ordinateur afin d’éviter toute perte de temps. Vous devrez présenter rapidement ce que vous avez fait, puis nous vous poserons des questions à propos de votre projet. Vous pouvez utiliser des slides, mais ce n’est pas obligatoire.