Projet environnements de programmation
Licence 3 Informatique - 2007-2008
PhilippeCollet,
NicolasNobelis
URL de cette page :
http://deptinfo.unice.fr/twiki/bin/view/Linfo/GLEnvtProg0708Projet
URL de l'enseignement :
http://deptinfo.unice.fr/twiki/bin/view/Linfo/GLEnvtProg0708
Avant propos
Où ? Quand ?
Le projet doit être rendu par mail à
nobelis@polytech.unice.fr
avant
le jeudi 13 mars 2008, minuit.
Le mail doit avoir pour sujet
Projet GLEnvtProg - Nom du binôme
. Pour être sûr que j'ai bien reçu votre projet, vous pouvez m'envoyer le mail avec une demande d'accusé de réception (je répondrai à toutes ces demandes).
N'oubliez pas d'attacher votre projet au mail (!)
Comment ?
- Le projet est à faire en binôme.
- Le projet sera rendu dans une archive tgz ou tbz nommée projetnom1nom2.{tgz,tbz}.
- Les questions marquées ajoutez signifient que vous devez joindre le fichier précisé à cette archive.
- Les questions marquées rédigez signifient que vous devez écrire la réponse à cette question dans un fichier texte simple nommé reponses_nom1nom2.txt en précisant le numéro de la question concernée. Vous joindrez bien sûr ce fichier à votre archive de rendu.
- Vous pouvez ajouter vos commentaires ou remarques dans ce fichier.
-
Ne copiez pas : un logiciel de comparaison avancée sera utilisé sur tous vos fichiers de rendu. Toute similarité sera sanctionnée.
Fournitures
L'archive
FournitureProjet.tbz contient les fichiers donc vous allez avoir besoin pour ce projet :
-
tableau.h
, contient les prototypes de toutes les fonctions de manipulation de tableau.
-
tableau.c
, contient les implémentations de certaines fonctions de manipulation de tableau (i.e. toutes sauf les fonctions de tri et celles de piles).
-
tableau_stack.c
, contient les implémentations de certaines fonctions de manipulation de tableau (i.e. les fonctions de piles).
-
tri_bulles.c
, contient l'implémentation d'un tri à bulles.
-
tri_insertion.c
, contient l'implémentation d'un tri par insertion.
-
tri_quicksort.c
, contient un appel à l'implémentation d'un tri rapide ("quicksort') contenue dans la libc.
-
test_tableau.c
, programme de test des algorithmes de tri.
-
test_tableau_stack.c
, programme de test de toutes les fonctions de manipulation de tableau.
-
Makefile
, voir ci-dessous.
-
kprof
, déjà utilisé dans le TP4.
La cible
all du
Makefile
construit quatre binaires nommés
test_bulles
,
test_insertion
,
test_quicksort
(à partir de
test_tableau.c
) et
test_stack
(à partir de
test_tableau_stack.c
). Les trois premiers binaires ont deux paramètres obligatoires et un troisième optionnel:
- Le première paramètre est la longueur des tableaux à générer.
- Le second paramètre est le nombre de tableaux à générer
- Si le troisième paramètre est positionné à 0, les tableaux seront générés déjà triés.
L'algorithme de tri est déterminé par l'implémentation ayant été liée au binaire.
Exemples de cas d'utilisation :
-
test_bulles 500 4000
=> génère 4000 tableaux de taille 500 initialisés aléatoirement, et les tri au fur et à mesure à l'aide d'un tri à bulles.
-
test_insertion 15 1 0
=> génère un tableau de taille 15 déjà trié, et le tri à l'aide d'un tri par insertion. Comme il n'y a qu'un seul tableau de taille modeste, celui-ci est affiché à l'exécution.
Le binaire
test_stack
quant à lui génère aléatoirement un seul tableau et effectue diverses opérations issues de
tableau.h
, dont un tri déterminé par l'implémentation ayant été liée au binaire. Celui-ci n'a qu'un paramètre obligatoire et un second optionnel:
- Le première paramètre est la longueur du tableau à générer.
- Si le second paramètre est positionné à 0, le tableau sera généré déjà trié.
Exemple de cas d'utilisation :
-
test_stack 15 0
=> génère un tableau de taille 15 déjà trié, et effectue plusieurs opérations sur celui-ci.
test_bulles
,
test_insertion
et
test_quicksort
sont utilisés dans les questions 3. et 4.
test_stack
est utilisé dans les questions 5. et 6.
1. Fin du TP5
- Finissez le TP5.
- ajoutez à votre archive le fichier checkFile1.c de la question 5. du TP5.
2. Makefile
- Copiez le
Makefile
fourni dans un fichier Makefile.1.
- Améliorez Makefile.1 pour utiliser :
- les variables de make et autres variables (CFLAGS,...),
- au maximum les variables automatiques ($@, $^, $<, ...),
- les règles implicites.
- ajoutez à votre archive ce fichier Makefile.1.
3. Optimisation
Dans cette question, nous utilisons le terme de
données conséquentes pour des paramètres de test élevés
non triés : par exemple longueur de tableau = 500 et nombre de tableaux = 4000. Adaptez ces valeurs suivant la puissance de votre machine de test.
- Utilisez la commande
time
pour tester la vitesse des différents algorithmes de tri (test_bulles
, test_insertion
et test_quicksort
) avec des données conséquentes.
- rédigez en ajoutant ces temps à votre rapport. Qu'en déduisez-vous sur ces algorithmes et la qualité de leur implémentation ?
- Utilisez la commande
time
pour tester la vitesse des différents algorithmes avec des données conséquentes mais déjà triées (c'est-à-dire que le troisième paramètre vaut 0).
- rédigez en ajoutant ces temps à votre rapport. Analysez et identifiez (ou supposez dans le cas du quicksort) d'où proviennent ces différences.
- Créez trois binaires pour le tri à bulles test_bulles0, test_bulles2, et test_bulles3, optimisés avec les paramètres respectifs
-O0
, -O2
, -O3
. Mesurez la vitesse de chaque binaire avec time
et des données conséquentes. Observez également la taille des binaires produits.
- rédigez en ajoutant ces temps et ces tailles à votre rapport. Qu'en déduisez-vous sur ces optimisations ?
- Regardez
tri_quicksort.c
. Si on utilisait les mêmes optimisations, mais avec un binaire lié au tri quicksort, qu'obtiendrait-on comme résultats ?
- rédigez, en la justifiant, votre réponse (il ne vous est pas demandé de faire ces compilations ni ces mesures).
- Prenez à présent un binaire non optimisé effectuant le tri à bulles, i.e.
test_bulles
. Utilisez des données conséquentes et faites variez la longueur des tableaux à trier. Faites une demi-douzaine de mesures.
- rédigez en ajoutant ces temps à votre rapport. Qu'en déduisez-vous ? Arrivez-vous à retrouver la complexité de l'algorithme ?
4. Profiling
- Obtenez, à l'aide de
gprof
, deux profiles pour test_insertion
et test_bulles
(sur des données conséquentes). Analysez ces profiles à la main ou avec kprof
.
- rédigez en présentant (et justifiant) les fonctions utilisant le plus de ressource. Quelles sont les fonctions qu'il faudrait optimiser ? (aidez-vous du code source de ces fonctions).
- Étudiez le taux des temps d'éxecution des deux algorithmes de tri (en le calculant à la main ou en utilisant l'option "comparer" de
kprof
). Générez deux nouveaux profiles en changeant adéquatement la taille des données triées, puis observez l'évolution (ou la non évolution) de ce taux.
- rédigez en ajoutant ces taux (et vos paramètres de test) à votre rapport. Qu'en déduisez-vous ?
5. Bibliothèque...et encore un peu de Makefile !
- Construisez une bibliothèque dynamique libtableau.so à partir de
tableau.o
et de tableau_stack.o
comme vu en TP.
- Construisez un binaire test_stack_dyn en un appel à
gcc
qui :
- compile
test_tableau_stack.c
,
- se relie au fichier
tri_quicksort.o
,
- se relie dynamiquement à la bibliothèque libtableau.so.
- Exécutez le binaire produit.
- Copiez Makefile.1 dans Makefile.2. Modifiez Makefile.2 en y ajoutant les trois commandes précédentes.
- ajoutez à votre archive ce fichier Makefile.2.
6. Tests
- Observez les spécifications contenues dans tableau.h pour les fonctions implémentées dans
tableau_stack.o
.
- Identifiez les cas critiques et rédigez un plan de test. Il ne vous est pas demandé d'implémenter ce plan de test.
- rédigez en présentant les cas critiques et votre plan de test.
- (Super bonus - optionnel) Finalement, écrivez dans
test_tableau_stack.c
le plan de test de la question précédente en utilisant l'infrastructure check.
- (Super bonus - optionnel) Copiez Makefile.2 dans Makefile.3. Modifiez le Makefile.3 pour pouvoir compiler et exécuter un binaire test_stack_dyn_check (vous aurez donc une ligne de compilation contenant
-ltableau
et -lcheck
).
- (Super bonus - optionnel) ajoutez à votre archive le fichier Makefile.3 et le fichier test_tableau_stack.c modifié.
--
NicolasNobelis - 09 Mar 2008
to top