Laboratoire 5 : Les Listes

Lecture préalable

Section 7 (Les Listes) des notes de cours.

Objectifs

Implémenter une liste doublement chaînée.
Appliquer une liste doublement chaînée pour résoudre un problème simple.
Optionnel : analyser la complexité temporelle d'un programme dont l'entrée est générée aléatoirement.

Tâches

Fichiers du lab5

Faites les commandes suivantes :

wget http://cria2.uqam.ca/INF3105/lab5/lab5.zip
unzip lab5.zip

Regardez brièvement le contenu des fichiers liste.h et test_liste.cpp.

Implémentation de la classe générique `Liste<T>`

L'implémentation de liste.h suit celle présentée à la section 7.3 des notes de cours.
Repérez les endroits commentés par « // À compléter. » dans liste.h.
Complétez le code.
Afin de bien comprendre chaque opération, dessinez sur papier une liste avant et après l'opération.
L'objectif est de faire réussir tous les tests dans test_liste.cpp.
Il est suggéré de procéder dans l'ordre des tests dans test_liste.cpp.
Lorsqu'une fonction contient un commentaire « // À compléter. », ne supposez pas que le return est bon. Plusieurs return incorrects ont été insérés uniquement pour éviter des messages d'avertissement ou d'erreur à la compilation.

Temps recommandé : 90 minutes. Après 90 minutes, considérez de passer à la tâche 3.

Application de la liste à la détection de fraude

Si vous n'avez pas terminé la tâche #2, vous pouvez récupérer une solution de liste.h.

Fraude typique dans le transport en commun

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).

Programme de validation

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 sont exprimés en secondes. Le programme doit garder en mémoire la liste des passages validés au cours des 10 dernières minutes (600 secondes).

Algorithme

1. Créer une liste vide liste_passages.
2. Tant que la lecture depuis 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.

Compilation et exécution

Pour tester, faites :

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 :

./lab5 < test1.txt

où test1.txt (fourni avec le code de départ) contient :

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

Exercice complémentaire au Lab5

Analyse du cas moyen de l'algorithme du programme lab5

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, un utilitaire de génération de tests est fourni (random_passages).

Syntaxe :

./random_passages nb_passages nb_cartes delai_moyen

où :

nb_passages est le nombre de passages aléatoire à générer;
nb_cartes est le nombre de numéros de carte différents;
delai_moyen est le délai moyen entre deux passages (suit une loi exponentielle).

Exemple:

./random_passages 15 4 10

peut produire :

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.

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:

./random_passages 15 4 10 | ./lab5

peut produire le résultat suivant :

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!

Lancez les tests suivants :

./random_passages 1000 10 1 | (time ./lab5) > /dev/null
./random_passages 5000 10 1 | (time ./lab5) > /dev/null
./random_passages 10000 10 1 | (time ./lab5) > /dev/null
./random_passages 50000 10 1 | (time ./lab5) > /dev/null
./random_passages 100000 10 1 | (time ./lab5) > /dev/null
./random_passages 500000 10 1 | (time ./lab5) > /dev/null
./random_passages 1000000 10 1 | (time ./lab5) > /dev/null
./random_passages 5000000 10 1 | (time ./lab5) > /dev/null
./random_passages 10000000 10 1 | (time ./lab5) > /dev/null

./random_passages 1000 1000 1 | (time ./lab5) > /dev/null
./random_passages 5000 1000 1 | (time ./lab5) > /dev/null
./random_passages 10000 1000 1 | (time ./lab5) > /dev/null
./random_passages 50000 1000 1 | (time ./lab5) > /dev/null
./random_passages 100000 1000 1 | (time ./lab5) > /dev/null
./random_passages 500000 1000 1 | (time ./lab5) > /dev/null
./random_passages 1000000 1000 1 | (time ./lab5) > /dev/null
./random_passages 5000000 1000 1 | (time ./lab5) > /dev/null
./random_passages 10000000 1000 1 | (time ./lab5) > /dev/null

./random_passages 1000 1000 0.1 | (time ./lab5) > /dev/null
./random_passages 5000 1000 0.1 | (time ./lab5) > /dev/null
./random_passages 10000 1000 0.1 | (time ./lab5) > /dev/null
./random_passages 50000 1000 0.1 | (time ./lab5) > /dev/null
./random_passages 100000 1000 0.1 | (time ./lab5) > /dev/null
./random_passages 500000 1000 0.1 | (time ./lab5) > /dev/null
./random_passages 1000000 1000 0.1 | (time ./lab5) > /dev/null
./random_passages 5000000 1000 0.1 | (time ./lab5) > /dev/null
./random_passages 10000000 1000 0.1 | (time ./lab5) > /dev/null

./random_passages 1000 10000 0.1 | (time ./lab5) > /dev/null
./random_passages 5000 10000 0.1 | (time ./lab5) > /dev/null
./random_passages 10000 10000 0.1 | (time ./lab5) > /dev/null
./random_passages 50000 10000 0.1 | (time ./lab5) > /dev/null
./random_passages 100000 10000 0.1 | (time ./lab5) > /dev/null
./random_passages 500000 10000 0.1 | (time ./lab5) > /dev/null
./random_passages 1000000 10000 0.1 | (time ./lab5) > /dev/null
./random_passages 5000000 10000 0.1 | (time ./lab5) > /dev/null
./random_passages 10000000 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.