Feuille de travaux pratiques numéro 1 cours d'algorithmique de licence

L'art de la mise en oeuvre

Objectifs :  Initiation à la detection et la correction des erreurs avec le compilateur gcc et le debogueur gdb.  Analyse des temps de calcul par le profiler gprof.  L'exercice est basé sur une méthode connue de tous pour construire la liste des nombres premiers :  le crible d'Eratostène.

Culture  scientifique :  Erasostène de Cyrène savant  de l'époque Euclidienne est célèbre pour son calcul de la circonférence terrestre.  Je vous laisse le soin de vous documenter par vous meme.  L'étude de la fonction de répartition des nombres premiers  n -> p(n) = {le nombre de premiers inférieurs à n } est une question centrale de l'arithmétique.  Euler utilise la formule du crible pour  calculer les valeurs de p(n), de ses calculs, il devine  une  formule d'une élégante simplicité :

 p(x) ~ x / ln(x).

    Il  en fit une démonstration fausse mais trés instructive : les mathématiques du XVIII n'étaient pas assez élaborées pour obtenir ce  résultat qui sera prouvé un siècle plus tard par  Gauss.  Le terme d'erreur relatif à cette approximation conduit à  Riemann à sa fameuse  hypothèse. Dans les années 20,  Turing  essaye de transformer  la machine de  Kelvin ( initialement concue pour mesurer l'amplitude des marées) pour calculer  et deviner une formule du terme d'erreur,  il échoue mais c'est le point de départ de  l'expérimentation numérique.

Temps : 1 séance de 3 heures.
  1. Parcourir les pages du manuel à propos des commandes gcc, gdb et gprof pour n'en retenir que l'essentiel.
  2. Préparer un mémo. Expliquez les liens entre le compilateur gcc, le debogueur gdb et le profileur gprof.
  3. Editer le programme crible.c.  Faire une première lecture. Que semble faire ce programme ?
  4. La compilation  simple sans option de crible.c signale  quelques  erreurs, corrigez les.
  5. Utiliser l'option -o pour faire un exécutable crible.x. Lancez le. Que se passe-il ?
  6. Compilez  de nouveau avec l'option -Wall.Corriger toutes les <<erreurs>> signalées par gcc.
  7. Le programme ne marche toujours pas :-( . Quelle est la nature de l'erreur ?
  8. Compilez avec l'option de debogage -g.
  9. Utiliser  le debogueur  gdb pour  trouver la ligne erronée.
  10. Réparer la source.
  11. Exécutez le programme en faisant varier le paramètre d'entrée  de 1000, 10000, etc...  Prendre garde au swap !
  12. Deviner une expression du temps de calcul de crible.x
  13. Transformez votre intuition en une démonstration. Puis déterminer le facteur caché de cette implantation de la méthode du crible d'Eratostene.
  14. Comparer les valeurs des fonctions p(n)et n/log(n). Commentaire ?
  15. Utilisez l'option de compilation -pg puis le profileur gprof pour déterminer le temps consommé par la procédure bif(t, n).
  16. Quelle est l'influence des options de compilation -Ox ?
Challenge.
  •     Ecrire un nouveau programme,  pour calculer p(n) pour un entier n aussi grand que possible en utilisant un  tableau de bits  plutot qu'un tableau de caractères.
  • Quelle valeur de n traite votre programme en moins de 1 minute ?

    •  
  • Utiliser le programme gnuplot pour  faire le graphe de la fonction n -> p(n).