****************************************** * 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. *** Une seule bonne reponse. [ méthode ] Une mesure de temps de calcul pour une valeur x de n et son double revele le plus grand exposant. D'ou lon tire B et l. Par exemple : x=128 tx=$( /usr/bin/time --format="%U" ./ab.exe $x 2>&1 ) let x*=2 ty=$( /usr/bin/time --format="%U" ./ab.exe $x 2>&1 ) echo "$ty/$tx" | bc -l 8.08333333333333333333 # ce qui montre que, l = 3, et B vaut : echo "$ty/$x^3" | bc -l .00000011563301086425 [b] Donner les valeurs de A et k. *** une demie bonne reponse [ méthode ] L'operation est delicate. Une facon d'aboutir consiste a effectuer deux mesures de temps de calcul puis de resoudre les systemes : t(x) = A x^k + B x^l t(y) = A y^k + B y^l avec les valeurs de k = 1, 2, ... et quelques instances x, y. La stabilite des solutions permet de detecter k. On utilise un script bc pour faire les calculs : =========================================================== #!/bin/bash k=$1 l=$2 x=2 ; c=0 ; tx=1 while [ 1 ] ; do let y=(3*x)/2 ty=$( /usr/bin/time --format="%U" ./ab.exe $y 2>&1 ) ## (A,B) solution du syteme : ## tx = A x^k + B x^l ## ty = A y^k + B y^l bc -l << CALC x = $x y = $y tx = $tx ty = $ty k = $k l = $l d = x^k * y^l - x^l * y^k; a = tx * y^l - x^l * ty; b = x^k * ty - tx * y^k; print "\nn=", y, " A=", a/d, " B=", b/d print "\nB/A=", b/a CALC x=$y tx=$ty done ============================================================== [c] Préciser la valeur de A/B *** pas de bonne reponse Au final, suivants les machines, il y avait trois solutions possibles : B/A = 0.6 l=3 k=2 = 0.2 l=4 k=3 = 0.33 l=4 k=2 Cependant la precision des mesures de temps de calcul avec /usr/bin/time ne permet pas de detecter le terme secondaire. *** question comptee juste pour tout le monde ! ====================== 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. *** quelques bonnes solutions *** beaucoup de reponses hors sujet ==================================================================== On suppose que x et represente des nombres en base 10 de facon standard i.e. sans chiffre inutile. Le mot le plus court est le plus petit, en cas d'egalite il faut comparer les chiffres. ==================================================================== int comp(char *x, char *y) { int i = strlen(x); int j = strlen(y); if (i < j) return +1; if (j < i) return -1; for (i = 0; i < j && x[i] == y[i]; i++); if (i == j) return 0; if (x[i] < y[i]) return +1; return -1; } =================================================================== [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 ] *** quelques reponses satisfaisantes *** remarque : il fallait faire attention a la taille des tampons ! *** strtok : jamais utilisee Il s'agit d'adapter le code du TP numero 1. Une gestion des options. La lecture ligne par ligne doit etre transformee en une lecture mot par mot [c] Utiliser le shell pour compter les lignes, les chaines numeriques et le nombre de caracteres du fichier z.dat/ *** resultats moyens $ wc -l z.dat 8091 z.dat $ wc -m z.dat 1930088 z.dat $ grep -Eo '[0-9]+' z.dat | wc -w 65536 [d] Donner le resultat des commandes : ./comp.exe -p -n 3 z.dat ./comp.exe -g -n 3 z.dat *** une seule reponse ./comp.exe -g -n3 z.dat 202790766912724697861012502954 193996444315973224042103318776 187533592819872310111789366143 ./comp.exe -p -n3 z.dat 1 29470256752159536835005211 98290699642999170137806862 [e] Utiliser le shell pour tester vos resultats : *** une seule reponse gcc -Wall -g comp.c -o comp.exe grep -Eo '[0-9]+' z.dat | sort -n | head -3 1 29470256752159536835005211 98290699642999170137806862 grep -Eo '[0-9]+' z.dat | sort -nr | head -3 202790766912724697861012502954 193996444315973224042103318776 187533592819872310111789366143 ========================== 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 *** satisfaisant ============================================================ fermat.exe : modular.o fermat.c gcc -Wall -g modular.o fermat.c -o fermat.exe modular.o : modular.h modular.c gcc -Wall -g -c modular.c =========================================================== [b] Commenter un exemple d'exécution. *** beaucoup n'ont pas su utiliser les options de la commande []$ ./fermat.exe -n5 Test de Fermat de F_5 taille=34 module: 2^32 + 2^0 . pass=1 certainement composé ! L'execution confirme que le 5ieme nombre de Fermat est compose, resultat obtenu par Euler au 18ieme. [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) ] *** une seule reponse acceptable D'apres le cours, T(N) est cubique. On collecte quelques temps de calcul : ======================================================== >fermat.dat for n in {1..10}; do t=$( echo "2^$n" | bc ) ; /usr/bin/time -a --format="$t %U" -o fermat.dat ./fermat.exe -n$n ; done ======================================================== $ cat fermat.dat 2 0.00 4 0.00 8 0.00 16 0.00 32 0.00 64 0.00 128 0.04 256 0.37 512 2.99 1024 23.77 Le script gnuplot *** une seule image ======================================================== set output 'fermat.png' set term png plot 'fermat.dat' w l,2*x*x*x/1E08 ======================================================== montre : T(N) = 2/1E08 N^3 sec [d] Estimer le temps de calcul de F_20 *** pas de bonne reponse T( 2^20 ) = 2/1E08 2^60 = approx = 2^37 sec !!! [e] Quelle valeur de n pourrait etre testée en moins de 10 jour ? *** une reponse acceptee On utilise bc s=24*60*60*10 t= e( l( s / 2 * 10^8) /3 ) n= l(t)/l(2) n 15.09869884864148479044 ========================== 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. *** beaucoup de fonctions fantaisistes pour une 3ieme annee de licence des sciences de l'ingenieur... Par exemple, vu en cours : ======================================================== int premier( int n ) { int p = 3; if ( 0 == n & 1 ) return 0; while ( p*p <= n ) { if ( 0 == n % p ) return 0; p+=2; } return 1; } ======================================================== [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 Les deux algorithmes ont ete vus en cours et TD. *** quelques bonnes reponses ======================================================= void dec(nombre x) { int i = 0; while (x[i] == 0) { x[i] = 1; i++; } x[i] = 0; } void expmod(nombre x, nombre n) { int i; nombre r = alloc(1); for (i = 0; i < taille; i++) { if (n[i] == 1) mult(r, x); mult(x, x); } for (i = 0; i < taille; i++) x[i] = r[i]; } ======================================================= [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. *** pas de bonne reponse ======================================================= int test(void) { int cpt = 0; nombre x = NULL, y; printf("\n"); while (cpt++ < 50) { if (x) free(x); x = aleas(); y = modulo(); dec(y); expmod(x, y); free(y); if (!unit(x)) break; } free(x); return cpt; } ======================================================= [d] quels sont les nombres : - p est premier - 100 < p < 200 - M(p) semble etre premier. *** pas de bonne reponse [ valeur ] 107, 127 [ remarque ] la commande factor confirme ces valeurs ! factor $( echo "2^107-1" | bc ) 162259276829213363391578010288127: 162259276829213363391578010288127 factor $( echo "2^127-1" | bc ) 170141183460469231731687303715884105727: 170141183460469231731687303715884105727 --------------------------------------------------------------- pl@microbe.rts.fr ---------------------------------------------------------------