Vollständige Induktion

08/05/2010 - 13:51 von Roman Töngi | Report spam
I would like to prove the correctness of the following recursive implementation
of a function Add using mathematical induction:

The function Add adds the number 1 to all elements of stack s.
For example, if s = [5, 3, 8]: Add([5, 3, 8]) = [6, 4, 9]

Implementation of Add:
function Add(s) {
if (Size(s) == 0)
return s;
}
else {
return Push(Peek(s) + 1, Add(Pop(s)));
}
}

Function Size(s) returns the number of elements in s.
Function Push(el, s) pushes element el onto stack s.
Function Peek(s) gets the top element of stack s not removing it.
Function Pop(s) returns the stack with the top element removed.


I proceeded as follows:

1. Base case:
If there is no elements to be processed, that is the empty stack, then
just return s.

2. Inductive step:

Inductive hypothesis: Add(s) = Push(Peek(s) + 1, Add(Pop(s)))

If there is one more element in s we have:
Add(Push(el, s)) = Push(Peek(Push(el, s)) + 1, Add(Pop(Push(el, s))))

I do not know how to prove Push(Peek(Push(el, s)) + 1, Add(Pop(Push(el, s))))
using the inductive hypothesis.

Thanks for any help.
 

Lesen sie die antworten

#1 k. Schubser
08/05/2010 - 14:57 | Warnen spam
Roman Töngi schrieb:
I would like to prove the correctness of the following recursive
implementation
of a function Add using mathematical induction:

The function Add adds the number 1 to all elements of stack s.
For example, if s = [5, 3, 8]: Add([5, 3, 8]) = [6, 4, 9]

Implementation of Add:
function Add(s) {
if (Size(s) == 0)
return s;
}
else {
return Push(Peek(s) + 1, Add(Pop(s)));
}
}



I don't know your Computer Language (i'm a Delphi-Freak),
but I anderstand your program and have no necessity to prove it.
It is clear.

Nevertheless:

Proposition:

For all n of {0,1,2,...}

s=[a1,a2,a3,..., a(n-1),an] => add(s)=[a1+2,a2+1,...,,a(n-1)+1,an+1]

Induction of n:

Base case: n=0

s=[] add(s)=[], because Size(s) == 0.

Induction step:

induction hypotheses:

for n of {0,1,2,...}
s=[a1,a2,a3,..., a(n-1),an] => add(s)=[a1+2,a2+1,...,a(n-1)+1,an+1]

We must show:
s=[a1,a2,a3,...,an,a(n+1)] => add(s)=[a1+2,a2+1,...,,a(n)+1,a(n+1)+1]

Prove:

add(s) = Push(Peek(s) + 1, Add(Pop(s)))

= Push(a(n+1) + 1,[a1+2,a2+1,...,a(n-1)+1,an+1])
(because induction hypotheses)
= [a1+2,a2+1,...,,a(n)+1,a(n+1)+1]

See Beispiel 1 of
http://delphi.zsg-rottenburg.de/vollstind.html

Greetings
K.

Ähnliche fragen