Skip to topic | Skip to bottom
Home
Linfo
Linfo.GLEnvtProg0708Projetr1.4 - 09 Mar 2008 - 10:13 - NicolasNobelistopic end

Start of topic | Skip to actions

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

  • ALERT! 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.

TIP test_bulles, test_insertion et test_quicksort sont utilisés dans les questions 3. et 4.
TIP 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.

  1. 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 ?
  2. 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.
  3. 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 ?
  4. 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).
  5. 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

  1. 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).
  2. É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

I Attachment sort Action Size Date Who Comment
FournitureProjet.tbz manage 89.7 K 02 Mar 2008 - 14:50 NicolasNobelis Fourniture pour le Projet

You are here: Linfo > GLEnvtProg0708 > GLEnvtProg0708Projet

to top

Copyright © 1999-2019 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding WIKIDeptinfo? Send feedback