DEUG MIAS M2

Examen final - 24 avril 1997 - 3 heures

Note : aucun document autorisé.

[Corrigé de l'examen]

Problème (9 points)

On considère des polynômes de degré maximal n de la forme:

P(x) = a_nxⁿ + a_n-1x^n-1 + ... a₁x + a₀

1. Spécifier un type abstrait Polynome avec les constructeurs et opérations suivants :

• construire le polynôme constant P(x) = a0 ;
• construire le polynôme P(x) = Q(x).x + a, Q étant un polynôme et a un réel ;
• retourner le i-ème coefficient d'un polynôme (ai) ;
• calculer la valeur d'un polynôme P(x) en un x donné.

Montrer comment construire le polynôme 3x⁵ + 2x⁴ + 5x² + 3x + 1 avec ce type abstrait.

2. Réaliser les fonctions suivantes en utilisant seulement les constructeurs et opérations du type abstrait :

• calculer le degré du polynôme (d tel que ai = 0 pour tout i > d) ;
• ajouter deux polynômes ;
• calculer la dérivée d'un polynôme (qui est un polynôme) ;
• calculer la valeur maximale d'un polynôme sur les valeurs entières d'un intervalle [a, b] donné, a et b étant entiers.

3. Spécifier et réaliser la fonction Puissance (x: real, n: integer) qui retourne x à la puissance n. Calculer le nombre de multiplications et d'additions nécessaires pour réaliser cette fonction.

4. Réaliser le type abstrait Polynome en utilisant un tableau dont les éléments sont les coefficients du polynôme. Donner la réalisation des constructeurs et des opérations du type abstrait (on pourra utiliser la fonction Puissance).

5. Compter le nombre de multiplications et d'additions nécessaires pour l'opération qui calcule la valeur d'un polynôme pour un x donné.

Ecrire une nouvelle réalisation de cette opération en utilisant la forme suivante d'un polynôme :

P(x) = ((a_n.x + a_n-1).x + a_n-2).x + ... a₁).x + a₀

Compter le nombre de multiplications et d'additions de cette nouvelle réalisation et comparer avec la version précédente.

Exercice 1 (5 points)

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

Les non-terminaux sont écrits entre chevrons lorsqu'ils sont en partie droite de règle et les terminaux sont en caractères gras. <expr> représente une expression du langage, <instr> une instruction, <> le non-terminal vide, et const une constante entière ou d'un type énuméré.

La sémantique de cette instruction est la suivante :

• on calcule la valeur Val [[expr]] de l'expression ;
• On compare cette valeur à chaque choix de chaque cas : pour un choix de la forme c , on teste si Val [[c]] = Val [[expr]] ; pour un choix de la forme c1 .. c2 on teste si Val [[c1]] <= Val [[expr]] <= Val [[c2]]. (c, c1 et c2 sont des constantes entières ou d'un type énuméré).
• si le test est satisfait, l'instruction du cas correspondant est exécutée, et l'exécution de l'instruction case se termine.

Un exemple d'instruction case est le suivant :

case carte of
	1 : writeln ('As!');
	2 .. 10 : writeln (carte);
	11, 12, 13 : writeln ('Figure');
end;
 

1. Donner un diagramme syntaxique de l'instruction case équivalent aux règles de production ci-dessus.

2. Expliquer pourquoi on ne peut pas toujours utiliser cette instruction case pour coder une action de découpage par cas du langage de réalisation.

3. Ecrire une instruction équivalente à l'exemple ci-dessus en utilisant l'instruction if-then-else.

4. Donner la syntaxe de l'instruction if-then-else sous forme de règles de production.

5. Indiquer le résultat de l'exécution de chacune des deux instructions ci-dessous, pour x valant respectivement 5, 15 et 50 :

if x < 20 then 
    if x < 10 then writeln ('petit')
else writeln ('pas petit');
 
if x < 20 then 
    if x < 10 then writeln ('petit')
    else writeln ('moyen');
else writeln ('grand');
 

Exercice 2 (4 points)

On rappelle qu'en Pascal, le mode de passage des paramètres d'une procédure s'effectue par adresse s'il y a le mot-clé "var" devant ses parametres formels, ou s'effectue par valeur sinon. On 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. Indiquer, pour chaque utilisation de la variable i, quelle est la déclaration (variable locale, globale ou paramètre) correspondante. On utilisera les numéros de ligne pour référencer les utilisations et les déclarations.

2. Donner le contenu du tableau a et de la variable i après chacun des appels de procédures des lignes 36, 37, 38 et 39. Donner l'affichage final du programme.

Question de cours (2 points)

Définir les notions de mémoire et d'environnement et indiquer dans quelles circonstances chacun d'eux est modifié. Donner un exemple de programme court et l'état de la mémoire et de l'environnement lors de son exécution.