next up previous
suivant: À propos de ce

Université Bordeaux 1 Licence Informatique 2005/2006


Initiation à l'algorithmique
 
TD 2



Exercice 2.1
On considère la fonction suivante :

fonction test (ref n:entier;val i:entier):vide;
debut
   tant que i > 0 faire
     n = n + i;
     i = i-1;
   fintantque
fin
Que valent $n$ et $i$ après l'appel de la fonction test dans les cas suivants :
  1. var n,i:entier 
    test(3,5)
    
  2. var n,i:entier 
    n = 4
    test(n,5)
    
  3. var n,i:entier 
    n = 4 
    i = 5 
    test(n,i);
    


Exercice 2.2
Ecrire les fonctions puissance, Modulo, QuotientEntier, PGCD à partir des algorithmes décrit dans le TD1.


Exercice 2.3

Multiplication alexandrine
(ou Multiplication à la russe)
Pour multiplier deux entiers X et Y, on détermine la suite :
Le produit XY est égal à la somme des $x_i$ pour lesquels $y_i$ est impair.
a- Appliquer l'algorithme au produit $7 \times 9$.
b- Justifier l'algorithme; expliquer son intérêt dans un calculateur.
c- Ecrire une fonction itérative Produit appliquant cet algorithme. Quel est le paramètre pertinent pour évaluer le temps d'exécution ?
e- Déduire des questions précédentes un algorithme permettant d'obtenir une fonction retournant $x^y$.


Exercice 2.4
Quelle est la plus petite valeur strictement positive de $n$ pour laquelle un algorithme dont le temps d'exécution est $100n^2$ s'exécute plus vite qu'un algorithme pour lequel le temps d'exécution est $2^n$ sur la même machine ?
Soit $n_1(t)$ (resp. $n_2(t)$) la valeur maximum de $n$ pour laquelle on peut exécuter un certain algorithme réalisant $100n^2$ (resp. $2^n$) opérations en un temps $t$. De combien augmente l'image de la fonction $n_1$ (resp. $n_2$) lorsque l'on passe de $t$ à $2t$ ?


Exercice 2.5
Écrire une fonction qui teste si un entier est premier ou non.


Exercice 2.6
Écrire une fonction utilisant les précédentes permettant d'afficher le énième nombre premier.



next up previous
suivant: À propos de ce
Maylis Delest 2005-04-06