Conservatoire National des Arts et Métiers Informatique cycle A

Algorithmique et Programmation

Exercices Dirigés 1

Exercices sur les grammaires

Exercice 1

1. Une date est donnée sous la forme “lundi 5” ou sous la forme “5 lundi”. Donner une grammaire BNF qui reconnait l’une ou l’autre de ces formes.

2. donner une grammaire BNF pour décrire les cases d’un échiquier (elles sont numérotées de A à H et de 1 à 8).

3. Définir une grammaire pour les numéros d’immatriculation. Un numéro d’immatriculation est une suite de 1 à 4 chiffres dont le premier chiffre n’est pas zéro, suivie de 2 lettres, suivies d’une suite de 2 chiffres différente de 00.

Exercice 2

1. Combien peut on représenter d’informations différentes avec un mot de n bits ?

2. Soit la grammaire:

terme ::= (lettre | chiffre) terme | lettre | chiffre
lettre ::= A| B | C
chiffre ::= 0| ... | 9

Donnez au moins 2 sémantiques pour cette grammaire.

3. Ecrire l’expression 7 + 8 * 2 + 5 - 1 en notation infixe, postfixe

4. quelle est la valeur de 2 ^2 ^3 si ^associe à gauche ? à droite ? (l’opérateur ^désigne l’élévation à la puissance)

Corrigé

Exercice 1

1. Les symboles terminaux (ou littéraux) sont les chiffres de 0 à 9 et le point représenté par point ainsi que les chaînes de caractères représentant le nom des jours de la semaine. On utilise les non-terminaux

Chiffre, Chiffre_non_nul, Jour, Numero_de_jour, Date pour expli-

quer la construction d’une forme correcte d’une date. Le point d’entrée

est Date.
<Date> ::= <Jour> <Numero_de_jour>  point
              | <Numero_de_jour > <Jour> point
<Jour> ::= lundi| mardi | ....
<Numero_de_jour>::= 3 (0|1)
                   | (2|1) <Chiffre>
                   | <Chiffre_non_nul>
<Chiffre_non_nul> ::= 1|..|9
<Chiffre> ::= 0 | <Chiffre_non_nul>

2. Grammaire pour l’échiquier.

<Case> ::= <Lettre> <Chiffre>
<Lettre> ::= A | .... | H  <Chiffre> ::= 1| ....|8

3. Les plaques d’immatriculation.

Constatons que l’on ne peut pas utiliser la répétition indiquée par des { } pour expliquer la construction d’une suite de un à quatre chiffres. Il faut donc introduire un non-terminal pour chacune des suites possibles. Voici une solution. Il en existe plusieurs autres.

<Nume'ro> ::= <C_4> <L_2> <DE>
<C_4> ::= <C> | <C_2>| <C_2><C_0>| <C_2> <C_0><C_0>
<DE>  ::=  <C>  <C_0> | <C_0><C>
<C_2> ::= <C> <C_0>   <C_0>::= <C> | 0    <C> ::= 1|2|3 .....|9
<L_2> ::= <L><L>     <L> ::= A | ....| Z

Exercice 2

1. Avec un bit, on représente 2 informations. Supposons que, avec (n−1) bits, on puisse représenter 2^{(n−1)} informations, alors avec n bits on peut construire deux familles de mots : une famille de 2^{(n−1)} mots commençant par 0 suivi d’un mot de (n − 1) bits, et une famille de 2^{(n−1)} mots commençant par 1. Au total, on peut donc construire 2^{n} mots donc représenter 2^{n} informations.

2. On peut considérer chaque symbole comme un chiffre : on a 13 symboles donc on peut considérer un mot de ce langage comme l’écriture d’un nombre en base 13. On peut aussi considérer un mot de ce langage comme une chaîne de caractères.

3. Il faut d’abord parenthéser complétement cette expression. Choisissons par exemple ce parenthésage : 7 + (((8 ∗ 2) + 5) − 1), qui s’écrit en notation infixe +7 − + ∗ 8 2 5 1 et 7 8 2 ∗ 5 + 1 − +.

4. Si ^possède un statut associant à gauche, alors ( 2^2) ^3 = 64. S’il associe à droite, alors : 2^(2^3) = 256.

Algorithmique et Programmation

Exercices Dirigés 2 Exercices de logique

Exercice 1 Soient a, b, c trois entiers positifs. Montrez que :

1. la proposition (a < b) → (a = b) a pour négation a < b

2. la proposition (a < b) → (a = a) a pour négation a ≠ a Exercice 2 Mettre chacune des phrases suivantes sous la forme d’une proposition.

1. Si (a < 0) et (b > 0) alors vrai sinon faux

2. Si (a < 9) alors, si (b > 3) alors vrai sinon faux, sinon faux

3. Une condition nécessaire pour qu’une suite S converge est que S soit bornée.

4. Une condition suffisante pour qu’une suite S ne converge pas est que S ne soit pas bornée.

5. Une condition suffisante pour que X soit impair est que X soit plus

grand que 2 et premier. Exercice 3 Mettre sous la forme de pédicats les expressions suivantes:

1. E est un ensemble de nombre non tous nuls.

2. E est un ensemble de nombre tous non nuls.

3. tout élève étudie au moins une langue étrangère.

4. certaines personnes deviennent agressives quand elles conduisent.

Exercice 4

Soient les propositions: (P) il pleut (S) la sortie est annulée (M) etre mouillé (R) rester à la maison

Traduire les phrases suivantes:

1. Si il pleut et si je reste à la maison, je ne serai pas mouillée.

2. Si il pleut mais si je reste à la maison, je ne serai pas mouillée.

3. Si il pleut et si la sortie n’est pas annulée ou si je ne reste pas à la maison, je serai mouillée.

4. que la sortie soit annulée ou non, s’il pleut, je reste à la maison.

Exercice 5

Écrire l’expression logique qui décrit les heures d’ouvertures d’un magasin . Celles ci sont: tous les jours de 7 heures à 13 heures et de 16 heures à 19

heures, sauf le dimanche aprés-midi et le lundi toute la journée.

0.1 corrigé

Exercice 1 On a :

((a < b) ⇒ (a = b)) ⇔ (Not (a < b)) or (a = b)

Sa négation est donc : (Not (Not (a < b))) ∧ (Not (a = b)) donc (a < b). Exercice 2 Les formules propositionnelles suivantes sont des tautologies.

1. S converge ⇒ S bornée

2. S n’est pas bornée ⇒ S ne converge pas

3. (X > 2) ∧ (X est premier) ⇒ (X est impair) Exercice 3

1. ∃x ∈ E, x ≠ 0

2. ∀x ∈ E, x ≠ 0

3. ∀x ∈ {Elèves}, ∃l ∈ {Langues}, (x apprend l)

4. ∃p ∈ {Personnes}, (p conduit) ⇒ (p agressive) Exercice 4

1. (P ∧ R ) ⇒ (Not M)

2. P ⇒ M

3. Deux traductions possibles :

((P ∧ (Not S)) or (Not R)) ⇒ M (P ∧ ( (Not S) or (Not R))) ⇒ M Sont-elles équivalentes?

4. (S or Not S) ∧ P ⇒ R (dans une syntaxe à la caml) on a: (jour ¬ "lundi" ∧ (heure ≥ 7) ∧ (heure ≤ 13)) ∨ ((jour ¬ "dimanche") ∧ (jour ¬ "lundi") ∧ (heure ≥ 6) ∧ (heure ≤ 19))

Algorithmique et Programmation

Exercices Dirigés 3

Exercice 1

1. Expliquer l’évaluation des déclarations suivantes:

nbr_1 : constant integer := 25;
nbr_2 : constant integer := nbr_1 + 10;
vrai : constant boolean := true;

2. Qu’elles ont dans cet environnement les valeurs des expressions:

vrai & false
nbr_1
``true” or vrai

3. Completer si possible les declarations suivantes supposées évaluées dans l’environnement courrant:

 x: constant ?? := (nbr_1 * nbr_2) > (nbr_2 * nbr_2) ;
 y: constant ?? := x+1;

Exercice 2

Créer un environnement pour calculer a^{7}, où a est un nombre entier que vous choisissez. Combien d’opérations effectuez-vous ? Trouvez une autre méthode nécessitant moins d’opérations en remarquant que a^{4} = (a^{2})^{2}. calculer alors a^{16}, a^{25}. Généralisez la méthode.

Exercice 3 Soit a un entier fixé. Calculez 2 + 3a + 4a^{2} + a^{3} + 2a^{4}. Comptez le nombre d’opérations effectuées. Comment réduire ce nombre ? Exercice 4 Evaluer les déclarations suivantes dans un état courant ⌊Env⌋ ⌈Mem⌉.

 x: integer := 1; – 1
 y: integer := x*3; – 2

Puis dans l’état courant

  x: integer := y*2; – 3

Quelle est la valeur de x+2*x?

corrigés

Exercice 1

Soit Env_Init l’environnement contenant les identificateurs prédéfinis. E désigne l’environnement courant.

nbr_1 : constant integer := 25;

C’est une déclaration de constante. On détermine d’abord le type du membre droit : 25 est une constante de type integer, donc nbr_1 est un identificateur de type integer. Ce qui est bien equivalent ł’expression de type de la déclaration. Cette information est mise dans l’environnement mais nous ne la faisons pas figurer explicitement. On évalue ensuite le membre droit pour créer la nouvelle liaison (nbr_1,25), placée ensuite en tête de l’environnement. On obtient : E_1 =⌊(nbr_1,25)◁ Env_Init⌋.

nbr_2 : constant integer := nbr_1 + 10;

Il s’agit encore d’une déclaration de constante. L’opérateur + attend deux arguments de type integer. Or, nbr_1 et 25 sont de type integer. Donc, nbr_1+10 est de type integer et nbr_2 est reconnu de type integer. Ensuite, la déclaration est évaluée. L’environnement devient : E_2 =⌊(nbr_2,35)(nbr_1,25)◁ Env_Init⌋.

Pour typer la déclaration suivante, on détermine d’abord le type du membre droit, true, qui est une constante de type boolean. Donc vrai est un identificateur de type boolean. L’environnement devient : E_4 =⌊(vrai,true)◁ Env_3⌋.

L’opérateur & prend deux opérandes de type boolean. L’expression vrai & false est donc bien typée, de type boolean.

Le résultat d’une comparaison de deux valeurs de type integer est une valeur booléenne donc x est de type boolean.

 x: constant boolean := (nbr_1 * nbr_2) > (nbr_2 * nbr_2) ;

On obtient E_5 =⌊(x,true)◁ Env_4⌋. Par contre, l’expression x+1 est mal typée dans Env_5, puisque x est de type boolean.

Exercice 2

Donnons à a la valeur 2, par exemple. Soit Env l’environnement courant au début de cet exercice.

a: constant integer := 2 ;
a_7 : constant integer := a * a * a * a * a * a * a ;

Notez le choix de l’identificateur : a_7 suffisamment explicite. Il est donc inutile d’expliquer le rôle de cet identificateur à l’aide d’un commentaire. On a effectué 6 multiplications. L’environnement est devenu E = ⌊(a_7,128)(a,2)◁ Env⌋. Procédons alors ainsi :

a_2 :constant integer := a*a ;
a_4 :constant integer := a_2*a_2 ;
a_7 :constant integer := a_4*a_2* a ;

L’environnement est maintenant E_1 = ⌊(a_7,128)(a_4,16)(a_2,4)◁ E⌋. On a effectué seulement 4 multiplications. Continuons ainsi pour calculer a^{16}.

a_8 :constant integer :=  a_4*a_4 ;;
a_16 :constant integer :=  a_8*a_8 ;;

On a effectué 4 multiplications au lieu de 15 avec l’écriture explicite. Notons que a^{16} = ((((a^{2})^{2})^{2})^{2}). Pour calculer a^{25}, remarquons alors que :

25 = 1 + 24 = 1 + 2 ∗ 12 = 1 + 2 ∗ 2 ∗ 2 ∗ (1 + 2)

et donc que : a^{25} = a ∗ (a^{2} ∗ a)^{2^{2^{2}}} .

Donc, on va calculer a^{2}, puis a^{3} puis a^{6} puis a^{12} puis a^{24} puis a^{25}. Nous avons divisé 25 par 2 puis divisé le quotient obtenu par 2, etc. Pour généraliser cette démarche, il nous faut “partir en sens inverse”. En effet, nous ne pouvons pas supposer disposer de cette suite de quotients par 2. Il nous faut la découvrir tout en effectuant le calcul de a^{n}. Reformulons ainsi notre raisonnement dans le cas n = 25 : pour calculer a^{25}, il suffit de calculer le carré de a^{12} et de le multiplier par a car 25 = 2 ∗ 12 + 1. Pour obtenir a^{12}, il suffit de calculer le carré de a^{6} puisque 12 = 2 ∗ 6 + 0. Pour obtenir a^{6}, il suffit d’élever a^{3} au carré et pour obtenir a^{3}, il suffit de multiplier a^{2} par a puisque 3 = 2 ∗ 1 + 1. Nous avons progressivement découvert l’égalité 25 = 1 + 2 ∗ 2 ∗ 2 ∗ (1 + 2).

Pour calculer a^{n}, on fait apparaître le quotient et le reste de la division entière de n par 2 : n = 2 ∗ p + r. On utilise alors les équations suivantes :

a^{2p+r} = (a^{p})^{2} ∗ a^{r} et a^{0} = 1

qui ramènent donc le problème à celui, plus simple, du calcul de a^{p}. Cette méthode est dite fondée sur la dichotomie puisqu’elle consiste à ramener un problème à un autre “deux fois plus simple”.

Cet exercice est le prolongement du précédent.

(* A *)
 val_polynome :constant integer := 2 + 3*a + 4*a*a + a*a*a + 2*a*a*a*a ;;
(*B*)
 val_polynome :constant integer := 2 + 3*a + 4*a_2 + a_2*a + 2*a_4 ;;
(*C*)
 val_polynome :constant integer := 2 + a * ( 3 + a * ( 4 + a * (1 + 2 * a))) ;;

L’évaluation de (*A*) demande 13 opérations. La méthode par dichotomie (*B*) en effectue 10. Mais, dans (*C*), on calcule seulement 8 opérations, simplement en imposant un ordre sur les calculs à l’aide de parenthèses. Rappelons que les parenthèses servent à préciser la sémantique de l’expression. Ici, à cause des conventions de priorité, il n’y a pas d’ambiguïté dans la première écriture de val_polynome. Les parenthèses servent uniquement à diriger les calculs.

La méthode utilisée ici s’appelle la méthode de Horner. Elle repose sur l’écriture de P (x) = a_{0} + a_{1}x + ⋯ + a_{n}x^{n} sous la forme suivante :

P (x) = a_{0} + x(a_{1} + x(a_{2} + ⋯ x(a^{n−1} + x a_{n}) ⋯)).

Exercice 4

Soit ⌊Env⌋ ⌈Mem⌉ l’état présent en début de session. Détaillons les états courants aux points numérotés :

  1. ⌊(x,@x)◁ Env⌋ ⌈(@x,1)◁ Mem⌉
  2. Posons Env1 = ⌊(y,@y)(x,@x)◁ Env⌋ et Mem1 = ⌈(@y,3)(@x,1)◁ Mem⌉.

3. La seconde déclaration de x crée l’état Env2 = ⌊(x,@x_1)◁ Env1⌋, Mem2

     = ⌈(@x_1,6)◁ Mem1⌉.

L’évaluation de x+2*x dans ⌊Env2⌋ ⌈Mem2⌉ donne la valeur 18.

Algorithmique et Programmation

Exercices Dirigés 4

Exercice 1

1. On utilise l’instruction : put(expression); où expression peut être une expression numérique, évaluer le bloc Ada suivant :

declare
x : constant integer := 1; – 1
y : constant integer := x*3; – 2
begin
put(y+2);
declare
 x : constant integer := y*2; – 3
begin
 put(x+2*x);
end;– 5
put(x+3);
end;

2. Même question avec la session :

declare
x: integer := 1; – 1
y: integer := x*3; – 2
begin
declare
 x: integer := y*2; – 3
begin
 put(x+2*x,width=>3);

end;
– 4
put(x+3,width=>3);
end;

Exercice 2

1. Evaluer l’unité Ada :

declare
nb1 : integer := 25;– 1
nb2 : integer := nb1 + 10; – 2
begin
declare
nb1: integer := nb2 + 20; – 3
begin
put(nb2);
put(nb1);
declare
 nb3: integer := nb1 * nb1; – 4
begin
 put(nb3 * nb2);
 declare
  x : boolean := (nb1*nb2)>(nb2*nb2); – 5
  y : boolean := x=true;
 begin
  null;
 end;
end;
end;
end;

2. Transformer cette unité de façon à n’utiliser que des constantes.

corrigé

Exercice 1

Résumons à propos de cet exercice la sémantique de l’évaluation des déclarations en Ada. Dans ce langage :

1. Les déclarations sont évaluées les unes à la suite des autres et, après chaque déclaration, l’environnement est étendu.

2. On ne peut pas avoir deux fois le même identificateur dans une liste de déclarations.

3. On ne peut pas mélanger des déclarations et des instructions. Pour insérer de nouvelles déclarations après une instruction, il faut créer un bloc.

4. L’élaboration d’une déclaration se fait en introduisant d’abord l’identificateur dans l’environnement avec une valeur qui n’est pas encore connue. Puis l’expression d’initialisation est évaluée dans l’environnement ainsi étendu.

1. declare
 x : constant integer := 1; – 1
 y : constant integer := x*3; – 2
begin
 put(y+2);
 declare
  x : constant integer := y*2; – 3
 begin
  put(x+2*x);
end;– 5
 put(x+3);
end;
–––––––––––––––––––-
          5         18          4
–––––––––––––––––––-

Soit ⌊Env⌋ ⌈Mem⌉ l’état courant en début d’exécution de cette session. Détaillons l’évolution de cet état aux points nommés.

(a) ⌊(x,1)◁ Env⌋ ⌈Mem⌉
(b) ⌊(y,3)(x,1)◁ Env⌋ ⌈Mem⌉.

C’est dans cet état que va être évaluée et imprimée la valeur de l’expression y+2.

(c) La déclaration du bloc interne permet la double déclaration de x :

⌊(x,6)(y,3)(x,1)◁ Env⌋ ⌈Mem⌉.

Dans cet état, l’exécution de la commande put(x+2*x); imprime la valeur 18.

(d) Il y a retour au bloc englobant, et donc à la composante environnement du point 2. L’état devient par conséquent : ⌊(y,3)(x,1)◁ Env⌋ ⌈Mem⌉. Seule la première déclaration de x est visible. L’exécution de put(x+3); dans cet état imprime la valeur 4.

2. declare
x: integer := 1; – 1
y: integer := x*3; – 2
begin
declare
x: integer := y*2; – 3
begin
put(x+2*x,width=>3);
end;
– 4
put(x+3,width=>3);
end;
–––––––––––––––––––-
18  4
–––––––––––––––––––-

Soit ⌊Env⌋ ⌈Mem⌉ l’état présent en début de session. Détaillons les états courants aux points numérotés :

(a) ⌊(x,@x)◁ Env⌋ ⌈(@x,1)◁ Mem⌉
(b) Posons Env1 = ⌊(y,@y)(x,@x)◁ Env⌋ et Mem1 = ⌈(@y,3)(@x,1)◁ Mem⌉.

(c) La déclaration locale de x crée l’état Env2 = ⌊(x,@x_1)◁ Env1⌋,

Mem2 = ⌈(@x_1,6)◁ Mem1⌉.

L’évaluation de !x+2*x dans ⌊Env2⌋ ⌈Mem2⌉ donne la valeur 18.

(d) Retour au bloc englobant et donc construction de l’état ⌊Env2⌋

    ⌈Mem2⌉.

L’exécution de put(x+3); va imprimer la valeur 4.

Exercice 2

1. Evaluation de l’unité Ada :

declare
 nb1 : integer := 25;– 1
 nb2 : integer := nb1 + 10; – 2
begin
  declare
   nb1: integer := nb2 + 20; – 3
  begin
   put(nb2);
   put(nb1);
   declare
    nb3: integer := nb1 * nb1; – 4
   begin
    put(nb3 * nb2);
    declare
     x : boolean := (nb1*nb2)>(nb2*nb2); – 5
     y : boolean := x=true;
    begin
     null;
    end;
   end;
  end;
end;
–––––––––––––––––––-
         35         55     105875
–––––––––––––––––––-

Soit ⌊Env⌋ ⌈Mem⌉ l’état présent en début de session.

 (a) ⌊(nb1,@nb1)◁ Env⌋, ⌈(@nb1,25)◁ Mem⌉
 (b) ⌊(nb2,@nb2)(nb1,@nb1)◁ Env⌋, ⌈(@nb2,35)(@nb1,25)◁ Mem⌉

 (c) ⌊(nb1,@nb1_1)(nb2,@nb2)(nb1,@nb1)◁ Env⌋,
    ⌈(@nb1_1,55)(@nb2,35)(@nb1,25)◁ Mem⌉.

Impression des valeurs 35 et 55.

 (d) ⌊(nb3,@nb3)(nb1, @nb1_1)(nb2,@nb2)(nb1,@nb1)◁ Env⌋,
    ⌈(@nb3,3025)(@nb1_1,55)(@nb2,35)(@nb1,25)◁ Mem⌉
 (e) ⌊(x,@x)(nb3,@nb3)(nb1, @nb1_1)(nb2,@nb2)(nb1,@nb1)◁ Env⌋,
    ⌈(@x,true)(@nb3,3025)(@nb1_1,55)(@nb2,35)(@nb1,25)◁ Mem⌉

2. Voici le texte Ada qui ne contient pas de variables. Le style est lourd; Ada comme tout autre langage impératif n’est pas adapté à ce style de programmation.

declare
 nb1 : constant integer := 25;– 1
 nb2 : constant integer := nb1 + 10; – 2
begin
  declare
– 3
   nb1:constant integer := nb2 + 20; – 4
  begin
   put(nb2);
   put(nb1);
    declare
– 5
     nb3:constant integer := nb1 * nb1; – 6
    begin
     put(nb3 * nb2);
    declare
– 7
      x:constant boolean := (nb1*nb2)>(nb2*nb2);
– 8
      y:constant boolean := x=true;
     begin
      null; –9
     end;
    end;
  end;
end;

–––––––––––––––––––-
         35         55     105875
–––––––––––––––––––-

Soit ⌊Env⌋ ⌈Mem⌉ l’état courant en début d’exécution de cette session. L’évolution de cet état aux points numérotés est détaillée ci-dessous.

 (a) ⌊(nb1,25)◁ Env⌋ ⌈Mem⌉
 (b) ⌊(nb2,35)(nb1,25)◁ Env⌋ ⌈Mem⌉
 (c) ⌊(nb2,35)(nb1,25)◁ Env⌋ ⌈Mem⌉
 (d) ⌊(nb1,55)(nb2,35)(nb1,25)◁ Env⌋ ⌈Mem⌉
 (e) ⌊(nb1,55)(nb2,35)(nb1,25)◁ Env⌋ ⌈Mem⌉
 (f) ⌊(nb3,3025)(nb1,55)(nb2,35)(nb1,25)◁ E nv⌋ ⌈Mem⌉
 (g) ⌊(nb3,3025)(nb1,55)(nb2,35)(nb1,25)◁ E nv⌋ ⌈Mem⌉
 (h) ⌊(x,true)(nb3,3025)(nb1,55)(nb2,35)(nb 1,25)◁ Env⌋ ⌈Mem⌉
 (i) ⌊(y,true)(x,true)(nb3,3025)(nb1,55)(nb2,35)(nb1,25)◁ Env⌋
    ⌈Mem⌉