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

Seules les notes de cours sur support papier sont autorisées.

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 : A l’exécution ce programme terminera-t-il ? Justifier. Q-1-2 : S’il se termine, qu’affichera-t-il ?

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 ’ )

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}

Expliquer ces résultats.

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 : Rappeler les 3 étapes principales à suivre pour définir un algorithme récursif.

Q-2-2 : Recherche du cas trivial ou Condition de terminaison. Que fait la méthode précédente lorsque dans le produit a × b, on a b = 1 ? b = 2 ? En déduire une condition de terminaison d’un éventuel algorithme récursif.

Q-2-3 : Réduction du cas général ou décomposition. Décrire suivant la parité de b, une étape d’application de la méthode sur le produit a × b. En déduire qu’un appel récursif de la méthode est possible.

Q-2-4 : Proposer un algorithme multiplicationEgyptienne qui prend en entrée deux entiers et qui retourne leur produit selon la méthode précédente. Cet algorithme ne fera usage que des fonctions traduisant les opérations admises. On supposera qu’on dispose d’une fonction int estPair(int a), retournant 1 si a est pair et 0 si a est impair.

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. On ne se préoccupera pas de la manière dont un polynôme est stocké en mémoire, on pourra simplement le désigner par une lettre.

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}.

Quel est le nombre de multiplications (sur les coefficients) nécessaires pour calculer le produit A(x) × B(x) ?

Q-2 : Réduction du nombre de multiplications On souhaite à présent effectuer le même calcul A(x) × B(x) avec seulement 5 multiplications. On commence par écrire C(x) = A(x) × B(x) 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

(1) | \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}

Vérifier la correction des formules proposées. En remarquant que les C_{i}, i = 0, …, 4 sont des entiers si A et B sont à coefficients entiers, conclure que le produit de deux polynômes de degrés 2 peut s’effectuer avec seulement 5 multiplications. On pourra remarquer que C(x) étant un polynôme de degré 4, son expression peux être obtenue en l’évaluant en 5 points distincts (0, 1, −1, 2, −2) et en utilisant le polynôme d’interpolation de Lagrange associé. C’est-à-dire

\begin{aligned}C(x) & = & \frac{C(0)}{4}(x^{4} − 5x^{2} + 4) − \frac{C(1)}{6}(x^{4} + x^{3} − 4x^{2} − 4x) − \frac{C(−1)}{6}(x^{4} − x^{3} − 4x^{2} + 4x) \\ & + & \frac{C(2)}{24}(x^{4} + 2x^{3} − x^{2} − 2x) + \frac{C(−2)}{24}(x^{4} − 2x^{3} − x^{2} + 2x) \end{aligned}

Q-3 : Généralisation On se propose de fournir un moyen d’effectuer le produit de deux polynômes de degrés strictement inférieurs à 3n en cinq multiplications de polynômes de degrés stritement inférieurs à n. Soit alors A et B deux polynômes de degrés strictement inférieurs à 3n.

Q-3-1 : Montrer que l’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.

Q-3-2 : Montrer qu’en adoptant les formules (1), on peut écrire

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 : Montrer que le calcul du produit de deux polynômes décrit par la méthode précédente rentre dans le formalisme de recherche d’algorithmiques dénommé Diviser Pour Régner.

Q-4-2 : Décrire l’algorithme récursif ainsi défini. On précisera avec soin la condition de terminaison. Q-5 : Complexité. On désigne par f(n) la complexité temporelle égale ici au nombre de multiplications nécessaires pour effectuer le produit, par l’algorithme précédent, de deux polynômes de degrés strictement inférieurs à n.

Q-5-1 : Montrer d’après ce qui précède qu’on a la relation de récurrence f(3n) = 5f(n) + n^{k}, où k est un entier positif ou nul à préciser.

Q-5-2 : En déduire que f(n) = Θ (n^{log_{3}(5)}). Comparer cette complexité à celle qu’on aurait obtenue en effectuant un produit naïf.