Exercice 2 Induction : Hypoth`ese de r´ecurrence : soit n ≥ 2 et supposons que l’algorithme F se termine et retourne la valeur 3k −2k pour tout entier k tel que 0 ≤ k < n

Solutions de TD 1

Prof. Abdelmajid DarghamFaculte des Sciences, Oujda

Master Specialise Ingenierie Informatique

Universite Mohamed Premier

Septembre, 2012

Exercice 1

Considerons l’algorithme suivant :

Fonction F(n : Entier) : Entier;Variables

x , y : Entier;Debut

x := n;y := n;Tant Que (y 6= 0) Faire

x := x + 2;y := y − 1;

FinTQRetourner(x);

Fin

Prof. Abdelmajid Dargham Chapitre 1 : Introduction aux algorithmes

Exercice 1

Considerons l’algorithme suivant :Fonction F(n : Entier) : Entier;Variables

x , y : Entier;Debut

x := n;y := n;Tant Que (y 6= 0) Faire

x := x + 2;y := y − 1;

FinTQRetourner(x);

Fin


Exercice 1

1 Calculons F (0), F (1) et F (2) :F (0) = 0 : x et y sont initialisees a 0.

Comme y = 0, la boucle ne sera pas executee.On sort alors avec x = 0.

F (1) = 3 : x et y sont initialisees a 1.Comme y = 1, on execute la boucle : x = 2 + 1 = 3 ety = 1− 1 = 0.Maintenant, y = 0, on quitte la boucle et l’on retournex = 3.

F (2) = 6 : x et y sont initialisees a 2.Comme y = 2, on execute la boucle : x = 2 + 2 = 4 ety = 2− 1 = 1.Comme y = 1, on execute de nouveau la boucle :x = 4 + 2 = 6 et y = 1− 1 = 0.y = 0, donc on sort de la boucle et l’on retourne lavaleur x = 6.


Exercice 1

1 Calculons F (0), F (1) et F (2) :

F (0) = 0 : x et y sont initialisees a 0.Comme y = 0, la boucle ne sera pas executee.On sort alors avec x = 0.




Exercice 1






Exercice 1


Comme y = 0, la boucle ne sera pas executee.

On sort alors avec x = 0.F (1) = 3 : x et y sont initialisees a 1.

Comme y = 1, on execute la boucle : x = 2 + 1 = 3 ety = 1− 1 = 0.Maintenant, y = 0, on quitte la boucle et l’on retournex = 3.



Exercice 1






Exercice 1



F (1) = 3 : x et y sont initialisees a 1.

Comme y = 1, on execute la boucle : x = 2 + 1 = 3 ety = 1− 1 = 0.Maintenant, y = 0, on quitte la boucle et l’on retournex = 3.



Exercice 1



F (1) = 3 : x et y sont initialisees a 1.Comme y = 1, on execute la boucle : x = 2 + 1 = 3 ety = 1− 1 = 0.

Maintenant, y = 0, on quitte la boucle et l’on retournex = 3.



Exercice 1






Exercice 1




F (2) = 6 : x et y sont initialisees a 2.

Comme y = 2, on execute la boucle : x = 2 + 2 = 4 ety = 2− 1 = 1.Comme y = 1, on execute de nouveau la boucle :x = 4 + 2 = 6 et y = 1− 1 = 0.y = 0, donc on sort de la boucle et l’on retourne lavaleur x = 6.


Exercice 1




F (2) = 6 : x et y sont initialisees a 2.Comme y = 2, on execute la boucle : x = 2 + 2 = 4 ety = 2− 1 = 1.

Comme y = 1, on execute de nouveau la boucle :x = 4 + 2 = 6 et y = 1− 1 = 0.y = 0, donc on sort de la boucle et l’on retourne lavaleur x = 6.


Exercice 1




F (2) = 6 : x et y sont initialisees a 2.Comme y = 2, on execute la boucle : x = 2 + 2 = 4 ety = 2− 1 = 1.Comme y = 1, on execute de nouveau la boucle :x = 4 + 2 = 6 et y = 1− 1 = 0.

y = 0, donc on sort de la boucle et l’on retourne lavaleur x = 6.


Exercice 1






Exercice 1

2 Determinons ce que calcule la fonction F (n), pour toutentier n ≥ 0 :

Avant la boucle, x = n et y = n.La boucle decremente y de 1 et incremente x de 2.Il y aura alors n iterations.La valeur finale de x est donc : n + 2n = 3n.Par suite, F (n) = 3n, ∀n ≥ 0.


Exercice 1




Exercice 1


Avant la boucle, x = n et y = n.

La boucle decremente y de 1 et incremente x de 2.Il y aura alors n iterations.La valeur finale de x est donc : n + 2n = 3n.Par suite, F (n) = 3n, ∀n ≥ 0.


Exercice 1


Avant la boucle, x = n et y = n.La boucle decremente y de 1 et incremente x de 2.

Il y aura alors n iterations.La valeur finale de x est donc : n + 2n = 3n.Par suite, F (n) = 3n, ∀n ≥ 0.


Exercice 1


Avant la boucle, x = n et y = n.La boucle decremente y de 1 et incremente x de 2.Il y aura alors n iterations.

La valeur finale de x est donc : n + 2n = 3n.Par suite, F (n) = 3n, ∀n ≥ 0.


Exercice 1


Avant la boucle, x = n et y = n.La boucle decremente y de 1 et incremente x de 2.Il y aura alors n iterations.La valeur finale de x est donc : n + 2n = 3n.

Par suite, F (n) = 3n, ∀n ≥ 0.


Exercice 1




Exercice 1

3 Prouvons l’invariant de boucle : xj + 2yj = 3n, pour toutentier j ≥ 0 :Commencons par les faits :

x0 = n et y0 = n.xj+1 = xj + 2, ∀j ≥ 0.yj+1 = yj − 1, ∀j ≥ 0.

Preuve de l’invariant de boucle (Par recurrence sur j).

Base : pour j = 0, on a x0 + 2y0 = n + 2n = 3n. Lapropriete est verifiee pour j = 0.Induction : soit j ≥ 0 et supposons que xj + 2yj = 3n.Montrons que xj+1 + 2yj+1 = 3n. On a :xj+1 + 2yj+1 = xj + 2 + 2(yj − 1) = xj + 2yj = 3n.


Exercice 1

3 Prouvons l’invariant de boucle : xj + 2yj = 3n, pour toutentier j ≥ 0 :

Commencons par les faits :





Exercice 1


x0 = n et y0 = n.

xj+1 = xj + 2, ∀j ≥ 0.yj+1 = yj − 1, ∀j ≥ 0.




Exercice 1


x0 = n et y0 = n.xj+1 = xj + 2, ∀j ≥ 0.

yj+1 = yj − 1, ∀j ≥ 0.




Exercice 1






Exercice 1






Exercice 1




Base : pour j = 0, on a x0 + 2y0 = n + 2n = 3n. Lapropriete est verifiee pour j = 0.

Induction : soit j ≥ 0 et supposons que xj + 2yj = 3n.Montrons que xj+1 + 2yj+1 = 3n. On a :xj+1 + 2yj+1 = xj + 2 + 2(yj − 1) = xj + 2yj = 3n.


Exercice 1




Base : pour j = 0, on a x0 + 2y0 = n + 2n = 3n. Lapropriete est verifiee pour j = 0.Induction : soit j ≥ 0 et supposons que xj + 2yj = 3n.

Montrons que xj+1 + 2yj+1 = 3n. On a :xj+1 + 2yj+1 = xj + 2 + 2(yj − 1) = xj + 2yj = 3n.


Exercice 1




Base : pour j = 0, on a x0 + 2y0 = n + 2n = 3n. Lapropriete est verifiee pour j = 0.Induction : soit j ≥ 0 et supposons que xj + 2yj = 3n.Montrons que xj+1 + 2yj+1 = 3n.

On a :xj+1 + 2yj+1 = xj + 2 + 2(yj − 1) = xj + 2yj = 3n.


Exercice 1






Exercice 1

4 Donnons alors la preuve de l’algorithme F (n) :

L’algorithme F (n) se termine, car il effectue n iterationset chaque iteration se termine.Exploitation de l’invariant de boucle :

(yj)j≥0 est une suite arithmetique de premier termey0 = n et de raison r = −1.Donc, yj = y0 + r(j − 0) = n − j , ∀j ≥ 0.On en deduit que xj = 3n − 2yj = n + 2j .Comme il y a n iterations, la derniere valeur de j est n,et par suite, xn = n + 2n = 3n.Or, F (n) = xn, donc F (n) = 3n et l’algorithme estcorrect.


Exercice 1





Exercice 1


L’algorithme F (n) se termine, car il effectue n iterationset chaque iteration se termine.

Exploitation de l’invariant de boucle :



Exercice 1





Exercice 1



(yj)j≥0 est une suite arithmetique de premier termey0 = n et de raison r = −1.

Donc, yj = y0 + r(j − 0) = n − j , ∀j ≥ 0.On en deduit que xj = 3n − 2yj = n + 2j .Comme il y a n iterations, la derniere valeur de j est n,et par suite, xn = n + 2n = 3n.Or, F (n) = xn, donc F (n) = 3n et l’algorithme estcorrect.


Exercice 1



(yj)j≥0 est une suite arithmetique de premier termey0 = n et de raison r = −1.Donc, yj = y0 + r(j − 0) = n − j , ∀j ≥ 0.

On en deduit que xj = 3n − 2yj = n + 2j .Comme il y a n iterations, la derniere valeur de j est n,et par suite, xn = n + 2n = 3n.Or, F (n) = xn, donc F (n) = 3n et l’algorithme estcorrect.


Exercice 1



(yj)j≥0 est une suite arithmetique de premier termey0 = n et de raison r = −1.Donc, yj = y0 + r(j − 0) = n − j , ∀j ≥ 0.On en deduit que xj = 3n − 2yj = n + 2j .

Comme il y a n iterations, la derniere valeur de j est n,et par suite, xn = n + 2n = 3n.Or, F (n) = xn, donc F (n) = 3n et l’algorithme estcorrect.


Exercice 1



(yj)j≥0 est une suite arithmetique de premier termey0 = n et de raison r = −1.Donc, yj = y0 + r(j − 0) = n − j , ∀j ≥ 0.On en deduit que xj = 3n − 2yj = n + 2j .Comme il y a n iterations, la derniere valeur de j est n,et par suite, xn = n + 2n = 3n.

Or, F (n) = xn, donc F (n) = 3n et l’algorithme estcorrect.


Exercice 1





Exercice 2

On considere l’algorithme suivant :

Fonction F(n : Entier) : Entier;Debut

Si (n ≤ 1) AlorsRetourner(n);

SinonRetourner 5× F (n − 1)− 6× F (n − 2);

FinSiFin


Exercice 2

On considere l’algorithme suivant :Fonction F(n : Entier) : Entier;Debut

Si (n ≤ 1) AlorsRetourner(n);

SinonRetourner 5× F (n − 1)− 6× F (n − 2);

FinSiFin


Exercice 2

1 Prouvons que l’algorithme F (n) calcule 3n − 2n, pour toutn ≥ 0 :La preuve sera par recurrence (forte) sur n.

Base :

Si n = 0, l’algorithme F se termine et retourne la valeur0. Or, 30 − 20 = 1− 1 = 0.De meme, si n = 1, l’algorithme F se termine etretourne la valeur 1. Or, 31 − 21 = 3− 2 = 1.Donc, si n = 0 ou n = 1, l’algorithme F se termine et ilest correct.


Exercice 2

1 Prouvons que l’algorithme F (n) calcule 3n − 2n, pour toutn ≥ 0 :

La preuve sera par recurrence (forte) sur n.Base :



Exercice 2


Base :



Exercice 2


Base :



Exercice 2


Base :

Si n = 0, l’algorithme F se termine et retourne la valeur0.

Or, 30 − 20 = 1− 1 = 0.De meme, si n = 1, l’algorithme F se termine etretourne la valeur 1. Or, 31 − 21 = 3− 2 = 1.Donc, si n = 0 ou n = 1, l’algorithme F se termine et ilest correct.


Exercice 2


Base :

Si n = 0, l’algorithme F se termine et retourne la valeur0. Or, 30 − 20 = 1− 1 = 0.

De meme, si n = 1, l’algorithme F se termine etretourne la valeur 1. Or, 31 − 21 = 3− 2 = 1.Donc, si n = 0 ou n = 1, l’algorithme F se termine et ilest correct.


Exercice 2


Base :

Si n = 0, l’algorithme F se termine et retourne la valeur0. Or, 30 − 20 = 1− 1 = 0.De meme, si n = 1, l’algorithme F se termine etretourne la valeur 1.

Or, 31 − 21 = 3− 2 = 1.Donc, si n = 0 ou n = 1, l’algorithme F se termine et ilest correct.


Exercice 2


Base :

Si n = 0, l’algorithme F se termine et retourne la valeur0. Or, 30 − 20 = 1− 1 = 0.De meme, si n = 1, l’algorithme F se termine etretourne la valeur 1. Or, 31 − 21 = 3− 2 = 1.

Donc, si n = 0 ou n = 1, l’algorithme F se termine et ilest correct.


Exercice 2


Base :



Exercice 2

Induction :

Hypothese de recurrence : soit n ≥ 2 et supposonsque l’algorithme F se termine et retourne la valeur3k − 2k pour tout entier k tel que 0 ≤ k < n.Demontrons maintenant que l’algorithme F (n) setermine et retourne la valeur 3n − 2n.Puisque n ≥ 2, alors l’algorithme F (n) va engendrerdeux appels recursifs : F (n − 1) et F (n − 2).D’apres l’hypothese de recurrence, ces deux appels seterminent et retournent respectivement 3n−1 − 2n−1 et3n−2 − 2n−2.Donc, l’algorithme F (n) se termine et retourne la valeur5× (3n−1 − 2n−1)− 6× (3n−2 − 2n−2).


Exercice 2

Induction :



Exercice 2

Induction :

Hypothese de recurrence : soit n ≥ 2 et supposonsque l’algorithme F se termine et retourne la valeur3k − 2k pour tout entier k tel que 0 ≤ k < n.

Demontrons maintenant que l’algorithme F (n) setermine et retourne la valeur 3n − 2n.Puisque n ≥ 2, alors l’algorithme F (n) va engendrerdeux appels recursifs : F (n − 1) et F (n − 2).D’apres l’hypothese de recurrence, ces deux appels seterminent et retournent respectivement 3n−1 − 2n−1 et3n−2 − 2n−2.Donc, l’algorithme F (n) se termine et retourne la valeur5× (3n−1 − 2n−1)− 6× (3n−2 − 2n−2).


Exercice 2

Induction :

Hypothese de recurrence : soit n ≥ 2 et supposonsque l’algorithme F se termine et retourne la valeur3k − 2k pour tout entier k tel que 0 ≤ k < n.Demontrons maintenant que l’algorithme F (n) setermine et retourne la valeur 3n − 2n.

Puisque n ≥ 2, alors l’algorithme F (n) va engendrerdeux appels recursifs : F (n − 1) et F (n − 2).D’apres l’hypothese de recurrence, ces deux appels seterminent et retournent respectivement 3n−1 − 2n−1 et3n−2 − 2n−2.Donc, l’algorithme F (n) se termine et retourne la valeur5× (3n−1 − 2n−1)− 6× (3n−2 − 2n−2).


Exercice 2

Induction :

Hypothese de recurrence : soit n ≥ 2 et supposonsque l’algorithme F se termine et retourne la valeur3k − 2k pour tout entier k tel que 0 ≤ k < n.Demontrons maintenant que l’algorithme F (n) setermine et retourne la valeur 3n − 2n.Puisque n ≥ 2, alors l’algorithme F (n) va engendrerdeux appels recursifs : F (n − 1) et F (n − 2).

D’apres l’hypothese de recurrence, ces deux appels seterminent et retournent respectivement 3n−1 − 2n−1 et3n−2 − 2n−2.Donc, l’algorithme F (n) se termine et retourne la valeur5× (3n−1 − 2n−1)− 6× (3n−2 − 2n−2).


Exercice 2

Induction :

Hypothese de recurrence : soit n ≥ 2 et supposonsque l’algorithme F se termine et retourne la valeur3k − 2k pour tout entier k tel que 0 ≤ k < n.Demontrons maintenant que l’algorithme F (n) setermine et retourne la valeur 3n − 2n.Puisque n ≥ 2, alors l’algorithme F (n) va engendrerdeux appels recursifs : F (n − 1) et F (n − 2).D’apres l’hypothese de recurrence, ces deux appels seterminent et retournent respectivement 3n−1 − 2n−1 et3n−2 − 2n−2.

Donc, l’algorithme F (n) se termine et retourne la valeur5× (3n−1 − 2n−1)− 6× (3n−2 − 2n−2).


Exercice 2

Induction :



Exercice 2

Or, 5× (3n−1 − 2n−1)−×6(3n−2 − 2n−2) =(2 + 3)× (3n−1 − 2n−1)− (2× 3)× (3n−2 − 2n−2) =2× 3n−1 + 3n − 2n − 3× 2n−1 − 2× 3n−1 + 3× 2n−1 =3n − 2n.

Par suite, l’algorithme est correct.


Exercice 2

Or, 5× (3n−1 − 2n−1)−×6(3n−2 − 2n−2) =

(2 + 3)× (3n−1 − 2n−1)− (2× 3)× (3n−2 − 2n−2) =2× 3n−1 + 3n − 2n − 3× 2n−1 − 2× 3n−1 + 3× 2n−1 =3n − 2n.



Exercice 2

Or, 5× (3n−1 − 2n−1)−×6(3n−2 − 2n−2) =(2 + 3)× (3n−1 − 2n−1)− (2× 3)× (3n−2 − 2n−2) =

2× 3n−1 + 3n − 2n − 3× 2n−1 − 2× 3n−1 + 3× 2n−1 =3n − 2n.



Exercice 2

Or, 5× (3n−1 − 2n−1)−×6(3n−2 − 2n−2) =(2 + 3)× (3n−1 − 2n−1)− (2× 3)× (3n−2 − 2n−2) =2× 3n−1 + 3n − 2n − 3× 2n−1 − 2× 3n−1 + 3× 2n−1 =

3n − 2n.



Exercice 2




Exercice 2




Exercice 2

2 En utilisant un tableau, ecrivons un algorithme iteratifG (n) qui soit equivalent a F (n) :Fonction G(n : Entier) : Entier;Variables

t : liste d’entiers; i : Entier;Debut

t[0] := 0; t[1] := 1;i := 2;Tant Que (i ≤ n) Faire

t[i ] := 5× t[i − 1]− 6× t[i − 2];i := i + 1;

FinTQRetourner (t[n]);

Fin


Exercice 2

2 En utilisant un tableau, ecrivons un algorithme iteratifG (n) qui soit equivalent a F (n) :

Fonction G(n : Entier) : Entier;Variables



t[i ] := 5× t[i − 1]− 6× t[i − 2];i := i + 1;


Fin


Exercice 2

2 En utilisant un tableau, ecrivons un algorithme iteratifG (n) qui soit equivalent a F (n) :Fonction G(n : Entier) : Entier;

Variablest : liste d’entiers; i : Entier;

Debutt[0] := 0; t[1] := 1;i := 2;Tant Que (i ≤ n) Faire

t[i ] := 5× t[i − 1]− 6× t[i − 2];i := i + 1;


Fin


Exercice 2




t[i ] := 5× t[i − 1]− 6× t[i − 2];i := i + 1;


Fin


Exercice 2


t : liste d’entiers;

i : Entier;Debut


t[i ] := 5× t[i − 1]− 6× t[i − 2];i := i + 1;


Fin


Exercice 2


t : liste d’entiers; i : Entier;

Debutt[0] := 0; t[1] := 1;i := 2;Tant Que (i ≤ n) Faire

t[i ] := 5× t[i − 1]− 6× t[i − 2];i := i + 1;


Fin


Exercice 2




t[i ] := 5× t[i − 1]− 6× t[i − 2];i := i + 1;


Fin


Exercice 2



t[0] := 0;

t[1] := 1;i := 2;Tant Que (i ≤ n) Faire

t[i ] := 5× t[i − 1]− 6× t[i − 2];i := i + 1;


Fin


Exercice 2



t[0] := 0; t[1] := 1;

i := 2;Tant Que (i ≤ n) Faire

t[i ] := 5× t[i − 1]− 6× t[i − 2];i := i + 1;


Fin


Exercice 2



t[0] := 0; t[1] := 1;i := 2;

Tant Que (i ≤ n) Fairet[i ] := 5× t[i − 1]− 6× t[i − 2];i := i + 1;


Fin


Exercice 2




t[i ] := 5× t[i − 1]− 6× t[i − 2];i := i + 1;


Fin


Exercice 2




t[i ] := 5× t[i − 1]− 6× t[i − 2];

i := i + 1;FinTQRetourner (t[n]);

Fin


Exercice 2




t[i ] := 5× t[i − 1]− 6× t[i − 2];i := i + 1;


Fin


Exercice 2




t[i ] := 5× t[i − 1]− 6× t[i − 2];i := i + 1;

FinTQ

Retourner (t[n]);Fin


Exercice 2




t[i ] := 5× t[i − 1]− 6× t[i − 2];i := i + 1;


Fin


Exercice 2




t[i ] := 5× t[i − 1]− 6× t[i − 2];i := i + 1;


FinProf. Abdelmajid Dargham Chapitre 1 : Introduction aux algorithmes

Exercice 2

3 Donnons la preuve de l’algorithme G (n) :Si n = 0, l’algorithme G se termine et retournet[0] = 0 = 30 − 20.Si n = 1, l’algorithme G se termine et retournet[1] = 1 = 31 − 21.Donc, si n = 0 ou n = 1, l’algorithme G se termine et ilest correct.Soit n ≥ 2. La boucle Tant Que est effectueen − 2 + 1 = n − 1 fois, et son corps se termine.Par suite, l’algorithme se termine.

Les faits:i0 = 2t[ij−1] = 5× t[ij−1 − 1]− 6× t[ij−1 − 2], ∀j ≥ 1ij = ij−1 + 1, ∀j ≥ 1


Exercice 2

3 Donnons la preuve de l’algorithme G (n) :

Si n = 0, l’algorithme G se termine et retournet[0] = 0 = 30 − 20.Si n = 1, l’algorithme G se termine et retournet[1] = 1 = 31 − 21.Donc, si n = 0 ou n = 1, l’algorithme G se termine et ilest correct.Soit n ≥ 2. La boucle Tant Que est effectueen − 2 + 1 = n − 1 fois, et son corps se termine.Par suite, l’algorithme se termine.



Exercice 2

3 Donnons la preuve de l’algorithme G (n) :Si n = 0, l’algorithme G se termine et retournet[0] = 0 = 30 − 20.

Si n = 1, l’algorithme G se termine et retournet[1] = 1 = 31 − 21.Donc, si n = 0 ou n = 1, l’algorithme G se termine et ilest correct.Soit n ≥ 2. La boucle Tant Que est effectueen − 2 + 1 = n − 1 fois, et son corps se termine.Par suite, l’algorithme se termine.



Exercice 2

3 Donnons la preuve de l’algorithme G (n) :Si n = 0, l’algorithme G se termine et retournet[0] = 0 = 30 − 20.Si n = 1, l’algorithme G se termine et retournet[1] = 1 = 31 − 21.

Donc, si n = 0 ou n = 1, l’algorithme G se termine et ilest correct.Soit n ≥ 2. La boucle Tant Que est effectueen − 2 + 1 = n − 1 fois, et son corps se termine.Par suite, l’algorithme se termine.



Exercice 2

3 Donnons la preuve de l’algorithme G (n) :Si n = 0, l’algorithme G se termine et retournet[0] = 0 = 30 − 20.Si n = 1, l’algorithme G se termine et retournet[1] = 1 = 31 − 21.Donc, si n = 0 ou n = 1, l’algorithme G se termine et ilest correct.

Soit n ≥ 2. La boucle Tant Que est effectueen − 2 + 1 = n − 1 fois, et son corps se termine.Par suite, l’algorithme se termine.



Exercice 2

3 Donnons la preuve de l’algorithme G (n) :Si n = 0, l’algorithme G se termine et retournet[0] = 0 = 30 − 20.Si n = 1, l’algorithme G se termine et retournet[1] = 1 = 31 − 21.Donc, si n = 0 ou n = 1, l’algorithme G se termine et ilest correct.Soit n ≥ 2. La boucle Tant Que est effectueen − 2 + 1 = n − 1 fois, et son corps se termine.

Par suite, l’algorithme se termine.



Exercice 2




Exercice 2


Les faits:

i0 = 2t[ij−1] = 5× t[ij−1 − 1]− 6× t[ij−1 − 2], ∀j ≥ 1ij = ij−1 + 1, ∀j ≥ 1


Exercice 2


Les faits:i0 = 2

t[ij−1] = 5× t[ij−1 − 1]− 6× t[ij−1 − 2], ∀j ≥ 1ij = ij−1 + 1, ∀j ≥ 1


Exercice 2


Les faits:i0 = 2t[ij−1] = 5× t[ij−1 − 1]− 6× t[ij−1 − 2], ∀j ≥ 1

ij = ij−1 + 1, ∀j ≥ 1


Exercice 2




Exercice 2

Explication des faits :

Considerons la jeme iteration, avec j ≥ 1.

La variable i est impliquee dans deux instructions :

La premiere est : t[i ] := 5× t[i − 1]− 6× t[i − 2]. Danscette affectation, on doit utiliser la valeur de i avant lajeme iteration. C’est donc ij−1.La deuxieme est : i := i + 1. Cette affectation vachanger la valeur courante de i . La valeur de i a gaucheest ij et la valeur de i a droite est ij−1.

Par consequent :



Exercice 2





Par consequent :



Exercice 2





Par consequent :



Exercice 2




La premiere est : t[i ] := 5× t[i − 1]− 6× t[i − 2].

Danscette affectation, on doit utiliser la valeur de i avant lajeme iteration. C’est donc ij−1.La deuxieme est : i := i + 1. Cette affectation vachanger la valeur courante de i . La valeur de i a gaucheest ij et la valeur de i a droite est ij−1.

Par consequent :



Exercice 2




La premiere est : t[i ] := 5× t[i − 1]− 6× t[i − 2]. Danscette affectation, on doit utiliser la valeur de i avant lajeme iteration.

C’est donc ij−1.La deuxieme est : i := i + 1. Cette affectation vachanger la valeur courante de i . La valeur de i a gaucheest ij et la valeur de i a droite est ij−1.

Par consequent :



Exercice 2




La premiere est : t[i ] := 5× t[i − 1]− 6× t[i − 2]. Danscette affectation, on doit utiliser la valeur de i avant lajeme iteration. C’est donc ij−1.

La deuxieme est : i := i + 1. Cette affectation vachanger la valeur courante de i . La valeur de i a gaucheest ij et la valeur de i a droite est ij−1.

Par consequent :



Exercice 2




La premiere est : t[i ] := 5× t[i − 1]− 6× t[i − 2]. Danscette affectation, on doit utiliser la valeur de i avant lajeme iteration. C’est donc ij−1.La deuxieme est : i := i + 1.

Cette affectation vachanger la valeur courante de i . La valeur de i a gaucheest ij et la valeur de i a droite est ij−1.

Par consequent :



Exercice 2




La premiere est : t[i ] := 5× t[i − 1]− 6× t[i − 2]. Danscette affectation, on doit utiliser la valeur de i avant lajeme iteration. C’est donc ij−1.La deuxieme est : i := i + 1. Cette affectation vachanger la valeur courante de i .

La valeur de i a gaucheest ij et la valeur de i a droite est ij−1.

Par consequent :



Exercice 2





Par consequent :



Exercice 2





Par consequent :



Exercice 2





Par consequent :

t[ij−1] = 5× t[ij−1 − 1]− 6× t[ij−1 − 2], ∀j ≥ 1

ij = ij−1 + 1, ∀j ≥ 1


Exercice 2





Par consequent :



Exercice 2

On en deduit que :

ij = i0 + 1× (j − 0) = j + 2, ∀j ≥ 0.

Alors : ij−1 = (j − 1) + 2 = j + 1, ∀j ≥ 1.

t[j + 1] = 5× t[j ]− 6× t[j − 1], ∀j ≥ 1.

Invariant de boucle :

t[j ] = 3j − 2j ,∀j ≥ 0

Preuve par recurrence.

Base :

On a : t[0] = 0 = 30 − 20 et t[1] = 1 = 31 − 21.Donc, la propriete est vraie pour j = 0 et j = 1.


Exercice 2

On en deduit que :

ij = i0 + 1× (j − 0) = j + 2, ∀j ≥ 0.

Alors : ij−1 = (j − 1) + 2 = j + 1, ∀j ≥ 1.

t[j + 1] = 5× t[j ]− 6× t[j − 1], ∀j ≥ 1.


t[j ] = 3j − 2j ,∀j ≥ 0


Base :



Exercice 2

On en deduit que :

ij = i0 + 1× (j − 0) = j + 2, ∀j ≥ 0.

Alors : ij−1 = (j − 1) + 2 = j + 1, ∀j ≥ 1.

t[j + 1] = 5× t[j ]− 6× t[j − 1], ∀j ≥ 1.


t[j ] = 3j − 2j ,∀j ≥ 0


Base :



Exercice 2

On en deduit que :

ij = i0 + 1× (j − 0) = j + 2, ∀j ≥ 0.

Alors : ij−1 = (j − 1) + 2 = j + 1, ∀j ≥ 1.

t[j + 1] = 5× t[j ]− 6× t[j − 1], ∀j ≥ 1.


t[j ] = 3j − 2j ,∀j ≥ 0


Base :



Exercice 2

On en deduit que :

ij = i0 + 1× (j − 0) = j + 2, ∀j ≥ 0.

Alors : ij−1 = (j − 1) + 2 = j + 1, ∀j ≥ 1.

t[j + 1] = 5× t[j ]− 6× t[j − 1], ∀j ≥ 1.


t[j ] = 3j − 2j ,∀j ≥ 0


Base :



Exercice 2

On en deduit que :

ij = i0 + 1× (j − 0) = j + 2, ∀j ≥ 0.

Alors : ij−1 = (j − 1) + 2 = j + 1, ∀j ≥ 1.

t[j + 1] = 5× t[j ]− 6× t[j − 1], ∀j ≥ 1.


t[j ] = 3j − 2j ,∀j ≥ 0


Base :



Exercice 2

On en deduit que :

ij = i0 + 1× (j − 0) = j + 2, ∀j ≥ 0.

Alors : ij−1 = (j − 1) + 2 = j + 1, ∀j ≥ 1.

t[j + 1] = 5× t[j ]− 6× t[j − 1], ∀j ≥ 1.


t[j ] = 3j − 2j ,∀j ≥ 0


Base :



Exercice 2

On en deduit que :

ij = i0 + 1× (j − 0) = j + 2, ∀j ≥ 0.

Alors : ij−1 = (j − 1) + 2 = j + 1, ∀j ≥ 1.

t[j + 1] = 5× t[j ]− 6× t[j − 1], ∀j ≥ 1.


t[j ] = 3j − 2j ,∀j ≥ 0


Base :



Exercice 2

On en deduit que :

ij = i0 + 1× (j − 0) = j + 2, ∀j ≥ 0.

Alors : ij−1 = (j − 1) + 2 = j + 1, ∀j ≥ 1.

t[j + 1] = 5× t[j ]− 6× t[j − 1], ∀j ≥ 1.


t[j ] = 3j − 2j ,∀j ≥ 0


Base :



Exercice 2

On en deduit que :

ij = i0 + 1× (j − 0) = j + 2, ∀j ≥ 0.

Alors : ij−1 = (j − 1) + 2 = j + 1, ∀j ≥ 1.

t[j + 1] = 5× t[j ]− 6× t[j − 1], ∀j ≥ 1.


t[j ] = 3j − 2j ,∀j ≥ 0


Base :

On a : t[0] = 0 = 30 − 20 et t[1] = 1 = 31 − 21.

Donc, la propriete est vraie pour j = 0 et j = 1.


Exercice 2

On en deduit que :

ij = i0 + 1× (j − 0) = j + 2, ∀j ≥ 0.

Alors : ij−1 = (j − 1) + 2 = j + 1, ∀j ≥ 1.

t[j + 1] = 5× t[j ]− 6× t[j − 1], ∀j ≥ 1.


t[j ] = 3j − 2j ,∀j ≥ 0


Base :



Exercice 2

Induction :

Soit j ≥ 2 et supposons que t[k] = 3k − 2k pour toutentier k tel que 0 ≤ k < j .Demontrons que t[j ] = 3j − 2j .On a : t[j ] = t[(j − 1) + 1] avec j − 1 ≥ 1.D’apres les faits,t[j ] = t[(j − 1) + 1] = 5× t[j − 1]− 6× t[j − 2].D’apres l’hypothese de recurrence, on a :t[j ] = 5× (3j−1 − 2j−1)− 6× (3j−2 − 2j−2) = 3j − 2j .


Exercice 2

Induction :



Exercice 2

Induction :

Soit j ≥ 2 et supposons que t[k] = 3k − 2k pour toutentier k tel que 0 ≤ k < j .

Demontrons que t[j ] = 3j − 2j .On a : t[j ] = t[(j − 1) + 1] avec j − 1 ≥ 1.D’apres les faits,t[j ] = t[(j − 1) + 1] = 5× t[j − 1]− 6× t[j − 2].D’apres l’hypothese de recurrence, on a :t[j ] = 5× (3j−1 − 2j−1)− 6× (3j−2 − 2j−2) = 3j − 2j .


Exercice 2

Induction :

Soit j ≥ 2 et supposons que t[k] = 3k − 2k pour toutentier k tel que 0 ≤ k < j .Demontrons que t[j ] = 3j − 2j .

On a : t[j ] = t[(j − 1) + 1] avec j − 1 ≥ 1.D’apres les faits,t[j ] = t[(j − 1) + 1] = 5× t[j − 1]− 6× t[j − 2].D’apres l’hypothese de recurrence, on a :t[j ] = 5× (3j−1 − 2j−1)− 6× (3j−2 − 2j−2) = 3j − 2j .


Exercice 2

Induction :

Soit j ≥ 2 et supposons que t[k] = 3k − 2k pour toutentier k tel que 0 ≤ k < j .Demontrons que t[j ] = 3j − 2j .On a : t[j ] = t[(j − 1) + 1] avec j − 1 ≥ 1.

D’apres les faits,t[j ] = t[(j − 1) + 1] = 5× t[j − 1]− 6× t[j − 2].D’apres l’hypothese de recurrence, on a :t[j ] = 5× (3j−1 − 2j−1)− 6× (3j−2 − 2j−2) = 3j − 2j .


Exercice 2

Induction :

Soit j ≥ 2 et supposons que t[k] = 3k − 2k pour toutentier k tel que 0 ≤ k < j .Demontrons que t[j ] = 3j − 2j .On a : t[j ] = t[(j − 1) + 1] avec j − 1 ≥ 1.D’apres les faits,t[j ] = t[(j − 1) + 1] = 5× t[j − 1]− 6× t[j − 2].

D’apres l’hypothese de recurrence, on a :t[j ] = 5× (3j−1 − 2j−1)− 6× (3j−2 − 2j−2) = 3j − 2j .


Exercice 2

Induction :



Exercice 2

Exploitation de l’invariant de boucle

Il y a (n − 1) iterations.

Donc, la derniere valeur de j est (n − 1).

On en deduit alors que : t[(n − 1) + 1] = t[n] = 3n − 2n.

L’algorithme G (n) retourne la valeur t[n] = 3n − 2n.

Conclusion : l’algorithme G (n) se termine et il est correct.


Exercice 2








Exercice 2








Exercice 2








Exercice 2








Exercice 2








Exercice 2

4 Sans utiliser aucun tableau, ecrivons un algorithme iteratifH(n) qui soit equivalent a F (n) :Fonction H(n : Entier) : Entier;Variablesi , a, b, c : Entier;Debut

Si (n ≤ 1) Alors Retourner (n) FinSia := 0; b := 1; i := 2;Tant Que (i ≤ n) Faire

c := 5× b − 6× a;a := b; b := c ; i := i + 1;

FinTQRetourner (b);

Fin


Exercice 2

4 Sans utiliser aucun tableau, ecrivons un algorithme iteratifH(n) qui soit equivalent a F (n) :

Fonction H(n : Entier) : Entier;Variablesi , a, b, c : Entier;Debut


c := 5× b − 6× a;a := b; b := c ; i := i + 1;

FinTQRetourner (b);

Fin


Exercice 2

4 Sans utiliser aucun tableau, ecrivons un algorithme iteratifH(n) qui soit equivalent a F (n) :Fonction H(n : Entier) : Entier;

Variablesi , a, b, c : Entier;Debut


c := 5× b − 6× a;a := b; b := c ; i := i + 1;

FinTQRetourner (b);

Fin


Exercice 2

4 Sans utiliser aucun tableau, ecrivons un algorithme iteratifH(n) qui soit equivalent a F (n) :Fonction H(n : Entier) : Entier;Variables

i , a, b, c : Entier;Debut


c := 5× b − 6× a;a := b; b := c ; i := i + 1;

FinTQRetourner (b);

Fin


Exercice 2

4 Sans utiliser aucun tableau, ecrivons un algorithme iteratifH(n) qui soit equivalent a F (n) :Fonction H(n : Entier) : Entier;Variablesi , a, b, c : Entier;

DebutSi (n ≤ 1) Alors Retourner (n) FinSia := 0; b := 1; i := 2;Tant Que (i ≤ n) Faire

c := 5× b − 6× a;a := b; b := c ; i := i + 1;

FinTQRetourner (b);

Fin


Exercice 2



c := 5× b − 6× a;a := b; b := c ; i := i + 1;

FinTQRetourner (b);

Fin


Exercice 2


Si (n ≤ 1) Alors Retourner (n) FinSi

a := 0; b := 1; i := 2;Tant Que (i ≤ n) Faire

c := 5× b − 6× a;a := b; b := c ; i := i + 1;

FinTQRetourner (b);

Fin


Exercice 2


Si (n ≤ 1) Alors Retourner (n) FinSia := 0;

b := 1; i := 2;Tant Que (i ≤ n) Faire

c := 5× b − 6× a;a := b; b := c ; i := i + 1;

FinTQRetourner (b);

Fin


Exercice 2


Si (n ≤ 1) Alors Retourner (n) FinSia := 0; b := 1;

i := 2;Tant Que (i ≤ n) Faire

c := 5× b − 6× a;a := b; b := c ; i := i + 1;

FinTQRetourner (b);

Fin


Exercice 2


Si (n ≤ 1) Alors Retourner (n) FinSia := 0; b := 1; i := 2;

Tant Que (i ≤ n) Fairec := 5× b − 6× a;a := b; b := c ; i := i + 1;

FinTQRetourner (b);

Fin


Exercice 2



c := 5× b − 6× a;a := b; b := c ; i := i + 1;

FinTQRetourner (b);

Fin


Exercice 2



c := 5× b − 6× a;

a := b; b := c ; i := i + 1;FinTQRetourner (b);

Fin


Exercice 2



c := 5× b − 6× a;a := b;

b := c ; i := i + 1;FinTQRetourner (b);

Fin


Exercice 2



c := 5× b − 6× a;a := b; b := c ;

i := i + 1;FinTQRetourner (b);

Fin


Exercice 2



c := 5× b − 6× a;a := b; b := c ; i := i + 1;

FinTQRetourner (b);

Fin


Exercice 2



c := 5× b − 6× a;a := b; b := c ; i := i + 1;

FinTQ

Retourner (b);Fin


Exercice 2



c := 5× b − 6× a;a := b; b := c ; i := i + 1;

FinTQRetourner (b);

Fin


Exercice 2



c := 5× b − 6× a;a := b; b := c ; i := i + 1;

FinTQRetourner (b);

FinProf. Abdelmajid Dargham Chapitre 1 : Introduction aux algorithmes

Exercice 2

5 Donnons la preuve de l’algorithme H(n) :

Si n = 0, l’algorithme G se termine et retournen = 0 = 30 − 20.Si n = 1, l’algorithme G se termine et retournen = 1 = 31 − 21.Donc, si n = 0 ou n = 1, l’algorithme G se termine et ilest correct.Soit n ≥ 2. La boucle Tant Que sera effectueen − 2 + 1 = n − 1 fois, et son corps se termine.Par suite, l’algorithme se termine.


Exercice 2




Exercice 2


Si n = 0, l’algorithme G se termine et retournen = 0 = 30 − 20.

Si n = 1, l’algorithme G se termine et retournen = 1 = 31 − 21.Donc, si n = 0 ou n = 1, l’algorithme G se termine et ilest correct.Soit n ≥ 2. La boucle Tant Que sera effectueen − 2 + 1 = n − 1 fois, et son corps se termine.Par suite, l’algorithme se termine.


Exercice 2


Si n = 0, l’algorithme G se termine et retournen = 0 = 30 − 20.Si n = 1, l’algorithme G se termine et retournen = 1 = 31 − 21.

Donc, si n = 0 ou n = 1, l’algorithme G se termine et ilest correct.Soit n ≥ 2. La boucle Tant Que sera effectueen − 2 + 1 = n − 1 fois, et son corps se termine.Par suite, l’algorithme se termine.


Exercice 2


Si n = 0, l’algorithme G se termine et retournen = 0 = 30 − 20.Si n = 1, l’algorithme G se termine et retournen = 1 = 31 − 21.Donc, si n = 0 ou n = 1, l’algorithme G se termine et ilest correct.

Soit n ≥ 2. La boucle Tant Que sera effectueen − 2 + 1 = n − 1 fois, et son corps se termine.Par suite, l’algorithme se termine.


Exercice 2


Si n = 0, l’algorithme G se termine et retournen = 0 = 30 − 20.Si n = 1, l’algorithme G se termine et retournen = 1 = 31 − 21.Donc, si n = 0 ou n = 1, l’algorithme G se termine et ilest correct.Soit n ≥ 2. La boucle Tant Que sera effectueen − 2 + 1 = n − 1 fois, et son corps se termine.

Par suite, l’algorithme se termine.


Exercice 2




Exercice 2

Les faits:

a0 = 0;

b0 = 1;

i0 = 2;

c0 n’est pas defini.

cj = 5× bj−1 − 6× aj−1, ∀j ≥ 1

aj = bj−1, ∀j ≥ 1

bj = cj = 5× bj−1 − 6× aj−1, ∀j ≥ 1

ij = ij−1 + 1, ∀j ≥ 1


Exercice 2

Les faits:

a0 = 0;

b0 = 1;

i0 = 2;


cj = 5× bj−1 − 6× aj−1, ∀j ≥ 1

aj = bj−1, ∀j ≥ 1

bj = cj = 5× bj−1 − 6× aj−1, ∀j ≥ 1

ij = ij−1 + 1, ∀j ≥ 1


Exercice 2

Les faits:

a0 = 0;

b0 = 1;

i0 = 2;


cj = 5× bj−1 − 6× aj−1, ∀j ≥ 1

aj = bj−1, ∀j ≥ 1

bj = cj = 5× bj−1 − 6× aj−1, ∀j ≥ 1

ij = ij−1 + 1, ∀j ≥ 1


Exercice 2

Les faits:

a0 = 0;

b0 = 1;

i0 = 2;


cj = 5× bj−1 − 6× aj−1, ∀j ≥ 1

aj = bj−1, ∀j ≥ 1

bj = cj = 5× bj−1 − 6× aj−1, ∀j ≥ 1

ij = ij−1 + 1, ∀j ≥ 1


Exercice 2

Les faits:

a0 = 0;

b0 = 1;

i0 = 2;


cj = 5× bj−1 − 6× aj−1, ∀j ≥ 1

aj = bj−1, ∀j ≥ 1

bj = cj = 5× bj−1 − 6× aj−1, ∀j ≥ 1

ij = ij−1 + 1, ∀j ≥ 1


Exercice 2

Les faits:

a0 = 0;

b0 = 1;

i0 = 2;


cj = 5× bj−1 − 6× aj−1, ∀j ≥ 1

aj = bj−1, ∀j ≥ 1

bj = cj = 5× bj−1 − 6× aj−1, ∀j ≥ 1

ij = ij−1 + 1, ∀j ≥ 1


Exercice 2

Les faits:

a0 = 0;

b0 = 1;

i0 = 2;


cj = 5× bj−1 − 6× aj−1, ∀j ≥ 1

aj = bj−1, ∀j ≥ 1

bj = cj = 5× bj−1 − 6× aj−1, ∀j ≥ 1

ij = ij−1 + 1, ∀j ≥ 1


Exercice 2

Les faits:

a0 = 0;

b0 = 1;

i0 = 2;


cj = 5× bj−1 − 6× aj−1, ∀j ≥ 1

aj = bj−1, ∀j ≥ 1

bj = cj = 5× bj−1 − 6× aj−1, ∀j ≥ 1

ij = ij−1 + 1, ∀j ≥ 1


Exercice 2

Les faits:

a0 = 0;

b0 = 1;

i0 = 2;


cj = 5× bj−1 − 6× aj−1, ∀j ≥ 1

aj = bj−1, ∀j ≥ 1

bj = cj = 5× bj−1 − 6× aj−1, ∀j ≥ 1

ij = ij−1 + 1, ∀j ≥ 1


Exercice 2

On en deduit que :

ij = j + 2, ∀j ≥ 0bj = 5× bj−1 − 6× aj−1, ∀j ≥ 1.


bj = 3j+1 − 2j+1,∀j ≥ 0.

Preuve par recurrence sur j (page suivante).


Exercice 2

On en deduit que :

ij = j + 2, ∀j ≥ 0bj = 5× bj−1 − 6× aj−1, ∀j ≥ 1.


bj = 3j+1 − 2j+1,∀j ≥ 0.



Exercice 2

On en deduit que :

ij = j + 2, ∀j ≥ 0

bj = 5× bj−1 − 6× aj−1, ∀j ≥ 1.


bj = 3j+1 − 2j+1,∀j ≥ 0.



Exercice 2

On en deduit que :

ij = j + 2, ∀j ≥ 0bj = 5× bj−1 − 6× aj−1, ∀j ≥ 1.


bj = 3j+1 − 2j+1,∀j ≥ 0.



Exercice 2

On en deduit que :

ij = j + 2, ∀j ≥ 0bj = 5× bj−1 − 6× aj−1, ∀j ≥ 1.


bj = 3j+1 − 2j+1,∀j ≥ 0.



Exercice 2

On en deduit que :

ij = j + 2, ∀j ≥ 0bj = 5× bj−1 − 6× aj−1, ∀j ≥ 1.


bj = 3j+1 − 2j+1,∀j ≥ 0.



Exercice 2

On en deduit que :

ij = j + 2, ∀j ≥ 0bj = 5× bj−1 − 6× aj−1, ∀j ≥ 1.


bj = 3j+1 − 2j+1,∀j ≥ 0.



Exercice 2

Base

Pour j = 0, on a : b0 = 1 = 3− 2 = 30+1 − 20+1.Pour j = 1, on a : b1 = c1 = 5× b0 − 6× a0

= 5× 1− 6× 0 = 5 = 32 − 22 = 31+1 − 21+1.Donc, la propriete est vraie pour j = 0 et j = 1.


Exercice 2

Base




Exercice 2

Base

Pour j = 0, on a : b0 = 1 = 3− 2 = 30+1 − 20+1.

Pour j = 1, on a : b1 = c1 = 5× b0 − 6× a0



Exercice 2

Base


= 5× 1− 6× 0 = 5 = 32 − 22 = 31+1 − 21+1.

Donc, la propriete est vraie pour j = 0 et j = 1.


Exercice 2

Base




Exercice 2

Induction

Hypothese de recurrence : soit j ≥ 2 et supposons quebk = 3k+1 − 2k+1, pour tout entier k tel que 0 ≤ k < j .Demontrons que bj = 3j+1 − 2j+1.D’apres les faits, on a :bj = 5× bj−1 − 6× aj−1 = 5× bj−1 − 6× bj−2.D’apres l’hypothese de recurrence, on a :bj = 5× (3j − 2j)− 6× (3j−1 − 2j−1) = 3j+1 − 2j+1.


Exercice 2

Induction



Exercice 2

Induction

Hypothese de recurrence : soit j ≥ 2 et supposons quebk = 3k+1 − 2k+1, pour tout entier k tel que 0 ≤ k < j .

Demontrons que bj = 3j+1 − 2j+1.D’apres les faits, on a :bj = 5× bj−1 − 6× aj−1 = 5× bj−1 − 6× bj−2.D’apres l’hypothese de recurrence, on a :bj = 5× (3j − 2j)− 6× (3j−1 − 2j−1) = 3j+1 − 2j+1.


Exercice 2

Induction

Hypothese de recurrence : soit j ≥ 2 et supposons quebk = 3k+1 − 2k+1, pour tout entier k tel que 0 ≤ k < j .Demontrons que bj = 3j+1 − 2j+1.

D’apres les faits, on a :bj = 5× bj−1 − 6× aj−1 = 5× bj−1 − 6× bj−2.D’apres l’hypothese de recurrence, on a :bj = 5× (3j − 2j)− 6× (3j−1 − 2j−1) = 3j+1 − 2j+1.


Exercice 2

Induction

Hypothese de recurrence : soit j ≥ 2 et supposons quebk = 3k+1 − 2k+1, pour tout entier k tel que 0 ≤ k < j .Demontrons que bj = 3j+1 − 2j+1.D’apres les faits, on a :bj = 5× bj−1 − 6× aj−1 = 5× bj−1 − 6× bj−2.

D’apres l’hypothese de recurrence, on a :bj = 5× (3j − 2j)− 6× (3j−1 − 2j−1) = 3j+1 − 2j+1.


Exercice 2

Induction



Exercice 2


Il y a (n − 1) iterations.Donc, la derniere valeur de j est (n − 1).On en deduit que : bn−1 = 3n − 2n.Par suite, l’algorithme H(n) retourne la valeurbn−1 = 3n − 2n, il est donc correct.


Exercice 2




Exercice 2



Donc, la derniere valeur de j est (n − 1).On en deduit que : bn−1 = 3n − 2n.Par suite, l’algorithme H(n) retourne la valeurbn−1 = 3n − 2n, il est donc correct.


Exercice 2


Il y a (n − 1) iterations.Donc, la derniere valeur de j est (n − 1).

On en deduit que : bn−1 = 3n − 2n.Par suite, l’algorithme H(n) retourne la valeurbn−1 = 3n − 2n, il est donc correct.


Exercice 2


Il y a (n − 1) iterations.Donc, la derniere valeur de j est (n − 1).On en deduit que : bn−1 = 3n − 2n.

Par suite, l’algorithme H(n) retourne la valeurbn−1 = 3n − 2n, il est donc correct.


Exercice 2




Exercice 3

Soient a et b deux entiers positifs.

On veut calculer le quotient de a par b en n’effectuantque des soustractions.

1 Etablissons un algorithme iteratif qui permet de resoudrece probleme :


Exercice 3





Exercice 3





Exercice 3





Exercice 3

Algorithme iteratif :

Fonction Quotient(a, b : Entier) : Entier;Variables

q : Entier;Debut

q := 0;Tant Que (a ≥ b) Faire

a := a − b;q := q + 1;

FinTQRetourner (q);

Fin


Exercice 3

Algorithme iteratif :Fonction Quotient(a, b : Entier) : Entier;

Variablesq : Entier;

Debutq := 0;Tant Que (a ≥ b) Faire

a := a − b;q := q + 1;

FinTQRetourner (q);

Fin


Exercice 3

Algorithme iteratif :Fonction Quotient(a, b : Entier) : Entier;Variables

q : Entier;Debut


a := a − b;q := q + 1;

FinTQRetourner (q);

Fin


Exercice 3


q : Entier;

Debutq := 0;Tant Que (a ≥ b) Faire

a := a − b;q := q + 1;

FinTQRetourner (q);

Fin


Exercice 3


q : Entier;Debut


a := a − b;q := q + 1;

FinTQRetourner (q);

Fin


Exercice 3


q : Entier;Debut

q := 0;

Tant Que (a ≥ b) Fairea := a − b;q := q + 1;

FinTQRetourner (q);

Fin


Exercice 3


q : Entier;Debut


a := a − b;q := q + 1;

FinTQRetourner (q);

Fin


Exercice 3


q : Entier;Debut


a := a − b;

q := q + 1;FinTQRetourner (q);

Fin


Exercice 3


q : Entier;Debut


a := a − b;q := q + 1;

FinTQRetourner (q);

Fin


Exercice 3


q : Entier;Debut


a := a − b;q := q + 1;

FinTQ

Retourner (q);Fin


Exercice 3


q : Entier;Debut


a := a − b;q := q + 1;

FinTQRetourner (q);

Fin


Exercice 3


q : Entier;Debut


a := a − b;q := q + 1;

FinTQRetourner (q);

Fin


Exercice 3

2 Donnons la preuve de l’algorithme :

Terminaison :

Si a < b, la boucle ”Tant Que” n’est pas executee.L’algorithme se termine.Si a ≥ b, la boucle sera executee au moins une fois.Comme la valeur de a se decremente de b unites a la finde chaque iteration, la condition a ≥ b deviendra faussea un certain moment. L’algorithme se terminera alors.


Exercice 3


Terminaison :



Exercice 3


Terminaison :



Exercice 3


Terminaison :

Si a < b, la boucle ”Tant Que” n’est pas executee.L’algorithme se termine.

Si a ≥ b, la boucle sera executee au moins une fois.Comme la valeur de a se decremente de b unites a la finde chaque iteration, la condition a ≥ b deviendra faussea un certain moment. L’algorithme se terminera alors.


Exercice 3


Terminaison :



Exercice 3

Correction :

Si a < b, l’algorithme retourne la valeur 0 = a/b.Supposons que a ≥ b. On a les faits suivants :

1 a0 = a.2 q0 = 0.3 aj+1 = aj − b; ∀j ≥ 04 qj+1 = qj + 1; ∀j ≥ 0

On en deduit alors que :

1 qj = j , ∀j ≥ 0.2 aj = a− jb, ∀j ≥ 0.


Exercice 3

Correction :


1 a0 = a.2 q0 = 0.3 aj+1 = aj − b; ∀j ≥ 04 qj+1 = qj + 1; ∀j ≥ 0


1 qj = j , ∀j ≥ 0.2 aj = a− jb, ∀j ≥ 0.


Exercice 3

Correction :

Si a < b, l’algorithme retourne la valeur 0 = a/b.

Supposons que a ≥ b. On a les faits suivants :

1 a0 = a.2 q0 = 0.3 aj+1 = aj − b; ∀j ≥ 04 qj+1 = qj + 1; ∀j ≥ 0


1 qj = j , ∀j ≥ 0.2 aj = a− jb, ∀j ≥ 0.


Exercice 3

Correction :


1 a0 = a.2 q0 = 0.3 aj+1 = aj − b; ∀j ≥ 04 qj+1 = qj + 1; ∀j ≥ 0


1 qj = j , ∀j ≥ 0.2 aj = a− jb, ∀j ≥ 0.


Exercice 3

Correction :


1 a0 = a.

2 q0 = 0.3 aj+1 = aj − b; ∀j ≥ 04 qj+1 = qj + 1; ∀j ≥ 0


1 qj = j , ∀j ≥ 0.2 aj = a− jb, ∀j ≥ 0.


Exercice 3

Correction :


1 a0 = a.2 q0 = 0.

3 aj+1 = aj − b; ∀j ≥ 04 qj+1 = qj + 1; ∀j ≥ 0


1 qj = j , ∀j ≥ 0.2 aj = a− jb, ∀j ≥ 0.


Exercice 3

Correction :


1 a0 = a.2 q0 = 0.3 aj+1 = aj − b; ∀j ≥ 0

4 qj+1 = qj + 1; ∀j ≥ 0


1 qj = j , ∀j ≥ 0.2 aj = a− jb, ∀j ≥ 0.


Exercice 3

Correction :


1 a0 = a.2 q0 = 0.3 aj+1 = aj − b; ∀j ≥ 04 qj+1 = qj + 1; ∀j ≥ 0


1 qj = j , ∀j ≥ 0.2 aj = a− jb, ∀j ≥ 0.


Exercice 3

Correction :


1 a0 = a.2 q0 = 0.3 aj+1 = aj − b; ∀j ≥ 04 qj+1 = qj + 1; ∀j ≥ 0


1 qj = j , ∀j ≥ 0.2 aj = a− jb, ∀j ≥ 0.


Exercice 3

Correction :


1 a0 = a.2 q0 = 0.3 aj+1 = aj − b; ∀j ≥ 04 qj+1 = qj + 1; ∀j ≥ 0


1 qj = j , ∀j ≥ 0.

2 aj = a− jb, ∀j ≥ 0.


Exercice 3

Correction :


1 a0 = a.2 q0 = 0.3 aj+1 = aj − b; ∀j ≥ 04 qj+1 = qj + 1; ∀j ≥ 0


1 qj = j , ∀j ≥ 0.2 aj = a− jb, ∀j ≥ 0.


Exercice 3

Soit k ≥ 1, le nombre d’iterations de la boucle ”TantQue”.

D’apres les faits : ak = a − bk et qk = k .

Posons r = a − bk .

Il est clair que a = bk + r et que 0 ≤ r < b.

Par suite, k est le quotient de a par b (theoreme de ladivision euclidienne).

L’algorithme fournira la valeur qk = k = a/b.

Il est donc correct.

3 Etablissons un algorithme recursif qui permet de resoudrece probleme :


Exercice 3










Exercice 3










Exercice 3










Exercice 3










Exercice 3










Exercice 3










Exercice 3










Exercice 3










Exercice 3

Algorithme recursif :

Fonction Quotient(a, b : Entier) : Entier;Debut

Si (a < b) AlorsRetourner (0);

SinonRetourner (Quotient(a − b, b) + 1);

FinSi;Fin


Exercice 3

Algorithme recursif :Fonction Quotient(a, b : Entier) : Entier;

DebutSi (a < b) Alors

Retourner (0);Sinon

Retourner (Quotient(a − b, b) + 1);FinSi;

Fin


Exercice 3

Algorithme recursif :Fonction Quotient(a, b : Entier) : Entier;Debut



FinSi;Fin


Exercice 3


Si (a < b) Alors

Retourner (0);Sinon


Fin


Exercice 3




FinSi;Fin


Exercice 3



Sinon


Fin


Exercice 3




FinSi;Fin


Exercice 3




FinSi;

Fin


Exercice 3




FinSi;Fin


Exercice 3


Preuve par recurrence (forte).

Base :

Si a < b, l’algorithme se termine et retourne 0 qui est lequotient de a par b.Donc, l’algorithme se termine et il est correct.

Induction :

Soit a ≥ b et supposons que l’algorithme se termine et ilest correct pour tout entier k avec 0 ≤ k < a.Montrons le pour l’entier a.


Exercice 3



Base :


Induction :



Exercice 3



Base :


Induction :



Exercice 3



Base :


Induction :



Exercice 3



Base :

Si a < b, l’algorithme se termine et retourne 0 qui est lequotient de a par b.

Donc, l’algorithme se termine et il est correct.

Induction :



Exercice 3



Base :


Induction :



Exercice 3



Base :


Induction :



Exercice 3



Base :


Induction :

Soit a ≥ b et supposons que l’algorithme se termine et ilest correct pour tout entier k avec 0 ≤ k < a.

Montrons le pour l’entier a.


Exercice 3



Base :


Induction :



Exercice 3

Comme a ≥ b, l’appel Quotient(a, b) va engendrer unappel recursif avec les parametres (a − b) et b.

Puisque 0 ≤ a − b < a, l’appel Quotient(a − b, b) setermine et renvoie la valeur q qui est le quotient de(a − b) par a.

Par consequent, l’appel Quotient(a, b) se termine etrenvoie la valeur q + 1.

On a : a − b = bq + r , avec 0 ≤ r < b.

Donc, a = b(q + 1) + r , avec 0 ≤ r < b.

D’apres le theoreme de la division euclidienne, (q + 1) estle quotient de a par b.

Cela montre que l’algorithme Quotient(a, b) se termine etil est correct.


Exercice 3




On a : a − b = bq + r , avec 0 ≤ r < b.

Donc, a = b(q + 1) + r , avec 0 ≤ r < b.




Exercice 3




On a : a − b = bq + r , avec 0 ≤ r < b.

Donc, a = b(q + 1) + r , avec 0 ≤ r < b.




Exercice 3




On a : a − b = bq + r , avec 0 ≤ r < b.

Donc, a = b(q + 1) + r , avec 0 ≤ r < b.




Exercice 3




On a : a − b = bq + r , avec 0 ≤ r < b.

Donc, a = b(q + 1) + r , avec 0 ≤ r < b.




Exercice 3




On a : a − b = bq + r , avec 0 ≤ r < b.

Donc, a = b(q + 1) + r , avec 0 ≤ r < b.




Exercice 3




On a : a − b = bq + r , avec 0 ≤ r < b.

Donc, a = b(q + 1) + r , avec 0 ≤ r < b.




Exercice 3




On a : a − b = bq + r , avec 0 ≤ r < b.

Donc, a = b(q + 1) + r , avec 0 ≤ r < b.




Documents

Exercice 2 Induction : Hypoth`ese de r´ecurrence : soit n ≥ 2 et supposons que l’algorithme F se termine et retourne la valeur 3k −2k pour tout entier k tel que 0 ≤ k < n