Induktion .. machen

Hey Leute, wie angekündigt, nun eine Frage zum Beweis des Algorithmus.
Ich habe also einen Algorithmus, der mir a^(2^m) in m schritten berechnet.

eine funktion pow(a, n) wobei n = 2^m ist.
(m wird dann mit log zur basis 2 von n berechnet)

pseudocode (E soll element aus heißen, dieses komische e halt):


function pow(a, n){
  m = log2(n)
  if not m E N return fehler //also wenn m keine natürliche zahl ist..
  x = a
  for i = 0, i < m, i++
    x = x * x
  end
  return x
end function

terminierung habe ich eigentlich bewiesen, das es m schritte sind auch. jetzt muss
ich die korrektheit durch induktion beweisen.

Ich könnte also für n = k über k indu…zieren? :

  • Induktionsanfang: k = 1:
    pow(a, 1) = a^(2^1) = a^2
    m ist ja log2 von 1, also 0,
    die schleife wird 0 mal ausfeführt, ergebnis ist x also a

  • Induktionsschritt: und hier ist mein problem. Die Annahme wäre das es für jedes
    k oder n E N0 also für jedes n oder k größer 0 gilt.

jetzt muss ich das ja für pow(a, n + 1) beweisen…
Könnte mir jemand helfen, wie ich das machen soll?

Danke…

*** Edit ***

theoreetisch… müsste ich doch beweisen das:

pow(a, n) * log2(n) = pow(a, n + 1), das wäre doch mein induktionsschritt oder?

aber wie beweise ich das?

(a * a * a… log2(n) mal) * log2(n) = (a * a… log2(n) + 1 mal…

aber das ist doch kein beweis, oder?

das mit dem log2 würde ich wegwerfen, das ist sinnlos

lieber gleich eine funktion power2(a,m) berechnet a^(2^m)

Ein Beweis der Korrektheit ist bei einem nicht-rekursiven Programm nicht ganz einfach, normalerweise würde man das so machen

funzt für m=0 check

funzt für m=1 check (überflüssig, aber manchmal schaut man halt nach)

angenommen es funzt für ein m

Zeige, dass dann auch für m+1 das richtige rauskommt

rekursiv ginge das so:

power2(a,m+1)

=power2(a,m)*power2(a,m) // das ist der Algorithmus

=2^m 2^m ** // das ist die Induktionsannahme**

= 2^(m+1) // Rechenregeln für Potenzen

in der aufgabe steht, die parameter sollen a und 2^m sein…

Hmm also sollte ich es rekursiv umschreiben?

2^m ist doch kein Parameter, m ist einer

*** Edit ***

[QUOTE=mymaksimus]in der aufgabe steht, die parameter sollen a und 2^m sein…

Hmm also sollte ich es rekursiv umschreiben?[/QUOTE]

Ja, ist schöner und eleganter, und in dem Fall ist der callstack kein problem

was möchte ich zeigen?,
Annahme,
Anfang,
Induktionsschritt,
qed,
(vollständige) Induktion,

aber so würde ich es nicht machen,

Invariante ist vielleicht schöner, und die ist nur zwei Zeichen. :wink:

hth, vlg.

[QUOTE=Bleiglanz]das mit dem log2 würde ich wegwerfen, das ist sinnlos

lieber gleich eine funktion power2(a,m) berechnet a^(2^m)

Ein Beweis der Korrektheit ist bei einem nicht-rekursiven Programm nicht ganz einfach, normalerweise würde man das so machen

funzt für m=0 check

funzt für m=1 check (überflüssig, aber manchmal schaut man halt nach)

angenommen es funzt für ein m

Zeige, dass dann auch für m+1 das richtige rauskommt

rekursiv ginge das so:

power2(a,m+1)

=power2(a,m)*power2(a,m) // das ist der Algorithmus

=2^m 2^m ** // das ist die Induktionsannahme**

= 2^(m+1) // Rechenregeln für Potenzen[/QUOTE]

edit: oje, das ist ja bullshit

= a^(2^m) a^(2^m)

= a^(2^m+2^m)

= a^(2*2^m)

= a^(2^(m+1))

muss es heißen

[QUOTE=Bleiglanz]edit: oje, das ist ja bullshit

= a^(2^m) a^(2^m)

= a^(2^m+2^m)

= a^(2*2^m)

= a^(2^(m+1))

muss es heißen[/QUOTE]

Das wollte ich eigentlich auch sagen, 2^m * 2^m wäre (2^m)². (Das hilft nicht weiter).

Du hast es jetzt so stehen, dass sofort ersichtlich ist, dass der Schritt m->m+1 gilt.

Aber die Schleifen-Invariante. Vorbedingung, Invariante, Nachbedingung (suaber aufschreiben), gilt auch als Beweis.

Ehmmm, bei der Aufgabe könnte int ((2^31)-1) schnell zu klein sein/werden. Deshalb müsste eigentlich auch noch bewiesen werden, dass der Wertebereich Ok ist. Aber wie man das macht, das weiß ich nicht.

mymaksimus, helfen dir unser Nachdenken weiter?

deins wie immer weniger, cyborg, und zum thema rekursiv… hmm…
lässt sich das denn nicht genauso für die schleife begründen? was übersehe ich?

Vollständige Induktion ist eine mathematische Beweismethode, nach der eine Aussage für alle natürlichen Zahlen bewiesen wird. Da es sich um unendlich viele Zahlen handelt, kann solch ein Beweis nicht für alle Einzelfälle durchgeführt werden. Er wird daher in zwei Etappen durchgeführt: als Induktionsanfang für eine kleinste Zahl, für die man die Aussage zeigen will, (meist 1 oder 0) und als Induktionsschritt, der aus der Aussage für eine variable Zahl die entsprechende Aussage für die nächste Zahl logisch ableitet. Dieses Beweisverfahren ist von grundlegender Bedeutung für die Arithmetik und Mengenlehre und damit für alle Gebiete der Mathematik.

Vollständige Induktion - Wiki

mit Schleife brauchst du nicht zu kommen, es gibt nur eine Induktion, Infos sind gegeben, nur noch schön aufzuschreiben

Der Witz ist, dass der Schleifenbeweis ein direkter Beweis ist und dann keine Induktion nötig ist.

Wenn du mit Argumenten beweist, dass die Schleife für den Input m die Zahl a^(2^m) produziert, bist du ja eh schon fertig, weil das Argument für m+1 genau so gehen würde.

Auch ein Beweis, genau so gut, aber eben kein Induktionsbeweis.

hm… naja… mal schauen was der übungsleiter dazu sagt :wink:
aber verstanden hab ichs, danke ^^

Wichtig ist einfach, dass du an einigen Stellen “magische Schritte” nicht einfach weglässt, s. d. es nachvollziehbar bleibt. Dann gibt’s ne 1.