INF3105 — Structure de données et algorithmes
Automne 2016
Regardez brièvement le contenu des fichiers liste.h et test_liste.cpp.wget http://ericbeaudry.ca/INF3105/lab5/lab5.zip unzip lab5.zip
Temps recommandé : 90 minutes. Après 90 minutes, considérez de passer à la tâche 3.
Supposez que vous avez une passe mensuelle, comme la carte OPUS. Vous payez un montant fixe par mois ou par semaine, et ce, peu importe le nombre de passages. Une fraude typique est de valider plusieurs fois la même passe afin de permettre à plusieurs personnes d'entrer.
Une façon simple de réduire ce type de fraude est d'interdire les multiples validations d'une même carte à l'intérieur d'un délai donné (ex. : 10 minutes).
Vous devez compléter le programme lab5.cpp pour détecter les tentatives de fraude. Le programme lit une liste de passages à valider. Chaque passage est une paire <Temps> <Numéro de passe>. Les temps est exprimé en secondes. Le programme doit garder en mémoire la liste des passages validés au cours des 10 dernières minutes (600 secondes).
1. Créer une liste vide liste_passages. 2. Tant que la lecture l'entrée standard n'est pas terminée : 3. | Lire un passage p. //Un passage est une paire d'entiers (temps, numéro_de_carte). 4. | Tant que liste_passages.premier().temps + 600 <= p.temps. 5. | | Enlever le premier élément de liste_passages. 6. | Si liste_passages contient un passage p2 tel que p.numéro=p2.numéro : 7. | | Afficher "Passage invalide : ", p2.temps, " " p2.numéro, "!". 8. | Sinon : 9. | | Ajouter p à la fin de liste_passages.
make ./lab5
Ensuite, tapez des entrées. Pour terminer, vous pouvez faire [Ctrl]+[D] (fin de fichier). Pour interrompre votre programme, vous pouvez faire [Ctrl]+[C].
Vous pouvez également rediriger un fichier dans l'entrée :
où test1.txt contient :./lab5 < test1.txt
0 1001 1 1002 1 1010 2 1020 50 1003 102 1030 253 1010 502 1004 602 1001
Cela devrait produire le résultat:
Passage invalide : 253 1010!
À noter que la passe #1001 peut être revalidée au temps 602, puisque c'est plus de 600 secondes plus tard que le temps 0. La passe #1010 pourra aussi être revalidée au temps 602, et ce, même si une tentative a été faite au temps 253.
Pour vérifier le bon fonctionnement de votre programme, quelques fichiers tests sont fournis. Vous pouvez comparer vos résultats manuellement ou avec le comparateur diff.
./lab5 < test1.txt > test1.monresultat.txt diff test1.monresultat.txt test1.result.txt
La complexité algorithmique de lab5 peut déprendre de plusieurs facteurs. Afin de déduire intuitivement des facteurs qui pourraient influencer le temps d'exécution, quelques un utilitaire de génération de tests est fourni (random_passages).
Pour compiler random_passages, il faut éditer le fichier Makefile et ajouter random_passages à la fin de la ligne all: . De plus, notez que random_passages.cpp a besoin d'être compilé avec un compilateur supportant la norme 2011 de C++. Le compilateur GCC version 4.7 supporte (expérimental) la norme 2011 en ajoutant l'option -std=c++11.
Syntaxe :
./random_passages nb_passages nb_cartes delai_moyen
où :
Exemple:
peut produire :./random_passages 15 4 10
Remarquez qu'il y a 4 numéros de cartes différents (10000 à 10003) et le temps moyen entre deux passages est d'environ 15 secondes. Évidemment, comme le programme random_passages produit des résultats aléatoires.2 10003 5 10002 13 10003 40 10002 43 10000 47 10000 60 10000 67 10002 77 10001 80 10003 135 10001 148 10002 158 10001 162 10002 165 10001
En ligne de commande, le symbole barre vertical (|) permet de connecter la sortie du programme random_passages à l'entrée du programme lab5 à l'aide d'un tuyau (pipe). Exemple:
peut produire le résultat suivant :./random_passages 15 4 10 | ./lab5
Lancez les tests suivants :Passage invalide : 13 10003! Passage invalide : 40 10002! Passage invalide : 47 10000! Passage invalide : 60 10000! Passage invalide : 67 10002! Passage invalide : 80 10003! Passage invalide : 135 10001! Passage invalide : 148 10002! Passage invalide : 158 10001! Passage invalide : 162 10002! Passage invalide : 165 10001!
./random_passages 10 10 1 | (time ./lab5) > /dev/null ./random_passages 10 10 1 | (time ./lab5) > /dev/null ./random_passages 100 10 1 | (time ./lab5) > /dev/null ./random_passages 1000 10 1 | (time ./lab5) > /dev/null ./random_passages 10000 10 1 | (time ./lab5) > /dev/null ./random_passages 100000 10 1 | (time ./lab5) > /dev/null ./random_passages 100000 10 1 | (time ./lab5) > /dev/null ./random_passages 10 1000 1 | (time ./lab5) > /dev/null ./random_passages 10 1000 1 | (time ./lab5) > /dev/null ./random_passages 100 1000 1 | (time ./lab5) > /dev/null ./random_passages 1000 1000 1 | (time ./lab5) > /dev/null ./random_passages 10000 1000 1 | (time ./lab5) > /dev/null ./random_passages 100000 1000 1 | (time ./lab5) > /dev/null ./random_passages 100000 1000 1 | (time ./lab5) > /dev/null ./random_passages 10 1000 0.1 | (time ./lab5) > /dev/null ./random_passages 10 1000 0.1 | (time ./lab5) > /dev/null ./random_passages 100 1000 0.1 | (time ./lab5) > /dev/null ./random_passages 1000 1000 0.1 | (time ./lab5) > /dev/null ./random_passages 10000 1000 0.1 | (time ./lab5) > /dev/null ./random_passages 100000 1000 0.1 | (time ./lab5) > /dev/null ./random_passages 100000 1000 0.1 | (time ./lab5) > /dev/null ./random_passages 10 10000 0.1 | (time ./lab5) > /dev/null ./random_passages 10 10000 0.1 | (time ./lab5) > /dev/null ./random_passages 100 10000 0.1 | (time ./lab5) > /dev/null ./random_passages 1000 10000 0.1 | (time ./lab5) > /dev/null ./random_passages 10000 10000 0.1 | (time ./lab5) > /dev/null ./random_passages 100000 10000 0.1 | (time ./lab5) > /dev/null ./random_passages 100000 10000 0.1 | (time ./lab5) > /dev/null
Tracez sur papier des graphiques pour tenter de déterminer comment les paramètres de random_passages influencent le temps d'exécution de lab5.
Enfin, analysez la complexité temporelle et spatiale de lab5 en fonction des paramètres nb_passages, nb_cartes et delai_moyen. Faites seulement l'analyse du cas moyen.