******************************************
          *   PREUVES ET ANALYSES DES ALGORITHMES  *
          *       EXAMEN DE TRAVAUX - PRATIQUES    *
          *    16 Decembre 2013  de 13:00 -- 16:00 *
          ******************************************

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Vous repondrez aux questions posees directement dans ce fichier en  
precisant sommairement les commandes et leurs options qui vous ont permis 
d'aboutir a vos reponses. 

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


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

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

  
======================
1. Temps de calcul  
======================

    Il s'agit de déterminer le temps de calcul de la
    commande ./prog.exe sachant que celle-ci prend un
    entier n en argument, et que le temps de calcul 
    est de la forme :

             T(n) = A n^k + B n^l

    avec 0 < k < l < 6.

[a] Donner les valeurs de B et l.
   
   [ méthode ]
 
[b] Donner les valeurs de A et k. 
   
   [ méthode ]

[c] Préciser la valeur de A/B

   A/B = 

======================
2. Tri de nombres 
======================

[a] Ecrire une fonction int comp( char *x, char *y ) pour comparer
    deux chaines numeriques décimales. Elle renvoie : -1, 0, ou +1 
    suivant que le nombre representé par x est < = ou > à celui 
    represénter par y.

    [ code ]
 
[b] Coder une commande comp.exe pour trier toutes les chaines 
    numériques d'un fichier. Un jeu d'options permettra de passer 
    le nom du fichier cible, de controler la sortie pour lister 
    au choix des éléments minimaux ou maximaux.

    OPTIONS:
      -n nombre : nombre de ligne a afficher
      -p        : affiche les éléments minimaux
      -g        : affiche les éléments maximaux

   Par exemple, ./comp.exe -p -n 3 z.dat affichera les 3 plus
   petits nombres du fichier z.dat

   NB : Un fichier a trier peut contenir plusieurs chaines 
        numeriques sur une meme ligne.

   Le code source sera nommé comp.c. 

   Decrire sommairement les etapes pour obtenir le code.

   [ méthode ]

[c] Utiliser le shell pour compter les lignes, les chaines
    numeriques et le nombre de caracteres du fichier z.dat/
 
   [ shell ]

[d] Donner le resultat des commandes :
      ./comp.exe -p -n 3 z.dat
      ./comp.exe -g -n 3 z.dat

[e] Utiliser le shell pour tester vos resultats :

   [ shell ]

==========================
3. Nombre de Fermat   
==========================

Le code fermat.c permet d'obtenir une commande qui lit un
entier n puis verifie si le n-ieme nombre de Fermat est
premier.
 
[a] Ecrire un makefile pour compiler une commande fermat.exe
    a partir des sources fermat.c, module.h, module.c
   
    [ cible ]

[b] Commenter un exemple d'exécution.

    [ commentaire ]

[c] Estimer le temps de calcul T(N) en fonction de N 
    la taille de F_n. Faire une representation graphique
    fermat.png 

    [ formule  pour T(N) ]
    [ script gnuplot     ] 

[d] Estimer le temps de calcul de F_2@code.

[e] Quelle valeur de n pourrait etre testée en moins de 
    1@code jour ?
    
    [ methode ] 
 
==========================
4. Nombre de Mersenne (30)
==========================

Un nombre de Mersenne est un nombre de la forme 
              
            M(p) = 2^p - 1,

où p est premier impair.

[a] Ecrire une fonction naive int premier( int x ) qui
    renvoie 1 si x est premier, 0 sinon.

    [ code C ]
   
[b] Implanter les fonctions :
       - dec( nombre x )
         // décrémente l'entier x    :  x := x - 1
       - expmod( nombre y, nombre x )
         // exponentiation modulaire :  y := y^x  [ module ]
    
   [ code C ]

[c] Ecrire une commande mers.exe qui prend en entrée un
    entier n, détermine le plus petit premier p >=n puis
    applique le test de Fermat a M_p.

   [ source mers.c ]

[d] quels sont les nombres :
	- p est premier
	- 100 < p < 200
	- M(p) semble etre premier.

   [ remarque ]
   [ valeur   ]

---------------------------------------------------------------
@auteur@@host.@code
---------------------------------------------------------------