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.
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. Soit p(n) le nombre de premiers inférieurs à n. Comparer les graphes des fonctions p(n) et f(n) = 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 moins de 5 minutes. Utiliser le programme gnuplot pour  faire le graphe de la fonction x -> p(x). Vérifier  expérimentalement la  loi de repartition des nombres premiers devinée par Euler et prouvée par Gauss :

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