phil@ou812.univ-tln.fr **************************************************************** * EXAMEN DE TRAVAUX PRATIQUES * * MODULE I41 * * MERCREDI 7 JUIN 2006 * **************************************************************** PREAMBULE: Vous disposez de 2 heures pour traiter un sujet compose de quatre exercices notes sur 5 points. Vous repondrez aux questions direct- ement dans ce fichier en inserant vos solutions immediatement apres chaque question. N'oubliez pas de sauvegardez regulierement votre fichier, une procedure automatique collectera vos reponses a la fin de l'examen. * * * NOM : Phil =================================================================== * EXERCICE 1 : suite recurrente, ( 5 points ) =================================================================== Il s'agit d'ecrire un programme qui lit un entier n sur la ligne de commande pour calculer le n-ieme terme de la suite recurrente d'ordre trois definie par les relations : U(0) = 0, U(1) = 1, U(2) = 4 et plus generalement, pour n superieur a 2 : U(n) = U(n-1) + U(n-2) + U(n-3) [ a ] Les elements de la suite seront representes par des entiers signes sur 32 bits. Quelle est la valeur de U(32) = [ b ] Preciser le domaine de validite de l'implantation. 0 <= n < ... [ c ] Inserer le listing du programme : =================================================================== * EXERCICE 2 : Algorithme Euclidien, ( 5 points ) =================================================================== Ecrire un programme qui prend deux entiers de 32 bits sur la ligne de commande pour calculer et afficher leur pgcd. Le programme deman- de doit obligatoirement etre base sur la version iterative de l'algo- rithme d'Euclide. [ a ] Completer : pgcd( 230562 ,300768 ) = [ b ] Inserer le listing du programme : =================================================================== * EXERCICE 3 : temps de calcul, ( 5 points ) =================================================================== Le repertoire exam-tp-i41 contient trois executables : a.exe, b.exe, et c.exe. Chacuns de ces programmes prend en entree un entier n, pour calculer une valeur qui importe peu. On rappelle qu'il est possible de mesurer le temps d'execution d'une commande avec la commande time, par exemple, pour mesurer le temps de calcul de la commande sleep 5 (temps d'execution 5sec), il suffit de lancer : [phil@ou812.univ-tln.fr exam-tp-i41]$ time sleep 5 [phil@ou812.univ-tln.fr exam-tp-i41]$ 0.000u 0.002s 0:05.01 0.0% +0k 0+0io 0pf+0w Le temps total de l'execution est indique en secondes sur la trois- ieme colonne, ici c'est 0:5.01. [ a ] Faire quelques mesures de temps d'execution du programme a.exe, (a la seconde pres) pour determiner la forme du temps de calcul en fonction de n. Les reponses possibles sont : lineaire, logarithmique, quadratique, cubique, et exponentielle. Indiquer les mesures : ------------------------------------------------------------ | n | ------------------------------------------------------------ | T(n) | ------------------------------------------------------------ Donner la forme du temps de calcul : Citer un algorithme du cours de preuves et analyses des algorithmes dont une implantation vue en TP possede un temps de calcul analogue. algorithme : [ b ] idem pour b.exe ------------------------------------------------------------ | n | ------------------------------------------------------------ | T(n) | ------------------------------------------------------------ forme du temps de calcul : algorithme : [ c ] idem pour c.exe. ------------------------------------------------------------ | n | ------------------------------------------------------------ | T(n) | ------------------------------------------------------------ forme du temps de calcul : algorithme : ============================================================= * EXERCICE 4 : Recherche de Motifs ( 5 points ) ============================================================= Le programme motif.c prend en entree deux chaines de caracteres en arguments sur la ligne de commande correspondants a un motif et un nom de fichier, pour faire une recherche de motifs. Il se termine en indiquant le nombre d'occurences du motif dans le fichier. Par exemple : [phil@ou812.univ-tln.fr exam-tp-i41]$ gcc -Wall motif.c -o motif.exe [phil@ou812.univ-tln.fr exam-tp-i41]$ ./motif.exe int motif.c [phil@ou812.univ-tln.fr exam-tp-i41]$ Nombre d'occurences de int : 20 [ a ] Faire une copie de la source motif.c dans un fichier ligne.c, changer les droits du fichier ligne.c pour pouvoir le modifier [phil@ou812.univ-tln.fr exam-tp-i41]$ chmod 777 ligne.c puis modifier le programme ligne.c de sorte a afficher le numero des lignes contenant le motif cherche. Un meme numero de ligne pourra etre afficher plusieurs fois quand le motif apparaitra plusieurs fois sur une meme ligne. Le resultat attendu doit prendre la forme : [phil@ou812.univ-tln.fr exam-tp-i41]$ gcc -Wall ligne.c -o ligne.exe [phil@ou812.univ-tln.fr exam-tp-i41]$ ./ligne.exe taratata motif.c [phil@ou812.univ-tln.fr exam-tp-i41]$ ligne :37 [phil@ou812.univ-tln.fr exam-tp-i41]$ ligne :46 [phil@ou812.univ-tln.fr exam-tp-i41]$ ligne :61 [phil@ou812.univ-tln.fr exam-tp-i41]$ Nombre d'occurences de taratata : 3 [ b ] Inserer le resultat de la commande : [phil@ou812.univ-tln.fr exam-tp-i41]$ diff motif.c ligne.c [ c ] Ecrire une nouvelle version strict.c de motif.c (changer les droits du fichier strict.c) qui compte les motifs dans un fichier sans chevauchements. Le resultat attendu doit prendre la forme : [phil@ou812.univ-tln.fr exam-tp-i41]$ gcc -Wall motif.c -o motif.exe [phil@ou812.univ-tln.fr exam-tp-i41]$ ./motif.exe ata motif.c [phil@ou812.univ-tln.fr exam-tp-i41]$ Nombre d'occurences de ata : 6 La nouvelle version doit retourner 3. [phil@ou812.univ-tln.fr exam-tp-i41]$ gcc -Wall strict.c -o strict.exe [phil@ou812.univ-tln.fr exam-tp-i41]$ ./strict.exe ata motif.c [phil@ou812.univ-tln.fr exam-tp-i41]$ Nombre d'occurences de ata : 3 [ b ] Inserer le resultat de la commande : [phil@ou812.univ-tln.fr exam-tp-i41]$ diff motif.c strict.c