INF3105 — Structures de données et algorithmes
Été 2024
UQAM
Département d'informatique

TP4 - Recherche de suspects

Scène de crime

Objectifs

Problématique

Dans un monde dystopique, le gouvernement a décidé de mettre en place un système de surveillance de masse pour lutter contre la criminalité. Ce système consiste à collecter des données de localisation de tous les citoyens. Ces données sont ensuite analysées pour identifier des suspects potentiels lors d'enquêtes criminelles. Le gouvernement vous engage pour développer un logiciel qui permettra d'analyser ces données de localisation.

Votre tâche dans le cadre du TP4 est d'écrire un programme qui analyse des traces de localisation de personnes afin de répondre à des requêtes faites par des agences gouvernementales.

Structure du programme

Vous devez écrire un programme en C++ nommé tp4. Un squelette de départ, fortement recommandé mais optionnel, est disponible dans tp4.zip.

Syntaxe d'appel

Le programme tp4 doit pouvoir être lancé en ligne de commande avec la syntaxe suivante :

./tp4 [nomfichier]

où nomfichier est optionnel. Si nomfichier est spécifié, alors le programme doit lire dans nomfichier au moyen d'un flux de lecture C++ std::ifstream. Sinon, le programme doit lire dans l'entrée standard (stdin) au moyen du flux d'entrée C++ std::cin. À noter que cette fonctionnalité est déjà implémentée dans le squelette de départ.

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

Format de dates

Toutes les dates dans le TP4 sont spécifiées dans le format 0j_00h00m00s. Pour simplifier, il n'y a ni mois ni année. Ainsi, vous n'aurez pas à gérer le nombre de jours de chaque mois, les années bissextiles, les secondes intercalaires, etc. Un début d'implémentation d'une classe DateHeure est fourni dans les fichiers date.h et date.cpp. Vous pouvez la compléter ou créer votre propre type DateHeure.

Formats d'entrée et de sortie

Le programme tp4 reçoit un flux de commandes. Une commande peut être l'ajout d'une trace de localisation pour une personne ou une requête d'un agent. Chaque commande commence par un mot-clé donnant son type. Le tableau suivant détaille les 5 types de commandes possibles.

Commande Syntaxe et description
trace 
"trace" date nom_lieu nom_personne ';'

Enregistre une trace de localisation. Cela ajoute dans le journal de localisations qu'à la date date, la personne nom_personne était au lieu nom_lieu. La commande affiche "OK" sur une seule ligne.

Attention, les commandes de type trace peuvent être en désordre de dates, dû à des retards dans l'arrivée des données.

localiser 
"localiser" '[' date_debut ',' date_fin ']' nom_personne ';'

Affiche sur une ligne la liste des noms des lieux, séparés par un espace, où s'est trouvée la personne nom_personne dans l'intervalle [date_debut,date_fin]. La liste doit être triée en ordre alphabétique.

presences 
"presences" '[' date_debut ',' date_fin ']' nom_lieu ';'

Affiche sur une ligne la liste des noms, séparés par un espace, des personnes ayant visité au moins une fois le lieu nom_lieu dans l'intervalle [date_debut,date_fin]. La liste doit être triée en ordre alphabétique.

frequentations 
"frequentations" '[' date_debut ',' date_fin ']' nom_personne ';'

Affiche sur une ligne la liste des noms des personnes, séparés par un espace, qui ont pu être en contact (ont été dans un même lieu en même temps) avec nom_personne dans l'intervalle [date_debut,date_fin]. La liste doit être triée en ordre alphabétique.

duree_rencontres 
"duree_rencontres" '[' date_debut ',' date_fin ']'  nom_personne1 nom_personne2 ';'

Affiche sur une ligne la durée totale (en secondes) que les personnes nom_personne1 et nom_personne2 ont été dans le même lieu, en même temps, dans l'intervalle [date_debut,date_fin]. Puisque deux personnes peuvent s'être rencontrées dans plusieurs lieux différents dans l’intervalle, il faut faire la somme des durées de toutes leurs rencontres.

Hypothèses, simplifications et remarques

  1. Pour faciliter la lecture, les noms de personne et de lieu ne comportent aucun espace blanc. Ils peuvent donc être lus au moyen de std::cin >>.
  2. Pour toute date d, on suppose qu'une personne est au lieu de la dernière trace enregistrée à une date d' tel que d'≤d.
  3. Il peut y avoir des conflits dans les traces. Un conflit se produit lorsque plusieurs traces sont reçues pour la même date et la même personne. Lors d'un conflit, seule la dernière trace lue en entrée doit être considérée.
  4. Une commande trace avec le lieu «?» signifie qu'on a perdu la trace d'une personne.
  5. Le lieu «?» est distinct pour chaque personne. Deux personnes, pour qui on a perdu leur trace, ne doivent pas être considérées comme étant dans un même lieu.
  6. Lors d'une requête, on considère uniquement l'historique accumulé jusqu'à présent. Ainsi, les requêtes doivent être traitées dans l'ordre d'apparition dans le flux d'entrée.
  7. Malgré la syntaxe utilisant les crochets [ ], la fin d'un intervalle n'est pas une borne inclusive. Les intervalles [debut, fin] doivent être interprétés comme suit : un temps t est inclut dans [debut,fin] si et seulement si debut ≤ t < fin. Dans le cas d'un intervalle où debut = fin, il faut quand même considérer le temps t = debut. Exemple: une trace au temps 10 n'est pas considérée pour une requête ayant l'intervalle [0,10], mais l'est dans [10,15] et [10,10].

Exemple

Entrée (test00.txt) Sortie (test00+.txt) 
trace 0j_00h00m00s PK Alice ;
trace 0j_01h00m00s SH Alice ;
trace 0j_03h00m00s CO Benoit ;
localiser [0j_00h00m10s,0j_00h00m10s] Alice ;
localiser [0j_00h00m00s,6j_00h00m00s] Alice ;
trace 0j_01h00m50s SH Alice ;
trace 0j_02h00m00s SH Alice ;
trace 0j_05h00m00s ? Alice ;
presences [0j_00h00m00s,0j_05h00m00s] PK ;
frequentations [0j_00h00m00s, 0j_00h36m00s] Alice ;
trace 0j_00h30m00s PK Celine ;
trace 0j_00h35m00s PK Celine ;
presences [0j_00h00m00s,0j_05h00m00s] PK ;
trace 0j_00h45m00s ? Celine ;
trace 0j_04h00m00s Biblio Alice ;
trace 0j_04h30m00s ? Alice ;
trace 0j_07h45m00s CO Celine ;
frequentations [0j_00h00m00s, 0j_00h36m00s] Alice ;
duree_rencontres [0j_00h00m00s,0j_10h00m00s] Alice Celine ;
frequentations [0j_00h00m00s, 0j_08h00m00s] Benoit ;
 
OK
OK
OK
PK
PK SH
OK
OK
OK
Alice

OK
OK
Alice Celine
OK
OK
OK
OK
Celine
900
Celine

Étapes proposées

Pour bien réussir le TP4, il faut adopter une méthodologie incrémentale. Voici les étapes proposées.

  1. Complétez la classe DateHeure. Testez rigoureusement votre opérateur DateHeure::operator<(const Date&) const avec testdate.cpp.
  2. Complétez la classe ArbreMap (travail déjà amorcé au Lab8).
  3. Réfléchissez à comment représenter les données dans la classe Historique.
  4. Implémentez la commande trace.
  5. Implémentez la commande localiser.
  6. Implémentez la commande presences.
  7. Implémentez la commande frequentations.
  8. Implémentez la commande duree_rencontres.
  9. Considérez l'efficacité.

Contraintes

Bibliothèques permises

Vous devez implémenter et utiliser vos propres structures de données (classes génériques ArbreAVL et ArbreMap). L'utilisation des conteneurs de la bibliothèque standard de C++ (ex.: std::set, std::map, etc.) est permise, mais sujette à une pénalité (voir critère d'évaluation F). 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. Votre TP doit pouvoir être compilé avec g++ version 11 ou 13 (versions installées sur le serveur java.labunix.uqam.ca).

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. Si le travail est fait en équipe, tous les membres de l'équipe doivent soumettre le travail séparément, en indiquant bien dans le formulaire de remise l'autre membre de l'équipe. 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. La participation inadéquate des membres de l'équipe 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

Des tests sont disponibles dans tp4.zip. Puisque ces tests sont générés pseudo-aléatoirement, ils ne couvrent pas nécessairement tous les cas limites. La correction pourrait utiliser d'autres tests. Notez que les résultats des derniers tests (16 et +) ne sont pas et ne seront pas fournis.

Ce fichier ZIP contient un script d'auto-correction evaluer.sh. Notez que les limites par défaut sont de 240 secondes en temps CPU utilisateur et de 2 Go de mémoire alluée. Les tests dépassant l'une de ces limites seront interrompus.

Pour lancer les tests


cd tests
g++ -O3 -o valideur valideur.cpp
cd ..
make
./tests/evaluer.sh

Solution de base sur Intel Core i5-7600K

Évaluation du TP4 d'INF3105...
Limite de 240 secondes par test.
Évaluation des temps d'exécution de tp4 sur les jeux de tests.
Les résultats sont déposés dans log-20240628_171635.txt.
Machine :  jgareau-U24.04 .
CPU : Intel(R) Core(TM) i5-7600K CPU @ 3.80GHz
Date début : 20240628_171635.
Limite de 240 secondes par test.

Fichier test    Total   Mém.(k) Trace   Local   Prés    Freq    DR      Trace   Local   Prés    Freq    DR
test00.txt      0.00    3668k   0.00    0.00    0.00    0.00    0.00    12/12   2/2     2/2     3/3     1/1
test01.txt      0.00    3808k   0.00    0.00    0.00    0.00    0.00    55/55   5/5     5/5     5/5     5/5
test02.txt      0.00    3672k   0.00    0.00    0.00    0.00    0.00    83/83   10/10   10/10   10/10   10/10
test03.txt      0.00    3684k   0.00    0.00    0.00    0.00    0.00    213/213 25/25   25/25   25/25   25/25
test04.txt      0.00    3824k   0.00    0.00    0.00    0.00    0.00    389/389 50/50   50/50   50/50   50/50
test05.txt      0.00    3828k   0.00    0.00    0.00    0.00    0.00    140/140 12/12   12/12   12/12   12/12
test06.txt      0.00    3840k   0.00    0.00    0.00    0.00    0.00    269/269 25/25   25/25   25/25   25/25
test07.txt      0.00    3720k   0.00    0.00    0.00    0.00    0.00    471/471 50/50   50/50   50/50   50/50
test08.txt      0.00    3764k   0.00    0.00    0.00    0.00    0.00    1052/1052       125/125 125/125 125/125 125/125
test09.txt      0.01    3824k   0.00    0.00    0.00    0.01    0.00    2088/2088       250/250 250/250 250/250 250/250
test10.txt      0.00    3852k   0.00    0.00    0.00    0.00    0.00    300/300 25/25   25/25   25/25   25/25
test11.txt      0.00    3868k   0.00    0.00    0.00    0.00    0.00    497/497 50/50   50/50   50/50   50/50
test12.txt      0.00    3892k   0.00    0.00    0.00    0.00    0.00    882/882 100/100 100/100 100/100 100/100
test13.txt      0.01    3848k   0.00    0.00    0.00    0.00    0.00    2119/2119       250/250 250/250 250/250 250/250
test14.txt      0.04    4096k   0.00    0.01    0.01    0.02    0.01    4141/4141       500/500 500/500 500/500 500/500
test15.txt      0.03    4096k   0.00    0.00    0.01    0.02    0.00    4030/4030       500/500 500/500 500/500 500/500
test16.txt      3.38    6668k   0.08    0.10    0.86    2.51    0.09    41068/41068     5000/5000       5000/5000       5000/5000       5000/5000
test17.txt      24.20   10880k  0.23    0.26    6.13    18.58   0.27    102319/102319   12500/12500     12500/12500     12500/12500     12500/12500
test18.txt      64.86   15232k  0.41    0.46    18.74   51.81   0.47    164000/164000   20000/20000     20000/20000     20000/20000     20000/20000
test19.txt      92.40   18688k  0.58    0.60    25.01   80.46   0.69    204725/204725   25000/25000     25000/25000     25000/25000     25000/25000

Solution avancée avec arbres d'intervalles sur Intel Core i5-7600K

Évaluation du TP4 d'INF3105...
Limite de 240 secondes par test.
Évaluation des temps d'exécution de tp4 sur les jeux de tests.
Les résultats sont déposés dans log-20240628_174544.txt.
Machine :  jgareau-U24.04 .
CPU : Intel(R) Core(TM) i5-7600K CPU @ 3.80GHz
Date début : 20240628_174544.
Limite de 240 secondes par test.

Fichier test    Total   Mém.(k) Trace   Local   Prés    Freq    DR      Trace   Local   Prés    Freq    DR
test00.txt      0.00    3800k   0.00    0.00    0.00    0.00    0.00    12/12   2/2     2/2     3/3     1/1
test01.txt      0.00    3712k   0.00    0.00    0.00    0.00    0.00    55/55   5/5     5/5     5/5     5/5
test02.txt      0.00    3808k   0.00    0.00    0.00    0.00    0.00    83/83   10/10   10/10   10/10   10/10
test03.txt      0.00    3692k   0.00    0.00    0.00    0.00    0.00    213/213 25/25   25/25   25/25   25/25
test04.txt      0.00    3712k   0.00    0.00    0.00    0.00    0.00    389/389 50/50   50/50   50/50   50/50
test05.txt      0.00    3824k   0.00    0.00    0.00    0.00    0.00    140/140 12/12   12/12   12/12   12/12
test06.txt      0.00    3840k   0.00    0.00    0.00    0.00    0.00    269/269 25/25   25/25   25/25   25/25
test07.txt      0.00    3860k   0.00    0.00    0.00    0.00    0.00    471/471 50/50   50/50   50/50   50/50
test08.txt      0.00    3920k   0.00    0.00    0.00    0.00    0.00    1052/1052       125/125 125/125 125/125 125/125
test09.txt      0.00    3888k   0.00    0.00    0.00    0.00    0.00    2088/2088       250/250 250/250 250/250 250/250
test10.txt      0.00    3856k   0.00    0.00    0.00    0.00    0.00    300/300 25/25   25/25   25/25   25/25
test11.txt      0.00    3752k   0.00    0.00    0.00    0.00    0.00    497/497 50/50   50/50   50/50   50/50
test12.txt      0.00    3912k   0.00    0.00    0.00    0.00    0.00    882/882 100/100 100/100 100/100 100/100
test13.txt      0.00    4032k   0.00    0.00    0.00    0.00    0.00    2119/2119       250/250 250/250 250/250 250/250
test14.txt      0.01    4224k   0.00    0.01    0.01    0.01    0.01    4141/4141       500/500 500/500 500/500 500/500
test15.txt      0.02    4084k   0.00    0.01    0.01    0.01    0.01    4030/4030       500/500 500/500 500/500 500/500
test16.txt      0.81    7808k   0.11    0.12    0.31    0.48    0.13    41068/41068     5000/5000       5000/5000       5000/5000       5000/5000
test17.txt      4.92    14080k  0.28    0.33    1.93    3.27    0.33    102319/102319   12500/12500     12500/12500     12500/12500     12500/12500
test18.txt      11.48   20224k  0.49    0.54    4.37    7.34    0.59    164000/164000   20000/20000     20000/20000     20000/20000     20000/20000
test19.txt      14.88   24576k  0.61    0.69    5.43    9.72    0.74    204725/204725   25000/25000     25000/25000     25000/25000     25000/25000

Remise

Vous devez remettre votre travail au plus tard le 21 juillet 2024 à 23h59m59s via le formulaire de remise du TP4.

Fichiers à remettre:

  1. tp4.zip : fichier ZIP contenant tous les fichiers sources (*.{h,cpp}) et votre fichier Makefile (cela inclut les fichiers sources du squelette que vous n'auriez pas modifiés). Ne pas inclure d'autres fichiers dans le fichier ZIP (voir critère de correction A).

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

Évaluation

Ce travail pratique vaut 10% 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 (les fichiers fournis doivent être soumis, même si non modifiés).
  • Aucun fichier binaire (ex.: .o, .obj, .gch, exécutable, etc.).
  • Aucun fichier test.
  • Aucun fichier caché.
  • Aucun sous-dossier: tous les fichiers doivent être à la racine du fichier ZIP.
  • Remise par le formulaire Web. Pas de remise par courriel.
  • Compilable avec make sans modification.
  • Exécutable sans modification.
  • Auto-évaluation: la valeur choisie (Correctement / Partiellement / Aucunement) est correcte.
 10
B. Appréciation générale.
  • Structure du programme + Qualité du code :
    • Découpage du programme (tout n'est pas dans la fonction main()); pas de fonction trop longue; éviter la duplication de code.
    • 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 Region peut être justifiée/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.
 10
C. Fonctionnement correct.
  • C1 : commande localiser (10 points).
  • C2 : commande presences (15 points).
  • C3 : commande frequentations (15 points).
  • C4 : commande duree_rencontres (15 points).

Remarques : Bien que le critère C n'évalue pas directement l'efficacité, une inefficacité déraisonnable peut être considérée. En d'autres mots, un programme doit produire des résultats dans des temps raisonnables afin de pouvoir être évalué. Par exemple, un programme qui ne parvient pas à produire des résultats pour un test après 15 minutes d'exécution, alors qu'une solution raisonnable met seulement quelques secondes à s'exécuter, pourrait être arrêté et n'obtenir aucun point pour le test en cause.

55
D. Efficacité raisonnable.

Pour obtenir ces points, il faut utiliser judicieusement des arbres binaires de recherche. Tous les points sont accordés dès que les temps d'exécution ne dépassent pas le double de ceux d'une solution raisonnable.

Pour obtenir des points d'efficacité, il faut que vos commandes réussisent les tests de fonctionnement du critère C. Un programme incorrect mais efficace est généralement inutile ! 		25
  Total : / 100
E.

Boni : Efficacité supérieure des commandes presences et frequences.

Doit implémenter un arbre d'intervalles. Référence suggérée: Chapitre 17 de la 4e édition du livre Introduction to Algorithms de Cormen, Leiserson, Rivest et Stein.

 + 15
F. Pénalité: Utilisation de la STL.

Un des objectifs du TP4 est l'implémentation d'un arbreMap tel que présenté en classe et dans les notes de cours. Si vous éprouvez des difficultés à compléter votre propre implémentation d'arbreAVL / arbreMap, il est permis d'utiliser les conteneurs de la bibliothèque standard de C++, dont les classes std::set et std::map. Toutefois, une pénalité de 15 points sera appliquée.

- 15
  Note maximale: 115

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