Matematik

Induktionsbevis for en algoritme

20. juni 2008 af datmat (Slettet)

Hej, er der nogen der kan løse opgaven herunder.

Betragt følgende algoritme til at gange to positive heltal.

MULT(a,b)
Hvis a = 1
returner b
Ellers
returner MULT([a/2],2b) + b * (a mod 2)

Bemærk at [a/2] betyder a/2 rundet ned, det betyder fx 3/2 = 1, 6/3 = 2, 5/2 = 2.

Også bemærk at "a mod 2" betyder fx 3 mod 2 = 1,
6 mod 2 = 0, 5 mod 3 = 2.

Opgaven lyder sådan her:
Bevis ved induktion over a, at MULT(a,b) returnerer produktet ab.

I mit forsøg på at løse opgaven har jeg gjort følgende.

Basisskridt:

a = 1

1 * b = 1 * b

MULT(1,b)
Hvis a = 1
returner b

Dvs. MULT(1,b) = b = 1 * b

Det betyder basisskridt er OK.

Induktionsskridt:

Antager at algoritmen MULT(a,b) er sand for a, og skal nu bevise at algoritmen også er sand for a + 1.

Nu kan jeg ikke komme videre !

Brugbart svar (0)

Svar #1
20. juni 2008 af tal-pædagog (Slettet)

Se nu på MULT(a+1,b). Da [(a+1)/2]<=a ved vi fra induktionsantagelsen, at MULT([(a+1)/2],2b) giver produktet af de to, altså:

MULT([(a+1)/2],2b) = [(a+1)/2]*2b

Prøv selv videre... Det kommer til at stemme (hint: indel i tilfældene a+1 lige hhv. a+1 ulige)

Svar #2
20. juni 2008 af datmat (Slettet)

Jeg vil prøve at kæmpe med at løse opgaven. Jeg skriver tilbage i morgen lørdag aften og fortæller hvordan det er gået. Det kan godt være at jeg har brug for lidt mere hjælp, lad os nu se, men foreløbig tak.

Svar #3
21. juni 2008 af datmat (Slettet)

Opgaven driller mig stadigvæk. Derfor har jeg et par yderligere spørgsmål.

1) Hvad er det egentlig for et udtryk vi skal nå frem til i induktonsskridtet, for at vi har bevist at algoritmen er sand for a+1 ?

2) Du skriver "Se nu på MULT(a+1,b). Da [(a+1)/2]<=a ved vi fra induktionsantagelsen, at MULT([(a+1)/2],2b) giver produktet af de to, altså:

MULT([(a+1)/2],2b) = [(a+1)/2]*2b."

Mit spørgsmål er følgende. I basisskridtet har jeg kun bevist at
MULT(a,b) giver produktet a * b når kun a = 1, og ikke når det er <= a, så hvordan kan du bruge <= her "Da [(a+1)/2]<=a ved vi fra induktionsantagelsen...." for oven i dit svar ?

3) Endvidere synes jeg ikke du har benyttet det sidste led i den sidste sætning i algoritmen til noget, det er det led der siger
"....+ b * (a mod 2)" ?

Brugbart svar (0)

Svar #4
21. juni 2008 af tal-pædagog (Slettet)

1) Du skal vise, at MULT(a+1,b)=(a+1)*b

2) Induktionsantagelser fungerer netop på den måde. Du har vist, at det gælder for a=1. Induktionsskridtet viser så, at det gælder for det næste tal, nemlig a=2. Men for ikke at skulle gennemføre beviset igen, "genbruger" man argumentationen. Da vi skal vise, at det gælder for samtlige naturlige tal, genbruger vi argumentationen uendeligt mange gange. Dette gøres som følger:

Vi skal vise implikationen

udsagnet er sandt for alle tal op til et bestemt tal (her a) => udsagnet er sandt for det næste tal (a+1)

altså antaget vi, at udsagnet gælder for alle tal mindre eller lig a, hvilket vi altså frit kan bruge.

3) Det mangler netop at blive benyttet - det er det, som får beviset til at passe i de to tilfælde, jeg nævner...

Hvis jeg skal hjælpe mere, kommer jeg til at give løsningen... Skal jeg det?

Svar #5
21. juni 2008 af datmat (Slettet)

Jo tak, jeg vil gerne bede om løsningen, og tak for hjælpen.

Brugbart svar (0)

Svar #6
21. juni 2008 af tal-pædagog (Slettet)

Der er to tilfælde:

Hvis a+1 er lige, er [(a+1)/2]=(a+1)/2, hvorfor [(a+1)/2]*2b=(a+1)*b og så passer det, da b*(a+1 mod 2) samtidig giver 0

Hvis a+1 er ulige, er [(a+1)/2]=a/2, hvorfor [(a+1)/2]*2b=a*b og så passer det sørme igen, da b*(a+1 mod 2) så giver b, så det i alt giver a*b+b, hvilket er (a+1)*b

Spørg, hvis det kniber med skridtene

Svar #7
21. juni 2008 af datmat (Slettet)

Med din løsning i hånden har jeg regnet opgaven igen fra start til slut. Jeg lærte en hel del nyt med denne opgave. Du skal have tak.

Brugbart svar (0)

Svar #8
21. juni 2008 af tal-pædagog (Slettet)

Det glæder mig meget!

Skriv et svar til: Induktionsbevis for en algoritme

Du skal være logget ind, for at skrive et svar til dette spørgsmål. Klik her for at logge ind.
Har du ikke en bruger på Studieportalen.dk? Klik her for at oprette en bruger.