Cette année encore, la canicule a fait rage sur le campus de l'université. Heureusement, les arbres et espaces verts ont aidé les usagers à supporter la température. Afin d'améliorer la situation, l'université aimerait planter des arbres de sorte que toutes les zones utilisées soient couvertes par leur fraîcheur. Cependant les arbres ne peuvent pas être plantés dans des zones bétonnées et doivent être remplacés par des parasols, moins efficaces. Les zones bétonnées reflètent la chaleur ce qui limite également la propagation de la fraîcheur.
Le projet se déroulera en plusieurs étapes :
Concernant l’organisation :
On vous propose les problèmes suivant: Comment placer les arbres de sortes que l'ensemble des zones utilisées du campus (trottoirs etc...) soient couvertes par de l'ombre ? Quel est le nombre minimal d'arbres à placer pour couvrir ces zones ?
Dans un second temps vous considérerez des problèmes annexes avec les parasols et la variation de la distance couverte en fonction du terrain.
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 le projet, vous aurez besoins des données cartographique du campus. Celles-ci peuvent-être récupérée via openstreetmap, par exemple en utilisant des requêtes overpass. Vous pouvez également utiliser d'autres sources ouvertes que vous trouveriez. osmnx pourrait également vous être utile si vous choisissez de faire votre projet en python
Chaque groupe préparera mini présentation de la modélisation. Les outils choisis pour la réalisation seront présenté également
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)
Pensez à commencer un rapport pour les prochains rendus.
Vous rédigerez un rapport reprenant les éléments suivants: