Fehler im Induktionsbeweis finden

Neue Frage »

deppensido Auf diesen Beitrag antworten »
Fehler im Induktionsbeweis finden
Hallo,

bei der Aufgabe im Anhang soll man begründen, wo der Fehler im Beweis ist.

Meine Idee: Im Induktionsanfang wird bereits die Behauptung als gültig vorausgesetzt, womit der Induktionsanfang falsch ist. Des weiteren sagt die definierte Menge nichts über die Laufzeit von Sortieralgorithmen aus, womit die Induktionsvoraussetzung: "n Algorithmen haben die gleiche Laufzeit" nicht angenommen werden kann. Somit wär auch der Induktionsschritt falsch.

Wäre meine Idee soweit richtig und kann man das so schreiben?

Vielen Dank schon mal.

Grüße
klarsoweit Auf diesen Beitrag antworten »
RE: Fehler im Induktionsbeweis finden
Versuch mal, ob der beschriebene Beweis für den Schritt von n=1 auf n=2 funktioniert. smile
Huggy Auf diesen Beitrag antworten »
RE: Fehler im Induktionsbeweis finden
Deine Argumentation ist völlig daneben.

Der Induktionsanfang ist völlig in Ordnung. Jeder Sortieralgorithmus hat dieselbe Laufzeit wie er selbst. Das ist nach den Regeln der Logik eine richtige Ausage. Da wird nichts vorausgesetzt.

Auch der Induktionsschluss ist fast richtig, aber halt nur fast. Es ist zu beweisen, wenn man für ein beliebiges gezeigt hat, , dann folgt daraus .

Der Schluss von auf ist für fast alle richtig, aber nicht für alle . Wenn man z. B. gezeigt hätte, , dann würde daraus zwingend folgen . Man hätte ja gezeigt, je 4 beliebige Sortieralgorithmen haben dieselbe Laufzeit. Nun betrachte man 5 beliebige Sortieralorithmen . Die Algorithmen haben dieselbe Laufzeit, weil man die Behauptung für schon gezeigt hat. Jetzt betrachte man die Algorithmen . Das sind auch 4 Stück. Also haben auch die dieselbe Laufzeit. Dann haben aber alle 5 dieselbe Laufzeit, was zu beweisen war.

Wo also steckt der Wurm?
Der Schluss von auf funktioniert bei nicht. Für ist die Behauptung richtig. Nun betrachte man 2 beliebige Algorthmen und . Wenn man jetzt in der Menge gegen austauscht, hat man die Menge . Das ist wieder eine einelementige Menge. Man kann in dieser Menge mit keinem anderen Agorithmus vergleichen. Also kann man nicht den Schluss ziehen und hätten dieselbe Laufzeit.

Der Fehler in diesem Induktionsbeweis ist schon etwas subtil versteckt.

Edit: Habe nicht bemerkt, dass es inzwischen eine Antwort gab.
deppensido Auf diesen Beitrag antworten »

Hallo,

erst mal danke für die ausführliche Antwort. Im Prinzip hast du die Antwort schon gegeben. Darauf, dass der Beweis fast richtig ist, hätte ich nicht gedacht. Somit wär ich wohl auch nicht auf die Lösung gekommen. Aber ich denke, ich hab verstanden, wie man an so was ran geht: Einfach ein Beispiel finden, für den der Induktionsschritt nicht stimmt, in diesem Fall war es für n = 1 auf n = 2.

Danke nochmals.

Grüße
alm Auf diesen Beitrag antworten »

Hallo,
ich habe eine sehr ähnliche Aufgabe zu lösen. Die Aufgabe von deppensido fand ich jedoch etwas einfacher.

Kann mir bitte jemand sagen, ob man bei meiner Aufgabe das so überhaupt machen kann. Der Induktionsanfang ist n=1 und alle ( nur einer ) Computer sind somt gleich schnell.

Nun entfernt man im Induktionsschritt einen Computer und behauptet, dass jetzt bei n-1 immer noch alle Compter gleich schnell sind. Wie ist das genau zu verstehen? Davor war es n=1 und danch n-1. Somit ist kein Computer mehr zu vergleichen und es dürfte auch keine Geschwindigkeit vorhanden sein, die man messen könnte.

Oder ist es so zu verstehen, dass bei keinem Comuter auch keine Geschwindigkeit ( was auch eine Geschwindigkeit ist ) vorhanden ist und somit sind "alle" nicht vorhanden Computer gleich schnell ohne Geschwindigkeit?

Wäre nett, wenn sich noch jemand zu diesem Thema melden würden.
RavenOnJ Auf diesen Beitrag antworten »

Der "Beweis" funktioniert aus exakt demselben Grund nicht wie der "Beweis" des ursprünglichen Fragestellers. Guck dir die Widerlegung an. Der kritische Wert ist wieder n=2. Da man einen Computer nicht mit sich selber vergleichen kann, ist die Schlussfolgerung im Induktionsschritt für n=2 sinnlos. Das kannst du schon daran sehen, dass du annehmen kannst, beide Computer sind unterschiedlich schnell. Das würde nichts an der "Richtigkeit" des Induktionsschrittes ändern. Er ist also unzulässig und damit falsch.
 
 
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »