Je viens de commencer à parcourir le manuel de conception d'algorithmes et j'ai du mal à comprendre comment prouver l'exactitude des algorithmes. Quelqu'un peut-il m'aider s'il vous plaît en expliquant l'exemple de question que j'ai fourni.

Prouvez l'exactitude de l'algorithme récursif suivant pour multiplier deux nombres naturels, pour toutes les constantes entières c ≥ 2.

function multiply(y,z)
comment Return the product yz.
1. if z = 0 then return(0) else
2. return(multiply(cy, z/c) + y · (z mod c))
1
Teererai Marange 29 déc. 2015 à 06:47

2 réponses

Meilleure réponse

Déclarons formellement ce que nous essayons de prouver:

For all integers y, z, we have multiply(y, z) = y · z.

Pour les algorithmes récursifs, nous voulons généralement une preuve d'induction. Cela nous oblige à sélectionner une quantité d'induction, qui devrait décroître à chaque appel récursif. Ici, nous pouvons utiliser |z|. La proposition inductive est

For all integers k ≥ 0, for all integers y, z such that |z| = k,
  we have multiply(y, z) = y · z.

Le cas de base est quand |z| = 0. Cela implique que z = 0, et nous vérifions que multiply(y, z) = 0 (le if est pris) et y · z = y · 0 = 0.

Les cas inductifs sont quand |z| > 0. Le else est pris, et depuis c ≥ 2, on sait que |trunc(z / c)| < |z| et donc, par l'hypothèse inductive, multiply(c · y, trunc(z / c)) = c · y · floor(z / c). La valeur de retour est donc

  c · y · trunc(z / c) + y · (z mod c)
= y · (c · trunc(z / c) + c · (z / c - trunc(z / c)))
= y · (c · z / c)
= y · z,

Comme demandé.

7
David Eisenstat 29 déc. 2015 à 04:10

Par récursivité sur z.

On suppose que c'est vrai pour tout z

C'est vrai si z = 0: multiplier (y, z) = 0 (règle 1).

Ensuite, ce sera vrai pour chaque K.

Cas 1: z & lt; c

Alors z / c = 0, z% c = z

Puis multiplier (y, z) = multiplier (cy, z / c) + y · (z mod c)) (règle 2).

= multiplier (cy, 0) + y · z = 0 + y. z = y. z VRAI

Cas 2: z & gt; = c

Alors z / c = 2)

Puis multiplier (y, z) = multiplier (cy, z / c) + y · (z mod c)) (règle 2).

= cy. (z / c) + y. (z mod c) (RÉCURSION)

= y. (c. (z / c) + z mod c)

Mais c. (z / c) + z mod c = z (définition de mod)

puis multipliez (y, z) = y. z C'est fait.

1
guillaume girod-vitouchkina 29 déc. 2015 à 07:44