sujet Test 1 : algorithmie et preuve

Rendu

Type de rendu

Rendu sur feuille.

Éléments de notation

1. Écriture sous la forme d'un pseudo-code correct
2. Lorsque l'on vous demande de donner un algorithme, il faudra toujours prouver :
   • sa finitude
   • son exactitude

Ne tartinez pas des pages et des pages de démonstration. Allez directement au fait et si c'est évident, dites le.

Sujet

Dans la suite de ce test, on supposera connu l'algorithme suivant qui rend le successeur d'un entier positif :

algorithme succ(n: entier) → entier:
    rendre n + 1

Question 1

On considère le programme suivant définis pour tous a et b entiers positifs :

programme somme(a: entier, b: entier) → entier:
    i ← 0
    j ← a
    tant que i ≠ b:
        i ← succ(i)
        j ← succ(j)
    rendre j

1.1

Montrez que l'expression a + i = j est un invariant de boucle du programme somme.

1.2

Montrez que somme est un algorithme et utilisez l'invariant de la question 1.1 pour prouver que somme(a, b) = a + b pour tous a et b entiers positifs.

Question 2

En utilisant uniquement somme, donnez un algorithme itératif permettant de calculer le produit de deux entiers passés en paramètre. Sa signature doit être :

produit(a: entier, b: entier) → entier

Et on doit avoir l'égalité produit(a, b) = a * b pour tous a et b entiers positifs ou nuls.

Question 3

En utilisant uniquement succ comme opération arithmétique donnez un algorithme permettant de calculer le prédécesseur d'un entier positif passé en paramètre. Sa signature doit être :

pred(a: entier) → entier

Et on doit avoir pour tout a entier positif ou nul :

• pred(a) = a - 1 si a > 0
• pred(0) = 0

Question 4

4.1

En utilisant succ et pred comme opérations arithmétiques, donnez un algorithme récursif permettant de calculer la somme de deux entiers passés en paramètre. Sa signature doit être :

somme_rec(a: entier, b: entier) → entier

Et on doit avoir l'égalité somme_rec(a, b) = a + b pour tous a et b entiers positifs ou nuls.

4.2

En utilisant uniquement somme_rec et pred, donnez un algorithme récursif permettant le produit de deux entiers passés en paramètre. Sa signature doit être :

produit_rec(a: entier, b: entier) → entier

Et on doit avoir l'égalité produit_rec(a, b) = a * b pour tous a et b entiers positifs ou nuls.