On considère des polynômes de degré maximal n de la forme:
P(x) = anxn + an-1xn-1 + ... a1x + a0
1. type abstrait Polynome :
type polynôme
{ constructeurs }
polynôme_constant : réel -> polynôme
construire : polynôme * réel -> polynôme
{ opérations }
ième : polynôme * entier -> réel
éval : polynôme * réel -> réel
Le polynôme 3x5 + 2x4 + 5x2 + 3x + 1 est construit comme suit (noter que le terme en x3 a un coefficient de 0) :
construire (
construire (
construire (
construire (
construire (
polynôme_constant(3), 2), 0), 5), 3), 1)
Les polynômes construits sont successivement :
3 3x + 2 3x2 + 2x + 0 3x3 + 2x2 + 0x + 5 3x4 + 2x3 + 0x2 + 5x + 3 3x5 + 2x4 + 0x3 + 5x2 + 3x + 1
2. Spécification des fonctions :
degre = polynôme -> entier
ajouter = polynôme * polynôme -> polynôme
dérivée = polynôme -> polynôme
max = polynôme * entier * entier -> réel
Réalisation des fonctions (n est une constante qui définit le degré maximal des polynômes, comme indiqué dans l'énoncé) :
fonction degré (p) lexique d : entier début (* tester les coefficients nuls à partir du terme de plus haut degré *) d <- n tantque d > 0 et ième (p, n) = 0 faire d <- d - 1 retourner d fonction ajouter (p1, p2) lexique p : polynôme i, d : entier début (* construire le polynôme à partir du terme de plus haut degré (voir question 1). Chaque coefficient est la somme des coefficients de même degré de p1 et p2 *) d <- max (degré(p1), degré(p2)) p <- polynôme_constant (ième(p1, d) + ième(p2, d)) pour i parcourant [d-1 .. 0] faire p <- construire (p, ième(p1, i) + ième(p2, i)) retourner p fonction dérivée (p) lexique dp : polynôme i, d : entier début (* la dérivée de anxn + an-1xn-1 + ... a1x + a0 est n.anxn-1 + (n-1).an-1xn-2 + ... a2x + a1 *) d <- degré (p) dp <- polynôme_constant (d * ième(p, d)) pour i parcourant [d-1 .. 1] faire dp <- construire (p, i * ième(p, i)) retourner dp fonction max (p, a, b) lexique m : réel x : entier y : réel début (* calculer les valeurs de p en a, a+1, ... b et conserver la plus grande *) m <- éval (p, a) pour x parcourant [a+1 .. b] faire y <- éval (p, x) si y > m alors m <- y retourner m
3. Spécification et réalisation de la fonction Puissance :
Puissance = réel * entier -> réel fonction Puissance (x, n) (* n est supposé >= 0 *) lexique res : réel i : entier début res <- 1 pour i parcourant [1 .. n] faire res <- res * x retourner res
Cette fonction nécessite n multiplications et n additions (chaque tour de la boucle pour nécessite d'ajouter 1 à i, d'où les n additions).
Note: on peut calculer cette fonction de façon plus efficace, en constatant que :
Dans les deux cas, xp n'a besoin d'être calculé qu'une fois. S'il faut p multiplications pour calculer xp, pour calculer xn il en faut donc p+1 si n est pair, p+2 si n est impair, avec p = n/2. Bien entendu, xp peut lui-même être calculé selon le même principe. Au total, xn peut être calculé avec environ log(n) multiplications.
4. Réalisation du type abstrait Polynome (n est le degré maximal) :
type polynôme = tableau [0 .. n] de réel;
Note : une représentation un peu plus efficace consisterait à utiliser un type produit contenant le tableau des coefficients et le degré du polynôme. Il serait alors intéressant de coder les fonctions de la question 2 par codage implicite.
Réalisation des constructeurs et des opérations du type abstrait :
fonction polynôme_constant (a) lexique p : polynôme i : entier début p[0] <- a; (* terme constant *) pour i parcourant [1 .. n] faire p[i] <- 0; (* les autres termes sont nuls *) retourner p fonction construire (q, a) lexique p : polynôme début (* le ième coefficient de q devient le i+1ème coefficient de p, et a devient le coefficient constant. Il faut donc que q soit de degré strictement inférieur à n *) p[0] <- a pour i parcourant [0 .. n-1] faire p [i+1] <- q[i] retourner p fonction ième (p, i) début retourner p[i] fonction éval (p, x) lexique val : réel i : entier début val <- 0 pour i parcourant [0 .. n] faire val <- val + p[i] * Puissance(x, i) retourner val
5. Nombre de multiplications et d'additions de éval : la boucle pour est parcourue n+1 fois, et dans chaque boucle on a :
Au total, on a donc n+1 + (0 + 1 + 2 + .. + n) additions et autant de multiplications. Sachant que la somme des n premiers entiers est n.(n+1)/2, le nombre d'additions et de multiplications est n+1 + n.(n+1) / 2, soit n2/2+3n/2+1.
Nouvelle réalisation de cette opération en utilisant la forme suivante (dite forme de Horner) : P(x) = ((an.x + an-1).x + an-2).x + ... a1).x + a0
fonction éval2 (p, x) lexique val : réel i : entier début val <- p[n] pour i parcourant [n-1 .. 0] faire val <- val * x + p[i] retourner val
Dans cette nouvelle version, la boucle est parcourue n fois, et chaque tour de boucle nécessite une multiplication et une addition. Au total, on a donc n additions et n multiplications. Cette version est donc beaucoup plus efficace que celle de la question 4.
On considère la syntaxe de l'instruction "case" d'un langage proche de Pascal, définie par les règles de production suivantes :
instrcase ::= case <expr> of <listecas> end listecas ::= <cas> | <listecas> ; <cas> cas ::= <listechoix> : <instr> | <> listechoix ::= <choix> | <listechoix>, <choix> choix ::= const | const .. const
1. Diagramme syntaxique équivalent :
2. Dans le langage de réalisation, l'instruction de découpage par cas utilise une expression pour chaque cas. Par exemple :
selon le cas d
d < 0 : écrire ("pas de solution")
d = 0 : écrire ("une solution double")
d > 0 : écrire ("deux solutions")
Dans l'instruction case de l'exercice, on compare une
même variable à plusieurs constantes. L'exemple
ci-dessus ne peut donc pas être traduit par une instruction
case. Pour qu'un découpage par cas soit traduisible en
une instruction case, il faut que chacune des expression soit
de la forme x = constante. ou x >= const1 et
x <= const2, et que x soit de type entier ou
énuméré.
3. Traduire l'instruction case ci-dessous avec des if-then-else :
case carte of
1 : writeln ('As!');
2 .. 10 : writeln (carte);
11, 12, 13 : writeln ('Figure');
end;
On obtient une cascade de if-then-else :
if carte = 1
then writeln ('As!')
else if carte >= 2 and carte <= 10
then writeln (carte)
else if carte = 11 or carte = 12 or carte = 13
then writeln ('Figure');
4. Syntaxe de l'instruction if-then-else sous forme de règles de production :
instrif ::= if <expr> then <instr> <suite> suite ::= else <instr> | <>
5. Résultat de l'exécution des instructions ci-dessous, pour x valant 5, 15 et 50 :
if x < 20 then
if x < 10 then writeln ('petit')
else writeln ('pas petit');
x = 5 -> petit
x = 15 -> pas petit
x = 50 -> (rien)
Note : l'indentation de l'instruction était (intentionnellement) trompeuse : le "else" correspond au second if (if x < 10) et non pas au premier. Si x < 20 est faux, il n'y a pas de partie "else" correspondant, et le programme n'écrit rien.
if x < 20 then
if x < 10 then writeln ('petit')
else writeln ('moyen');
else writeln ('grand');
x = 5 -> petit
x = 15 -> moyen
x = 50 -> grandOn considère le programme suivant :
1 program exam; 2 var i : integer; 3 a : array[0..4] of integer; 4 5 procedure p1 (var i, j : integer); 6 begin 7 i := i+1; 8 j := j+1; 9 a[i] := a[j-1] +1; 10 end; 11 12 procedure p2 (j : integer); 13 var i : integer; 14 begin 15 i := 2; 16 j := j+1; 17 a[i] := a[j]-1; 18 a[j] := a[i]+1; 19 end; 20 21 procedure p3 (x : integer); 22 begin 23 a[4] := a[4]-1; 24 x := x+1; 25 i := 3; 26 a[i] := a[i]+1; 27 end; 28 29 begin 30 a[0] := 0; 31 a[1] := 1; 32 a[2] := 2; 33 a[3] := 3; 34 a[4] := 4; 35 i := 0; 36 p2 (a[2]); 37 p1 (a[1], a[0]); 38 p1 (i, i); 39 p3 (a[4]); 40 writeln (a[0]+a[1]+a[2]+a[3]+a[4], i); 41 end.
1. Ligne de déclaration correspondant à chaque utilisation de la variable i :
2. Contenu du tableau a et de la variable i (seules sont mentionnées les valeurs affectées) :
a[0] a[1] a[2] a[3] a[4] i après ligne 35 0 1 2 3 4 0 après ligne 36 2 3 après ligne 37 1 2 2 après ligne 38 3 2 après ligne 39 4 3 3
L'affichage final du programme est donc 13, 3.
(voir cours).