******************************************
          *        PREUVES ET ANALYSES DES         *
          *               ALGORITHMES              *
          *       EXAMEN DE TRAVAUX - PRATIQUES    *
          *   19 Decembre 2012  de 09:00 -- 11:30  *
          ******************************************

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

Vous pouvez utiliser les informations presentes sur votre compte, la
documentation en ligne de commande, aucun autre document n'est autorise.

Les explications, modifications de codes etc... seront renseignees dans
ce fichier, immediatement apres la question.

   /\    Pour validez votre travail a la fin de l'examen :
  /!!\
  ----  /home/partage/validexam I51

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

L'objectif de l'exercice est de programmer une commande mysort qui
correspondant a la description suivante :
 
MYSORT(1exam)       User Commands                         

NAME
       mysort - trie les lignes de fichiers textes

SYNOPSIS
       mysort [ OPTION ]... [FILE] 

DESCRIPTION
       La commande mysort concatene les lignes des fichiers 
       les trie, et les envoie sur la sortie standard.

   options:

       -a comparaison alphabetique
       -n comparaison numerique
       -s silence, les lignes ne sont pas affichees
       -t temps d'execution cpu
       -u unique

AUTEUR
      @auteur

       

=====================
0. fichiers
=====================

Le repertoire de travail contient

   - makefile
   - table.h, table.c
   - comp.h,  comp.c   
   - main.c

[ a ] Parcourir les fichiers, preciser le role des
      fichiers tables et comps. 

[ b ] Decrire le role des varibles nbmemb et table.

[ b ] Modifier le makefile pour construire la
      cible mysort

<cat makefile>

[ c ] Dans l'etat que fait la commande  mysort ?


=====================
1. Demonstration
=====================

[ a ] Completer le fichier main.c que la commande
      trie des fichiers dans l'ordre alphabetique.

<modification sur main.c>

[ b ] Faire une demonstration pour illustrer le
      fonctionnement de mysort.

=====================
1. Fichier test
=====================

Pour chaque entier n, un fichier test est un fichier texte
de n lignes de longueurs supérieure à 2n. Les préfixes de
longueurs 2n de ces lignes sont identiques, le suffixe est
un nombre aléatoire de 16 bits au plus. 

Exeemple pour n=8 :

xxxxxxxxxxxxxxxxxx30542
xxxxxxxxxxxxxxxxxx17005
xxxxxxxxxxxxxxxxxx16199
xxxxxxxxxxxxxxxxxx28875
xxxxxxxxxxxxxxxxxx16788
xxxxxxxxxxxxxxxxxx23692
xxxxxxxxxxxxxxxxxx244
xxxxxxxxxxxxxxxxxx9412

[ a ] Consulter le manuel de bash pour determiner la variable
      globale de bash contenant un nombre aleatoire. Commenter
      le resultat de la commande :
      echo $RANDOM

[ b ] Ecrire un script test.sh pour construire un fichier
      test de n lignes.

<cat test.sh>

=====================
2. Chronometrage
=====================

[ a ] Modifier main.c pour chronometrer l'execution de 
      qsort. Vous utiliserez la fonction clock().

[ b ] Mettre en place les options -t  et -s       

[ c ] Preciser les modifications faites sur main.c :

<modifications sur main.c>

=====================
3. Experience    
=====================

Il s'agit de mettre en evidence la forme mathematique
du temps de tri sur les fichiers tests.

[ a ] Ecrire un script pour construire un fichier data.txt
      chaque ligne comprend deux valeurs : n et le temps de
      tri du fichier test a n lignes.

[ b ] Utiliser gnuplot pour construire une image test.png 
      representation graphique du temps de calcul des fichiers 
      tests.

<commande gnuplot>

[ c ] Modifier le makefile

<modification makefile>

[ d ] Quelle est la forme du temps de calcul ?

[ e ] Interpreter ce resultat numerique. 

=====================
4. option : numerique
=====================

Il s'agit de mettre en place le tri numerique. Le nombre
associe a une chaine est 0 ou bien un entier.

[ a ] Quelle option de la commande sort permet de faire
      un tri suivant les valeurs numeriques ?

[ b ] Ecrire une fonction cmpnum( char *x, char* y) qui
      compare les chaines x et y suivant leurs valeurs
      numeriques. 

[ c ] mettre en place l'option -n


=====================
5. option : unique
=====================

[ a ] Ecrire une fonction unique( void ) qui envoie
      les lignes de la table sans repetition, comme
      par exemple la commande unix uniq.

[ b ] mettre en place l'option -u