Vollständige Induktion für Java-Methode

U

User5001

Mitglied
Ich weiß nicht so recht, ob ich hier im Forum richtig bin mit meiner Frage, versuche es aber trotzdem mal :)

Folgende Aufgabe gilt es zu lösen:

zwischenablage015m5y.jpg


Der Quellcode dazu ist dieser:

Java: 
public static double calc (int n) {
	if (n < 0)
		throw new RuntimeException ();
	double summe = 0.0;
	int produkt = 1;
	double quotient = 0.0;
	int i = 0;
	// I
	while(i < n) {
		i++;
		produkt = i * (i +1);
		quotient = 1.0/ produkt ;
		summe += quotient ;
		// II
	}
	return summe ;
}

Meiner Überlegung nach ist jetzt summe = summe + 1.0 / produkt was ja summe = summe + 1.0 / i * (i+1) ist.
Das ist ja was anderes als zu beweisen ist. ???:L Hat jemand eine Idee, wie man die Sache angeht?
 
S

SlaterB

Gast
ein wichtiger Punkt bei Induktion ist, dass du annehmen kannst, dass für den vorherigen Schritt die Annahme stimmt (für den ersten ja bewiesen),
(edit: steht ja auch groß und breit in der Aufgabe, bei b) die ersten zwei Zeilen.. )
daher ist summe nicht irgendwas beliebiges sondern genau ein Term den du zum Ausrechnen brauchst,
du musst den alten Term einsetzen und bekommst den neuen der auch wieder stimmt
 
Zuletzt bearbeitet von einem Moderator:
G

Gonzo17

Gast
Naja ich würde bei solchen Aufgaben immer den "mathematischen Weg" gehen, indem ich aus dem Code abeschreibe, was mathematisch so enthalten ist. Da steht ja beispielsweise nichts anderes als
Code: 
summe(n+1) = summe(n) + quotient(n)
(oder so in der Art). Musst du dir dann eben mal weitere Gedanken machen und dann kommste auch drauf.
 
A

Andi_CH

Top Contributor
Was ist eine Schleifeninvariante? Die einzige Variable die von der Schleife nicht verändert wird ist der Parameter n. Muss man beweisen das "n" stimmt?

Summe = Schleifeninvariante ???:L

Warum wird so etwas in einem loop berechnet?

Java: 
return ((n*1.0) / n + 1.0);

reicht doch auch?

Vermutlich wäre das im Bereich Mathematik besser aufgehoben? Ich sehe kein Java-typisches Problem ausser einer unhandlich komplizierten Lösung für eine banales Problem.
 
Zuletzt bearbeitet:
U

User5001

Mitglied
Danke für die Tipps! :)

Ja, mit Java hat das nicht unbedingt zu tun, ist nur das erste mal, dass ich einen Beweis zu einem Quelltext mache und ich dachte, hier hat das der ein oder andere schon hinter sich und kann helfen.

Ich denke, ich habs jetzt. Falls es jemanden interessiert, hier mein Versuch einer Lösung (mangels Zeit in Form von Screenshots):


Ich hoffe das kommt in etwa hin. Die Tabellen sind wohl nicht unbedingt notwendig, bringen aber vielleicht ein paar Pünktchen bei der Korrektur.
 
S

SlaterB

Gast
bisher hast du keinen Beweis,
du schreibst zunächst immer noch
summe = summe + 1/(i*(i+1))
was als Java-Befehl vielleicht Sinn macht, in der Mathematik aber nicht, summe links ist was anderes als summe rechts, also vergib auch unterschiedliche Variablen, wie Gonzo17 schon schrieb z.B. summe_i, summe_i+1 usw
das Einsetzen danach ist falsch bis fragwürdig,

besonders danach dann aber "was genau [..] entspricht" ist nun kein Beweis sondern eine Behauptung,
eine nicht richtige dazu, durch Beispiel (i = 5 einsetzen) leicht zu widerlegen
 
Zuletzt bearbeitet von einem Moderator:
A

Andi_CH

Top Contributor
User5001 hat gesagt.:
Ja, mit Java hat das nicht unbedingt zu tun, ist nur das erste mal, dass ich einen Beweis zu einem Quelltext mache und ich dachte, hier hat das der ein oder andere schon hinter sich und kann helfen.
Zum Vergrößern anklicken....

Du sollst eine beliebige Funktion beweisen, die im Quellcode vorliegt - was ich sagen wollte: Das Forum ist defintiv nicht das optimale das ist eine rein Mathematische Problemstellung.

Ich hab mir eben erklären lassen (ja und die grauen Zellen ganz weit hinten erwachten dann auch wieder=) was ein Induktion ist.

1. Schritt
Es gilt zu Beweisen, dass die Funktion für einen bestimmten Wert x das richtige Resultat liefert.
Ist in diesem Fall für X = 0 recht einfach
Mathematisch: f(0) = 0 / 0+1 = 0;
Die Funktion liefert 0, da der loop nie durchlaufen wird.
Des paasst

2. Schritt
Es gilt zu beweisen, dass die Funktion für ein beliebiges n ein korrektes Resultat liefert welches auf n-1 basiert.
Die Summe enthält das Resultat der letzten Berechung, also f(n-1)
Der Quotient enthält 1 / n * (n +1)
f(n) = n / (n+1) = f(n-1) + ( 1 / n * (n +1)) = summe + quotient

Für n = 4 (Beliebig gewählt - halt so dass es einfach Brüche gibt :) )

Direkt gerechnet: f(n) = n/(n+1) = 4/5

Basierend auf n-1 gerechnet:
f(n-1) = 3/4;
(1/(n*(n+1)) = 1 / 20
f(n) = 3/4 + 1/20 = 16/20 = 4/5 = f(n) qed

Ist es das was der Prof sehen will?
 
Zuletzt bearbeitet:
S

SlaterB

Gast
gesehen werden will ein allgemeiner Beweis mit Variablen, nicht ein bestimmtest Beispiel 4 und 5,
aber ein ganz guter Hinweis zum Rechnungsweg ohne gleich alles zu lösen, insofern passt das schon
 
A

Andi_CH

Top Contributor
Die Vollständige Induktion basiert aber genau auf einem konkreten Wert als Anfangsbedingung und dem Schritt von N auf N+1 ....

Jetzt kann ja auf dem Papier schritt für schritt nachweisen, dass das auch formelgemäss implementiert ist.

Mindestens für mich war erst mal der Beweis fällig, dass man n/n+1 auch wirklich so berechnen kann, wobei das allerdings viele einfacher auf algebraischem Weg denn als Induktion geht ....

Ich bin allerdings extrem gespannt wie man so einen Beweis anhand von Code führen soll.
 
Zuletzt bearbeitet:
U

User5001

Mitglied
Erstmal abwarten, wie gut meine Lösung war, dann kann ich sie auch gerne posten (dazu muss mein Prof sie mir aber erstmal zurückgeben) :)
 
S

SlaterB

Gast
i/(i+1) + 1/((i+1)*(i+2))
= (i+1)/(i+2)

genau, das ist der entscheidende Schritt,
erstaunlich dass du volle Punktzahl bekommst obwohl du ihn nur einfach hingeschrieben hast ;)

die Umrechnungen dafür sind gar nicht so trivial, mit binomischer Formel,
jedenfalls aus mathematischer Sicht interessanter als die restlichen 2 Seiten der Lösung
 
U

User5001

Mitglied
Ja, die Tabellen usw. waren wohl garnicht nötig, aber lieber zu viel als zu wenig, solange es nicht falsch ist.
Evtl. ist die Bewertung in meinem Fall nicht so streng. Ich studiere eigentlich Biologie und kämpfe mich nur durch ein unbenotetes Informatik-Modul um der Studienordnung gerecht zu werden.
 

Aktuelle Jobs

Neue Themen


Oben