INF3105 — Structures de données et algorithmes
Automne 2017
UQAM
Département d'informatique

Travail pratique #1 :
Système de recommandation pour les usagers de BIXI

Objectifs

Problématique

Vous devez écrire un programme C++ nommé tp1 qui assiste des usagers du BIXI, un système de location de vélos en libre-service. Le programme reçoit en entrée un état du réseau BIXI et liste de requêtes de déplacements à servir. Pour chaque requête, le programme affiche une recommandation. Il a 2 types de recommandations possibles :

  1. marcher jusqu'à une station BIXI, prendre un vélo, pédaler jusqu'à une autre station, et finalement marcher jusqu'à la destination finale;
  2. ou marcher directement jusqu'à la destination, et ce, sans utiliser de vélo.

Critère de recommandation et hypothèses simplificatrices

Votre programme doit recommander l'option la plus rapide en temps (nombre de secondes). Pour cela, on considère qu'un usager marche à une vitesse constante de 1 mètre par seconde (1 m/s), et roule à BIXI à une vitesse constante de 4 mètres par seconde (4 m/s). Afin de simplifier le problème, on suppose que les déplacements se font en ligne droite sur la surface la Terre. La distance entre deux point (coordonnées latitude et longitude) sur la carte se calcule avec la fonction PointST::distance() fournie. Celle-ci retourne la longueur en mètres en faisant l'hypothèse que la Terre est une sphère parfaite d'un rayon de 6371 km. Pour l'instant, les routes et les obstacles ne doivent pas être considérés. Nous verrons comment considérer les routes plus tard dans le cours (partie graphes).

Exemple 1

À titre d'exemple, voici une portion de la carte de Montréal avec quelques stations BIXI.

Supposons qu'un usager soit initialement localisé au pavillon Président-Kennedy de l'UQAM, soit aux coordonnées (45.509444, -73.568304). L'usager désire se rendre à la Grande Bibliothèque, soit aux coordonnées (45.515399, -73.561996). Pour cette requête, la meilleure option de déplacement est de :

  1. marcher jusqu'à la station Clark / Evans (17 vélos disponibles), et y prendre un vélo;
  2. pédaler jusqu'à la station Berri / de Maisonneuve (9 points d'ancrage disponibles), et y ancrer le vélo;
  3. marcher jusqu'à la destination finale.

Exemple 2

Supposons qu'un autre usager soit localisé au pavillon Adrien-Pinard de l'UQAM, soit aux coordonnées (45.510843, -73.569871). L'usager désire se rendre au restaurant Cégep du Vieux Montréal, soit aux coordonnées (45.514241, -73.567339). Pour cette requête, la meilleure option de déplacement est de marcher sans emprunter de vélo, car la station de l'Hôtel de Ville / Sherbrooke n'a aucun point d'ancrage disponible.

Traitement séquentiel des requêtes

Les requêtes doivent être traitées séquentiellement, c'est-à-dire qu'on suppose qu'il y a toujours qu'un seul déplacement à la fois.

Après chaque requête, le programme doit mettre à jour l'état du réseau BIXI selon la recommandation effectuée. La mise à jour de l'état est nécessaire pour répondre aux requêtes subséquentes. Par exemple, suite à la requête de l'exemple 1, il y aura 16 vélos et 2 points d'ancrage disponibles à la station Clark / Evans, et il y aura 23 vélos et 8 points d'ancrage disponibles à la station Berri / de Maisonneuve.

Les recommandations sont optimisées sur une base individuelle, c'est-à-dire qu'on ne considère que la requête courante. On ne doit pas considérer les requêtes suivantes. Par exemple, si on combine les exemples 1 et 2 ci-haut, un meilleur plan global aurait pu être de recommander au premier usager de rendre son vélo à University/des Pins, plutôt qu'à la station Hutchison/des Pins, afin qu'il soit disponible pour le deuxième usager. Effectuer de telles optimisations dépasse les objectifs du cours.

Structure du programme

Pour bien amorcer ce travail, il est fortement recommandé de commencer avec le squelette de départ fourni dans tp1.zip. Vous pouvez modifier ces fichiers autant que vous désirez. Toutefois, vous devez préserver la syntaxe d'appel du programme et ses formats d'entrée et de sortie. Cela est nécessaire pour la correction automatique.

Syntaxe d'appel du programme tp1

Le programme tp1 doit pouvoir être lancé en ligne de commande avec l'une des deux syntaxes suivantes :

./tp1 reseau-bixi.txt requetes.txt
./tp1 reseau-bixi.txt < requetes.txt

où :

Si requetes.txt est passé en argument (argv[2]), alors votre programme doit lire depuis le fichier nomfichier au moyen d'un flux de lecture de type std::ifstream. Sinon, votre programme doit lire dans l'entrée standard (stdin) au moyen du flux d'entrée std::cin. À noter que le squelette fourni implémente déjà cela.

Les résultats produits par votre programme doivent être écrits dans la sortie standard (stdout) à l'aide du flux de sortie C++ std::cout.

Fichier d'état d'un réseau BIXI

Un fichier de réseau BIXI est structuré de la façon suivante. Sur chaque ligne, on y retrouve une station BIXI spécifiée par les champs suivants :

Pour faciliter la lecture (le parsing) au moyen d'un flux de lecture std::istream, des tabulations ou des espaces blancs séparent les champs. De plus, les noms de station ne contiennent aucun espace blanc. Ainsi, ils peuvent être lus au moyen d'un seul appel à l'opérateur >>.

À titre d'exemple, voici un extrait du fichier d'entrée montreal-bixi.txt fourni.

1	Hotel-de-Ville_2_(du_Champs-de-Mars_/_Gosford)	(45.509310285552,-73.554431051016)	13	2
2	Ste-Catherine_/_Dezery	(45.539230296982,-73.541082367301)	4	19
3	Clark_/_Evans	(45.511132280739,-73.567907139659)	17	1
4	Hotel-de-Ville_(du_Champs-de-Mars_/_Gosford)	(45.509228519662,-73.554469943047)	13	22
5	Metcalfe_/_Square_Dorchester	(45.500233546666,-73.571126461029)	29	2
6	18e_avenue_/_Rosemont	(45.557895457529,-73.576529100537)	1	22
7	de_l'Hotel-de-Ville_/_Ste-Catherine	(45.511640093571,-73.562183976173)	10	13
8	Sanguinet_/_Ste-Catherine	(45.512734,-73.5611406)	25	10
9	Ste-Catherine_/_Labelle	(45.515051758517,-73.559221476316)	14	9
10	Ste-Catherine_/_St-Denis	(45.513833539884,-73.560445904732)	3	16
11	St-Andre_/_St-Antoine	(45.5140873,-73.55230004)	16	15
12	Metro_St-Laurent_(de_Maisonneuve_/_St-Laurent)	(45.51066,-73.56497)	35	14
13	Sanguinet_/_de_Maisonneuve	(45.513542213035,-73.562870621681)	12	19
14	St-Denis_/_de_Maisonneuve	(45.514395514513,-73.561765551567)	16	11
15	Berri_/_de_Maisonneuve	(45.515299,-73.561273)	22	9
...

Fichier de requêtes

Chaque requête est spécifiée sur une seule ligne. Une requête est spécifiée par un point d'origine et un point de destination.

À titre d'exemple, voici le fichier montreal-req0.txt. Ce dernier contient les deux requêtes des exemples 1 et 2 des sections 2.2 et 2.3 ci-haut.

(45.509444, -73.568304) (45.515399, -73.561996)
(45.510843, -73.569871) (45.514241, -73.567339)

Sortie

Les recommandations calculées par le programme doivent être écrites dans la sortie standard (stdout) à l'aide du flux de sortie C++ std::cout. Chaque recommandation est écrite sur une seule ligne.

Le format de sortie varie selon le type de recommandation :

Il est très important de respecter ce format de sortie, car des scripts de correction seront utilisés. Les durées affichées doivent être arrondies à la seconde près à l'aide de la fonction round().

Durant le développement, il est recommandé d'utiliser le flux standard d'erreur C++ std::cerr pour afficher des messages de débogage. Ainsi, si vous oubliez d'enlever des messages de débogage, ces derniers ne seront pas redirigés dans le fichier de sortie.

L'exécution de la commande

./tp1 montreal-bixi.txt montreal-req0.txt

doit produire le résultat (montreal-req0+.txt) :
Clark_/_Evans --> Berri_/_de_Maisonneuve 421 s
Marche 426 s

Algorithme

Voici le pseudocode partiel (à compléter) d'un algorithme suggéré pour effectuer une recommandation utilisant exactement 1 vélo.

Entrées : origine, destination;

meilleur_temps = +infini;
Pour toutes les stations i :
    Pour toutes les stations j :
        Si la station i a aucun vélo disponible, ignorer;
        Si la station j a aucun point d'ancrage disponible, ignorer;
        tempsMarche1 = distance(origine, stations[i].coor) / vitesse_marche;
        tempsVelo = distance(stations[i].coor, stations[j].coor) / vitresse_velo;
        tempsMarche2 = distance(stations[j].coor, destination) / vitesse_marche;
        temps = tempsMarche1 + tempsVelo + tempsMarche2;
        si temps < meilleur_temps :
            meilleur_temps = temps;
            (sol1, sol2) = (i,j);
Afficher stations[sol1].nom, " --> ", stations[sol2].nom, " ", meilleur_temps, " s";

Contraintes

Librairies permises

Vous devez implémenter et utiliser vos propres structures de données. Pour l'instant, l'utilisation des conteneurs de la librairie standard de C++ (Standard Template Library) n'est pas permise. Ce sera permis plus tard dans le cours.

Environnement de développement

Relisez les Politiques et les directives sur les outils informatiques dans le cours INF3105.

Taille des équipes

Vous pouvez faire ce travail en équipe de 1 ou 2. Toutefois, tous les membres de l'équipe doivent contribuer à l'ensemble du travail et non à seulement quelques parties. Le travail d'équipe vise à favoriser les discussions et l'entraide. Le travail d'équipe ne vise pas à réduire la tâche. Ainsi, se diviser la tâche en deux n'est pas une méthode de travail d'équipe appropriée dans ce cours. Tous les membres de l'équipe doivent être en mesure de comprendre et d'expliquer l'ensemble du travail. La participation inadéquate d'une étudiante ou d'un étudiant peut être considérée comme du plagiat. Le professeur et le correcteur pourront sélectionner quelques équipes au hasard afin de vérifier que tous les membres sont capables d'expliquer l'ensemble du travail.

Tests et Interface graphique

Des tests sont disponibles dans tp1-tests.zip.

Exécution des tests sur votre propre machine

Pour exécuter les tests, vous devez décompresser le fichier tp1-tests.zip. Les fichiers tests et le script evaluer.sh ne doivent pas être dans le même répertoire que votre programme tp1. Le script utilise un valideur qui doit être compilé une fois.

Si vous êtes sous macOS et que tp1-tests.zip a été téléchargé avant le 4 octobre à 13h40, il faut corriger la ligne #145 du script evaluer.sh en enlevant le premier caractère $ (dollar) immédiatement devant tp1.
t=`(time -p ./$tp1 ...
t=`(time -p ./tp1 ...

cd tp1
make tp1
wget http://ericbeaudry.uqam.ca/INF3105/tp1/tp1-tests.zip
unzip tp1-tests.zip
cd tests
g++ valideur.cpp -o valideur
cd ..
./tests/evaluer.sh
Évaluation du TP1 d'INF3105...
...

Test	Stations	Requêtes	CPU	Mém	NbOK
ottawa-req0.txt	23	1	0.00	3688	1	OK
ottawa-req1.txt	23	10	0.00	3672	10	OK
ottawa-req2.txt	23	50	0.00	3632	50	OK
ottawa-req3.txt	23	100	0.00	3788	100	OK
ottawa-req4.txt	23	500	0.01	3668	500	OK
...

Si GnuPlot est installé sur votre machine, le script d'auto-évaluation evaluer.sh produira 4 fichiers : graphique[12].{pdf,png} qui pourraient vous aider à valider votre analyse de la complexité temporelle. Le premier graphique trace les courbes de temps pour tous les tests. Le deuxième graphique trace la courbe du temps d'exécution en fonction du nombre de stations, et ce, pour 5000 requêtes. Attention, le script evaluer.sh limite le temps d'exécution à 180 secondes. Voici deux exemples de graphiques.

Exécution des tests sur le serveur Malt

Les fichiers tests sont déjà dans le répertoire /home/inf3105/tp1/. Vous n'avez pas besoin de télécharger tp1-tests.zip.

ssh votre_codems@malt.labunix.uqam.ca
cd tp1
make tp1
/home/inf3105/tp1/evaluer.sh
Évaluation du TP1 d'INF3105...
...

Test	Stations	Requêtes	CPU	Mém	NbOK
ottawa-req0.txt	23	1	0.00	1384	1	OK
ottawa-req1.txt	23	10	0.00	1392	10	OK
ottawa-req2.txt	23	50	0.00	1400	50	OK
ottawa-req3.txt	23	100	0.00	1400	100	OK
ottawa-req4.txt	23	500	0.00	1400	500	OK
...

À la fin, le script produit 4 fichiers : graphique[12].{pdf,png} à l'aide de GnuPlot. Voir la sous-section précédente pour plus de détails.

Interface graphique

Pour vous aider à visualiser des réseaux BIXI et à générer vos propres tests, une visionneuse est fournie avec dans tp1.zip (visionneuse.jar).

Utilisation:

Remise

Vous devez remettre électroniquement le TP1 au plus tard le dimanche 15 octobre 2016 à 24h00 (la minute suivante 23h59). La remise papier doit être remise avant le début du cours suivant cette date.

Remise électronique

Vous devez remettre tous vos fichiers sources, incluant un fichier Makefile, via le système Oto. Il est recommandé d'effectuer la remise en ligne de commande sur le serveur oto.labunix.uqam.ca.

Avant de soumettre votre travail, il est fortement conseillé de le vérifier. Exemple :

oto verifier_tp beaudry_er INF3105-TP1 Makefile *.h *.cpp

Exemple de commande pour remettre votre TP1:

oto rendre_tp beaudry_er INF3105-TP1 CODE00000001,CODE00000002 Makefile *.h *.cpp

Exemple de commande pour obtenir une confirmation de remise:

oto confirmer_remise beaudry_er INF3105-TP1 CODE00000001,CODE00000002

Vous pouvez aussi utiliser l'application Web d'Oto. À noter que la vérification peut ne pas fonctionner correctement via l'application Web.

Vous pouvez soumettre votre TP autant de fois que vous voulez. Seule la dernière soumission sera considérée.

Remise papier

La partie papier est constituée du/d'un(e)/de:

  1. Formulaire de remise imprimé [ PDF | OpenDocument | Word ], dûment rempli et signé.
  2. Auto-évaluation indiquant si votre programme fonctionne correctement, partiellement ou aucunement.
  3. Un tableau montrant les temps d'exécution sur les fichiers tests fournis.
    • Si un test prend plus de 60 secondes, vous pouvez l'arrêter et simplement écrire >60 dans votre rapport.
    • Vous pourrez générer un rapport automatiquement en lançant la commande /home/inf3105/tp1/evaluer.sh sur malt.labunix.uqam.ca à partir du répertoire où vous avez compilé votre exécutable tp1.
  4. Analyse de la complexité temporelle (pire cas) en notation grand O
    • La complexité temporelle doit être exprimée en fonction de la taille du problème :
      • n indique nombre de stations BIXI;
      • m indique nombre de requêtes.
  5. Code source.
    • Imprimez tout votre code source.
    • L'impression doit être fait à l'aide d'un éditeur de texte mettant la syntaxe C++ en évidence, comme GEdit ou Notepad++.
    • N'imprimez pas depuis un logiciel de traitement de texte comme Word.
    • Pour réduire la consommation de papier, SVP, imprimez dans un format 2 pages par côté de feuille et en recto verso (4 pages par feuille).
    • Le code source doit être présenté dans un ordre convenable. Par exemple, un fichier d'entête (.h) devrait venir immédiatement le fichier source (.cpp) correspondant.

Brochez le tout. Évitez les trombones. Il n'est pas nécessaire d'insérer le tout dans une grande enveloppe.

Vous pouvez aussi remettre la partie papier dans la chute à travaux tout juste à gauche de la première porte du PK-4151. Vous pouvez aussi remettre au début d'un cours.

Les correcteurs vous feront des commentaires constructifs directement sur la partie papier qui vous sera ensuite retournée.

Évaluation

Ce travail pratique vaut 15% de la note finale.

Grille de correction

Critère Description Pondération
A. Respect des directives pour la remise
  • Fichiers sources seulement (ex.: .h, .cpp, Makefile). Aucun fichier source manquant. Aucun fichier binaire (.o, exécutable). Aucun fichier test.
  • Remise par Oto. Pas de remise par courriel.
  • Compilable avec make sans modification.
  • Exécutable sans modification.
/ 2
B. Appréciation générale
  • Structure du programme + Qualité du code :
    • Découpage du programme (tout n'est pas dans la fonction main()).
    • Choix des types de données; identificateurs (noms) significatifs, lisibilité du code, pertinence des commentaires; etc.
    • Justesse de l'usage du mot clé const, des références (&) et des pointeurs (*).
  • Encapsulation :
    • Respect des principes de l'abstraction;
    • Cachez le maximum de la représentation des objets en rendant un maximum d'attributs privés;
    • Évitez autant que possible les bris d'abstraction, comme des getters et setters qui retournent ou affectent directement des attributs d'un type abstrait de donnée. Par exemple, les fonctions getX() et getY() ne devraient pas exister dans une classe Point. Mais, une fonction getNom()dans une classe Personne peut être justifiée dont tolérée.
    • Utilisation appropriée des modificateurs d'accès public, protected et private, et du mot clé friend, etc.
  • Gestion de la mémoire :
    • Toute la mémoire allouée dynamiquement doit être correctement libérée au moment approprié et avant la fin du programme.
/ 3
C. Fonctionnement correct.
Le programme produit les bonnes recommandations. Une recommandation non optimale est considérée mauvaise même si elle est très proche de l'optimale.
L'efficacité n'est pas directement évaluée. Cependant, l'efficacité peut être indirectement évaluée lorsqu'un programme ne parvient pas à produire des résultats dans des délais raisonnables. Votre programme doit également consommer une quantité de mémoire raisonnable.
/ 7
D. Exactitude de l'auto-évaluation.
Vous déclarez que votre programme fonctionne ...
Correctement Partiellement Aucunement (Déclaration absente)
À la correction, votre programme fonctionne correctement (C=7) 1 0.5 0 0
À la correction, votre programme fonctionne partiellement (0<C<7) 0.5 1 0.5 0
À la correction, votre programme ne fonctionne aucunement (C=0) 0 0 1 0

Attention : les tests fournis ne sont pas nécessairement ceux qui seront utilisés pour la correction. De nouveaux tests pourront être utilisés.

/ 1
E. Analyse de l'algorithme.
  • Complexité temporelle en notation grand O.
  • Ordre de grandeur simplifié. Ex: O(2n) ==> O(n).
  • Justification. La justification sert à démontrer la complexité temporelle obtenue. Elle n'a pas besoin d'être longue. Un tiers à une demie page peut suffire. Votre justification peut être scindée en plusieurs parties indépendantes, comme le chargement des données, les calculs préalables s'il y en a, et le traitement des requêtes. Vous pouvez écrire le pseudocode du coeur de votre programme, un peu comme à la section 3.5, et ensuite annoter l'analyse ligne par ligne pour dénombrer le nombre d'opérations.
/ 2
Total : / 15
F. Efficacité (boni).

  1. Jusqu'à 1 point boni peut être accordé si votre programme s'exécute significativement plus rapidement que les temps médians des programmes du groupe.
  2. Un deuxième point boni peut être accordé à l'équipe qui aura les meilleurs temps d'exécution.

Avertissements :

  1. Pour être éligible aux points bonis, il faut obtenir 7/7 au critère C.
  2. Implémenter une version efficace peut parfois demander beaucoup de temps et être une source de bogues, et ce, pour seulement 1 point boni.
  3. Il existe souvent un compromis entre l'efficacité d'un logiciel et ses autres qualités, comme le fonctionnement correct, la robustesse, la lisibilité du code, la maintenabilité, etc. Vous devez donc être prudents. Évitez les sacrifices qui pourraient vous pénaliser aux autres critères dont B, C et E.
+ 2
Note maximale : 17 / 15

Pour les cas problématiques, jusqu'à 2 points peuvent être retranchés pour la qualité de la langue et de la présentation.

Crédits et licences