Licence L3 Mathématiques et Applications (MAP) Université Paris–Sud Maths312: Algorithmique et programmation en C Centre d’Orsay Année 2009 − 2010

Partiels Mardi 28 Octobre 2009 - Durée : 2 heures Elément de correction.

Exercice - 1 Langage C

Q-1 : Exemple sur l’effet de codage des types de base en C On considère le programme suivant qui compile bien.

1 #include <s t d i o .h>
2 i n t main( i n t argc , char ∗∗ argv )
3 {
4 i n t m = 1;
5  p r i n t f( ”% d\n”,m) ;
6  while (m>0)
7  {
8  m++;
9  }
10  p r i n t f( ”% d\n”,m) ;
11  m−−;
12  p r i n t f( ”% d\n”,m) ;
13  return 0;
14 }

Q-1-1 : Ce programme se termine puisque les entiers sont codés sur 4 octets soit 32 bits. Ceci étant, un int variera entre −2^{31} et 2^{31} − 1. Ainsi, la plus grande valeur que peut prendre m est 2^{31} − 1. Au-déla de cette valeur, l’opération m++, met m à −2^{31} qui est négatif et le programme s’arrête.

Q-1-2 : Ce programme va afficher : Sur une machine 32 bits, le programme affichera

• 1 du fait de la ligne 4

• −2^{31} soit −2147483648 du fait de la ligne 10, car les entiers se suivent de manière cyclique. Ainsi le suivant du plus grand est le plus petit

• 2^{31} − 1 soit 2147483647 du fait de la ligne 12, pour les mêmes raisons que précédemment.

Q-2 : Exemple d’erreur syntaxique Trouver et corriger l’erreur de syntaxe contenue dans le programme suivant : (On précise que les commentaires donnés dans le programme ne sont pas source d’erreurs.)

1 #include <s t d i o .h>
2 i n t main( i n t argc , char ∗∗ argv )
3 {
4  f l o a t a ;  / ∗ d e c l a r a t i o n d ’un ré e l ∗ /
5  f l o a t ∗ p, q ;  / ∗ dé c l a r a t i o n de deux pointeurs p et q sur des ré e l s ∗ /
6  p = &a ;  / ∗ p pointe sur a ∗ /
7  ∗p = 0 . 5 ;  / ∗ m o d i f i c a t i o n de a à t r a v e r s p ∗ /
8  q = p;  / ∗ q pointe aussi sur a ∗ /
9  p r i n t f( ”On trouve a=% f de même a=% f \n”, ∗p, ∗q) ; / ∗ a f f i c h a g e ∗ /
10  return 0;
11 }

Voici le message afficher par le compilateur

1 declaPointeur . c : In f u n c t i o n ’main ’ :
2 declaPointeur . c : 8 : e r r o r : incompatible types i n assignment
3 declaPointeur . c : 9 : e r r o r : i n v a l i d type argument of ’unary ∗ ’ (have ’ f l o a t ’ )

L’erreur se trouve à la ligne 8, car q n’est pas déclaré comme un pointeur. Cette erreur de déclaration de pointeur dans une liste est assez courante. Pour le corriger il faut rapporter l’opérateur ’*’à la variable pointeur. Ainsi, on écrira alors int* p,*q .

Q-3 : Exemple d’erreur sémantique On considère les deux programmes suivants :

1 #include <s t d i o .h>
2 i n t main( i n t argc , char ∗∗ argv )
3 {
4  i n t m, ∗p;
5  scanf ( ”% d”,p) ;
6  m = ∗p;
7  p r i n t f( ”La valeur lue est % d \n”,m) ;
8  return 0;
9 }

1 #include <s t d i o .h>
2 i n t main( i n t argc , char ∗∗ argv )
3 {
4  i n t m, ∗p;
5  p = &m ;
6  scanf ( ”% d”,p) ;
7  p r i n t f( ”La valeur lue est % d \n”,m) ;
8  return 0;
9 }

Après compilation et exécution, lorsqu’on rentre une valeur (ici 2), les programmes affichent respectivement

1 Erreur de segmentation  ^{1 La valeur lue est 2}

Tout ce passe bien à droite car scanf attend bien l’adresse d’un entier et p pointe bien sur l’entier m.

Par contre ça se passe mal à gauche car p dans scanf ne pointe sur rien !. Une variable pointeur doit toujours être initialisée puisqu’elle est destinée à stocker l’adresse d’un variable existante. Il est donc conseillé de lui donner la valeur NULL ou 0 si elle ne doit pas être utilisée afin d’éviter quelle pointe par défaut sur une zone mémoire quelconque, au risque de modifier une variable de l’environnement.

Exercice - 2 Exemple d’algorithme : Multiplication Egyptienne

Q-1 : Méthode

Les Egyptiens de l’antiquité savaient :

– additionner deux entiers strictement positifs,

  int somme(int a, int b);

– soustraire 1 à un entier strictement positif,

  int moinsUn(int a);

– multiplier par 1 et 2 tout entier strictement positif,

  int produitParUn(int a);  int produitParDeux(int a);

– diviser par 2 un entier strictement positif pair,

  int divisionParDeux(int a);

Voici un exemple qui multiplie a = 14 et b = 13 en utilisant uniquement ses opérations

14 × 13 = 14 + 14 × (13 − 1)  = 14 + 14 × 12
= 14 + (14 × 2) × (12/2) = 14 + 28 × 6
= 14 + (28 × 2) × (6/2) = 14 + 56 × 3
= 14 + 56 + 56 × (3 − 1) = 70 + 56 × 2
= 70 + (56 × 2) × (2/2) = 70 + 112 × 1
= 70 + 112  =  182

Q-2 : Algorithme. On souhaite écrire un algorithme récursif appliquant cette méthode.

Q-2-1 : (Voir cours) pour les 3 étapes d’un algorithme récursif.

Q-2-2 : Recherche du cas trivial ou Condition de terminaison.

Puisqu’on sait effectuer le produit par 1 et par 2, il vient que lorsque b = 1 respectivement b = 2 le calcul s’effectue directement et l’on retrouve respectivement b et b × 2. En conséquence, b = 1 ou b = 2 est une condition de terminaison de tout éventuel algorithme récursif. Il faut noter que le comportement à adopter porte essentiellement sur b. Il est inutile d’imposer la condition de terminaison sur a. Car si a < b on évalue b × a au lieu de a × b.

Q-2-3 : Réduction du cas général ou décomposition. Soit d = a × b. Lorsque b est pair il est divisible par 2, on peut alors écrire d = a × b comme d = (a × 2) × (b/2) Il en découle l’appel récursif suivant :

 d = multiplicationEgyptienne(produitParDeux(a), divisionParDeux(b))

Lorsque b est impair alors b − 1 est pair et d’après ce qui précède, et le produit par b − 1 est possible. On écrit alors d = a × b comme d = a × (1 + (b − 1)) = a + a × (b − 1). Ce qui donne l’appel récursif suivant :

 d = somme(a, multiplicationEgyptienne(a, moinsUn(b))

Q-2-4 : Proposer un algorithme multiplicationEgyptienne Puisqu’on diminue b, on peut quitte à permutter a et b supposer qu’on a toujours a > b. L’algorithme est donné en langage C ci-dessous avec les différentes fonctions utiles.

1 / ∗∗
2 Fonction e f f e c t u a n t l e p r o d u i t de deux e n t i e r s passes en parametres
3 Entrees :
4  a : l e permier e n t i e r
5  b: l e second e n t i e r
6 Retour :
7  l e p r o d u i t a∗b
8 S o r t i e :
9  op : stocke l e nombre d ’appels r e c u r s i f s e f f e c t u e s
10 ∗ /
11 i n t m u l t i p l i c a t i o n E g y p t i e n n e( i n t a , i n t b, i n t∗ op ){

12

13  i f (1== b)
14  {
15  (∗op )++;
16  return produitParUn(a ) ;
17  }
18  else i f (2 == b)
19  {
20  (∗op )++;
21  return produitParDeux(a ) ;
22  }
23  else {
24  i f (1 == e s t P a i r (b) )
25  {
26  (∗op )++;
27  return m u l t i p l i c a t i o n E g y p t i e n n e(produitParDeux(a ) , divisionParDeux (b) ,op ) ;
28  }else {
29  (∗op )++;
30  return somme (a , m u l t i p l i c a t i o n E g y p t i e n n e(a ,moinsUn (b) , op ) ) ;
31  }
32  }
33 }

Voici à présent la fonction d’évaluation et quelsques fonctions utiles

1 / ∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗ ∗ /
2 i n t e s t P a i r ( i n t a ){
3  i f (0== a%2) return 1;
4  return 0;
5 }

6

7 / ∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗ ∗ /
8 i n t moinsUn ( i n t a ){
9  return a−1;
10 }

1 / ∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗ ∗ /
2 i n t somme ( i n t a , i n t b){
3  return a+b;
4 }

5

6 / ∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗ ∗ /
7 i n t produitParDeux( i n t a ){
8  return a∗2;
9 }

1 / ∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗ ∗ /
2 i n t produitParUn( i n t a ){
3  return a ;
4 }

5

6 / ∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗ ∗ /
7 i n t divisionParDeux ( i n t a ){
8  return a / 2 ;
9 }

Enfin, pour tester le programme, on propose ici la fonction principale

1 / ∗∗
2 ∗  EVALUATIONDE LA FONCTION
3 ∗ /

4

5 i n t main( i n t argc , char ∗∗ argv )
6 {
7  i n t a = 14 , b= 13; / ∗ l e s e n t i e r s a m u l t i p l i e r s i b>a on c a l c u l e r a p l u t o t b∗a ! ∗ /
8  i n t res ;  / ∗ l e r e s u l t a t du p r o d u i t ∗ /
9  i n t nb op =0;  / ∗ l e numbre d ’appels r e c u r s i f s ∗ /
10  res = m u l t i p l i c a t i o n E g y p t i e n n e(a ,b,& nb op ) ;
11  p r i n t f( ”m u l t i p l i c a t i o n E g y p t i e n n e(% d,% d)= % d en % d operations \n”,a ,b, res , nb op ) ;
12  return 0;
13 }

Exercice - 3 Production d’algorithmes et complexité : Multiplication rapide de polynôme On se propose ici de construire un algorithme de produit rapide de deux polynômes. Q-1 : Préliminaires. On considère deux polynômes à coefficients réels de degré 2 :

A(x) = A_{0} + A_{1}x + A_{2}x^{2} et B(x) = B_{0} + B_{1}x + B_{2}x^{2}.

Un calcul naïf du produit A(x)B(x) donne C(x) = C_{0} + C_{1}x + C_{2}x^{2} + C_{3}x^{3} + C_{4}x^{4} avec

(1)  | \begin{matrix}C_{0} = A_{0}B_{0} \\ C_{1} = A_{0}B_{1} + A_{1}B_{0} \\ C_{2} = A_{0}B_{2} + A_{1}B_{1} + A_{2}B_{0} \\ C_{3} = A_{1}B_{2} + A_{2}B_{1} \\ C_{4} = A_{2}B_{2} \end{matrix}  Soit un total de 9 multiplications.

Q-2 : Réduction du nombre de multiplications Afin de réduire le nombre de multiplications, on écrit le produit sous la forme C(x) = C_{0} + C_{1}x + C_{2}x^{2} + C_{3}x^{3} + C_{4}x^{4}, où les coefficients c_{i}, i = 0 … 4 sont donnés par

(2) | \begin{matrix}C_{0} = P_{0} \\ C_{1} = \frac{1}{12}(8(P_{1} − P_{2}) + (P_{4} − P_{3})) \\ C_{2} = \frac{1}{24}( − 30P_{0} + 16(P_{1} + P_{2}) − (P_{3} + P_{4})) \\ C_{3} = \frac{1}{12}(2(P_{2} − P_{1}) + (P_{3} − P_{4})) \\ C_{4} = \frac{1}{24}(6P_{0} − 4(P_{1} + P_{2}) + (P_{3} + P_{4})) \end{matrix} avec | \begin{matrix}P_{0} = A_{0}B_{0} \\ P_{1} = (A_{0} + A_{1} + A_{2})(B_{0} + B_{1} + B_{2}) \\ P_{2} = (A_{0} − A_{1} + A_{2})(B_{0} − B_{1} + B_{2}) \\ P_{3} = (A_{0} + 2A_{1} + 4A_{2})(B_{0} + 2B_{1} + 4B_{2}) \\ P_{4} = (A_{0} − 2A_{1} + 4A_{2})(B_{0} − 2B_{1} + 4B_{2}) \end{matrix}

Les produits de coefficients ne sont maintenant apparents que dans l’évaluation des expressions P_{i}, i = 0, … 4, soit un total de 5 multiplications. Vérifions la correction de ces formules. On peut effectuer un calcul brute (bien fastidieux !) en développant les différentes expressions et en les comparant à celles des C_{i}, i = 0, … 4 obtenues précédemment. Nous allons suivre l’indication donnée dans l’énoncé, à savoir l’utilisation des polynôme de Lagrange. On sait que A(x) × B(x) est polynômes de degré au plus 4. On peut le définir en utilisant ses valeurs en 5 points distincts x_{0}, x_{1}, x_{2}, x_{3}, x_{4}, en utilisant les polynômes de Lagrange. En effet, désignant par l_{i}(x), i = 0, …, 4 les polynômes de Lagrange associés aux points x_{0}, x_{1}, x_{2}, x_{3}, x_{4}

c’est-à-dire l_{i}(x) = \frac{∏_{j=0,j≠i}^{4}(x − x_{j})}{∏_{j=0,j≠i}^{4}(x_{i} − x_{j})} , on a l’expression suivante Q(x) = ∑_{i=0}^{4} Q(x_{i})l_{i}(x) de tout polynôme

Q(x) de degré au plus 4.

Ainsi, on peut écrire

A(x) × B(x) = ∑_{i=0}^{4} (A(x_{i}) × B(x_{i})) l_{i}(x).

Pour le choix suivant des points \{ \begin{matrix}x_{0} = 0, \\ x_{1} = 1, \\ x_{2} = −1, \\ x_{3} = 2, \\ x_{4} = −2 \end{matrix} on obtient \{ \begin{matrix}l_{0}(x) = \frac{1}{4}(x^{4} − 5x^{2} + 4), \\ l_{1}(x) = −\frac{1}{6}(x^{4} + x^{3} − 4x^{2} − 4x) \\ l_{2}(x) = −\frac{1}{6}(x^{4} − x^{3} − 4x^{2} + 4x) \\ l_{3}(x) = \frac{1}{24}(x^{4} + 2x^{3} − x^{2} − 2x) \\ l_{4}(x) = \frac{1}{24}(x^{4} − 2x^{3} − x^{2} + 2x) \end{matrix}

Par conséquent,

(3)  A(x) × B(x) = P_{0}l_{0}(x) + P_{1}l_{1}(x) + P_{2}l_{2}(x) + P_{3}l_{3}(x) + P_{4}l_{4}(x)

où

(4)  | \begin{matrix}P_{0} = & A(0)B(0) & = A_{0}B_{0} \\ P_{1} = & A(1)B(1) & = (A_{0} + A_{1} + A_{2})(B_{0} + B_{1} + B_{2}) \\ P_{2} = & A(−1)B(−1) & = (A_{0} − A_{1} + A_{2})(B_{0} − B_{1} + B_{2}) \\ P_{3} = & A(2)B(2) & = (A_{0} + 2A_{1} + 4A_{2})(B_{0} + 2B_{1} + 4B_{2}) \\ P_{4} = & A(−2)B(−2) & = (A_{0} − 2A_{1} + 4A_{2})(B_{0} − 2B_{1} + 4B_{2}) \end{matrix}

Et les expressions des C_{i}, i = 0, …, 4 en fonction des P_{i}, i = 0, …, 4 découlent du developpement de (3) suivi de l’identification des coefficients des puissances de x.

Q-3 : Généralisation La généralisation à des polynômes de de degrés strictement inférieurs à 3n est possible. C’est-à-dire qu’on peut effectuer le produit de deux polynômes de degrés strictement inférieurs à 3n en cinq multiplications de polynômes de degrés strictement inférieurs à n.

Soit A et B deux polynômes de degrés strictement inférieurs à 3n.

Q-3-1 : On peut les mettre sous la forme A = A_{0} + x^{n}A_{1} + x^{2n}A_{2}, B = B_{0} + x^{n}B_{1} + x^{2n}B_{2} où les A_{i}, B_{i}, i = 0, 1, 2 sont des polynômes de degrés strictement inférieurs à n.

En effet

A = ∑_{i=0}^{3n−1} a_{i}x^{i} = ∑_{i=0}^{n−1} a_{i}x^{i} + ∑_{i=n}^{2n−1} a_{i}x^{i} + ∑_{i=2n}^{3n−1} a_{i}x^{i}

= ∑_{i=0}^{n−1} a_{i}x^{i} + ∑_{i=0}^{n−1} a_{i+n}x^{i+n} + ∑_{i=0}^{n−1} a_{i+2n}x^{i+2n}

= ( ∑_{i=0}^{n−1} a_{i}x^{i}) + x^{n}( ∑_{i=0}^{n−1} a_{i+n}x^{i}) + x^{2n}( ∑_{i=0}^{n−1} a_{i+2n}x^{i})
= A_{0} + x^{n}A_{1} + x^{2n}A_{2}

Q-3-2 : En posant y = x^{n} on a A = A_{0} + yA_{1} + y^{2}A_{2}, B = B_{0} + yB_{1} + y^{2}B_{2}. Et d’après la formule (2), on peut écrire AB = C_{0} + yC_{1} + y^{2}C_{2} + y^{3}C_{3} + y^{4}C_{4}. En y remplaçant y par son expression

il vient AB = C_{0} + x^{n}C_{1} + x^{2n}C_{2} + x^{3n}C_{3} + x^{4n}C_{4}.

Q-4 : Algorithme. On obtient l’algorithme en appliquant la méthode décrite de manière récursive dans l’évaluation des polynômes P_{0}, P_{1}, …, P_{4}.

Q-4-1 : La méthode décrite respecte bien le formalisme de recherche d’algorithmiques dénommé Diviser Pour Régner (voir cours).

Q-4-2 : Voici l’algorithme avec les différentes fonctions issues de l’analyse descendante. Il faut faire attention à la condition de terminaison qui est cachée du fait de la gestion des constantes comme des polynômes de degré 0. On a supposé l’existence d’un type ”Polynome” et utilisé le passage par adresse pour représenter les variables d’entrées modifiables. On vous laisse identifier par leur nom les rôles des différentes fonctions.

1

2 PROCEDURE m u l t i p l i c a t i o n R a p i d e(Polynome A, Polynome B, Polynome∗ C)

3

4 DEBUT

5

6 Polynome P0A,P1A,P2A,P3A,P4A
7  P0B,P1B,P2B,P3B,P4B,
8  P0 ,P1 ,P2 ,P3 ,P4
9  C0 ,C1 ,C2 ,C3 ,C4

10

11 / ∗ D i v i s i o n ∗ /

12

13 fomerLesFacteursDesPi (A,& P0A,& P1A,& P2A,& P3A,& P4A)
14 fomerLesFacteursDesPi (B,& P0B,& P1B,& P2B,& P3B,& P4B)

15

16 / ∗ Appels r e c u r s i f s ∗ /

17

18 SI degre (A) >= 3

19

20  m u l t i p l i c a t i o n R a p i d e(P0A,P0B,& P0)
21  m u l t i p l i c a t i o n R a p i d e(P1A,P1B,& P1)
22  m u l t i p l i c a t i o n R a p i d e(P2A,P2B,& P2)
23  m u l t i p l i c a t i o n R a p i d e(P3A,P3B,& P3)
24  m u l t i p l i c a t i o n R a p i d e(P4A,P4B,& P4)

25

26 FIN SI

27

28 / ∗ Recomposition ∗ /

29

30 formerLesCi (P0,P1,P2,P3,P4,& C0,& C1,& C2,& C3,& C4)

31

32 composerPolyC (C0,C1,C2,C3,C4,C)

33

34 FIN

Les fonctions utilisées dans l’algorithme sont données ci-dessous

1 PROCEDURE
2 formerLesFacteursDesPi (Polynome A,
3  Polynome∗ P0A,
4  Polynome∗ P1A,
5  Polynome∗ P2A,
6  Polynome∗ P3A,
7  Polynome∗ P4A)
8 DEBUT

9

10 Polynome A0, A1, A2

11

12 e x t r a i r e L e s A i (A, &A0, &A1, &A2)

13

14 (∗P0A) <− A0
15 (∗P1A) <− A0 + A1 + A2
16 (∗P2A) <− A0 − A1 + A2
17 (∗P3A) <− A0 + 2 A1 + 4 A2
18 (∗P4A) <− A0 − 2 A1 + 4 A2

19

20 FIN

1 PROCEDURE formerLesCi (Polynome P0,
2  Polynome P1,
3  Polynome P2,
4  Polynome P3,
5  Polynome P4,
6  Polynome∗ C0,
7  Polynome∗ C1,
8  Polynome∗ C2,
9  Polynome∗ C3,
10  Polynome∗ C4)

11

12 DEBUT

13

14 (∗C0) <− P0
15 (∗C1) <− ( 8 (P1−P2) + (P4 − P3) )/12
16 (∗C2) <− ( −30 P0 + 16(P1+P2) − (P3 + P4) )/12
17 (∗C3) <− ( 2 (P2−P1) + (P3 − P4) )/12
18 (∗C4) <− ( 6 P0 − 4 (P1+P2) + (P3 + P4) )/12

19

20 FIN
1 PROCEDURE e x t r a i r e L e s A i ( (Polynome A, Polynome∗ A0, Polynome∗ A1, Polynome∗ A2)
2 DEBUT
3  (∗A0) <− polynome de deg < n e x t r a i t de A
4  (∗A1) <− polynome de deg < n c o e f f i c i e n t de xˆ n dans A
5  (∗A2) <− polynome de deg < n c o e f f i c i e n t de xˆ 2n dans A
6 FIN
1 PROCEDURE
2 composerPolyC (Polynome C0, Polynome C1, Polynome C2, Polynome C3, Polynome C4, Polynome∗ C)
3 / ∗ c o n s t r u i t C = C 0 + xˆ n C 1 + xˆ {2n} C 2 + xˆ {3n} C 3 + xˆ {4n} C 4 ∗ /

Un effort non négligeable doit être mené pour passer de l’algorithme ci-dessus à son implémentation dans le langage C. Outre celui consistant à définir le type Polynôme, dont un choix simple peut être de le considérer comme un tableau (à une entrées) de ses coefficients, le plus difficile sera de dire comment effectuer la décomposition A = A_{0} + x^{n}A_{1} + x^{2n}A_{2} pour un polynôme quelconque.

Q-5 : Complexité. On désigne par f(n) la complexité temporelle égale ici au nombre de multiplications des coefficients nécessaire pour effectuer le produit, par l’algorithme précédent, de deux polynômes de degrés strictement inférieurs à n.

Q-5-1 : Au vue de l’analyse précédente, pour effectuer le produit de deux polynômes de degrés strictement inférieurs à 3n, on effectue 5 produits de polynômes de degrés strictement inférieurs à n afin de générer les coefficients P_{i}, i = 0, …, n. Les produits des coefficients interviennent seulement à cet étape. Le calcul de chacun de ces 5 produits peut se faire par le même algorithme, soit une complexité de f(n) pour chacun. Ce qui donne une équation de complexité f(3n) = 5f(n) + r(n) où r(n) est la complexité des opérations subsidiaires. Ces dernières ne faisant pas intervenir le produit des coefficients des polynômes, r(n) est donc constant pour la complexité qui nous concerne. On a donc f(3n) = 5f(n) + 1 d’où f(n) = 5f(\frac{n}{3}) + 1 .

Q-5-2 : \underline{Déduisons que f(n) = Θ (n^{log_{3}(5)})}.

La fonction de complexité vérifie la récurrence f(n) = 5f(\frac{n}{3}) + n^{k} avec k = 0. D’après le cours la solution

est f(n) = Θ (n^{log_{3}(5)}) . Toujours d’après le cours, on aurait obtenu le même résultat pour k < log_{3}(5). Un calcul naïf donnerait une complexité Θ (n^{2}), qu’il faut comparer avec Θ (n^{1.4650}) car log_{3}(5) = 1.4650.