Großer Theta-Beweis für die Polynomfunktion

7

Dies sind keine Hausaufgaben. Ich habe die Lösung, aber es ist nicht das, was ich bekomme. Ich weiß, dass es mehrere Lösungen für das Problem gibt, aber ich möchte sicherstellen, dass mir nichts entgeht.

Die Frage lautet wie folgt:

Man beweise, dass 2 - 4n + 7 = Θ ( ) ist. Geben Sie die Werte der Konstanten an und zeigen Sie Ihre Arbeit.n2n2

So bin ich mit dem Problem umgegangen:

Aus der Definition von Θ (g (n)):

0 ≤ C 1 n2 ≤ 2 n2 - 4n + 7 ≤ C 2 n2

Teilen Sie die Ungleichung durch den n-Term der größten Ordnung. (Nur so kann ich diese Gleichungen lösen.)

0 ≤ C 1 ≤ 2 - (4 / n - 7 / ) ≤ C 2n2

Teilen Sie das Problem in zwei Teile: LHS und RHS.

Wir beginnen mit der RHS:

Finden Sie die Konstante C 2 , die erfüllt

0 ≤ 2 - (4 / n - 7 / ) ≤ C 2n2

n = 1, (2 - (4/1 - 7/1 )) = 512

n = 2, (2 - (4/2 - 7/2 )) = 7/422

n = 3, (2 - (4/3 - 7/9)) = 13/9

Wir wählen C 2 als 2, n ≥ 2, um die RHS zu erfüllen.

LHS: Wir versuchen eine Konstante zu finden, die zufriedenstellt

0 ≤ C 1 ≤ 2 - (4 / n - 7 / )n2

Von oben wissen wir, dass sich die Gleichung nach n = 2 2 nähert, wenn n größer wird. Wenn wir also eine Konstante wählen, die kleiner als 2 ist, sollte sie die LHS erfüllen.

Wir wählen C 1 als 1. Für n würde die Wahl von 1 die linke Seite erfüllen, aber da die RHS n ≥ 2 benötigt, bleiben wir dabei.

Die Konstanten, die 2 - 4n + 7 = Θ ( ) beweisen, sind alson2n2

C 1 = 1, C 2 = 2, n ≥ 2

Die gegebene Lösung für dieses Problem wählt n≥4, aber ich bin nicht sicher warum. Es scheint, dass n ≥ 2 gut funktionieren würde. Liege ich irgendwo falsch

Wenn ich mich nicht irre, wenn ich C 1 als auch 2 gewählt hätte, würde das nicht auch die linke Seite befriedigen, da die Ungleichung es erlaubt, ≤ zu sein?

Harrison Nguyen
quelle

Antworten:

8

Ihre Lösung ist in Ordnung. Es gibt mehrere Möglichkeiten, diese Tatsache zu beweisen, alle gültig / korrekt. Ihr Ansatz ist also gültig, und es ist möglich, dass die Lösung aus Ihrer Klasse auch gültig ist: Das ist kein Widerspruch.

Lassen Sie mich Ihnen jedoch einen Rat geben, wie Sie Ihren Beweis in Zukunft strukturieren können. In dem Argument, das Sie in der Frage skizziert haben, arbeiten Sie "rückwärts": Sie gehen von der Aussage aus, von der Sie sich wünschen, dass sie wahr ist (dasc1n22n2- -4n+7c2n2), und dann versuchen Sie abzuleiten, was wahr sein muss c1,c2für Ihren Wunsch, wahr zu halten. Die Erfahrung hat jedoch gezeigt, dass diese Art von Argumentation fehleranfällig ist: Es fällt Ihnen leicht, unterwegs einen Fehler zu machen. Es ist auch für andere schwer zu überprüfen.

Wenn Sie Ihren Beweis aufschreiben, schlage ich vor, dass Sie in die entgegengesetzte Richtung argumentieren. Beginnen Sie mit dem, was Sie wissen, dass es wahr ist, und leiten Sie dann die Implikationen daraus ab und schließen Sie mit der Schlussfolgerung, dassc1n22n2- -4n+7c2n2. Dies entspricht besser der Denkweise der Menschen und erleichtert dem Leser das Verständnis der Vorgänge. Und der Zweck eines Beweises besteht darin, dem Leser eine Idee zu vermitteln. Daher sollte der Beweis so strukturiert sein, dass das Leben des Lesers einfacher wird: damit der Leser so einfach wie möglich überprüfen kann, ob die Argumentation des Beweises korrekt und gültig ist. Es ist wie ein gutes Buch; Gutes Schreiben wird gewählt, um dem Leser das Leben gut zu machen. Beweise sind der gleiche Weg. Und letztendlich wird dies auch Ihnen zugute kommen: Wenn Sie meiner Erfahrung nach diesem Ansatz folgen, ist es weniger wahrscheinlich, dass Sie einen subtilen Fehler in Ihrem Beweis machen.

Ein besserer Beweis wäre also, dies zu zeigen n22n2- -4n+7 gilt für alle n2 (weil so und so), und zeigen Sie das 2n2- -4n+72n2 gilt für alle n2 (weil bla-de-bla), und schließen Sie daraus 2n2- -4n+7Θ(n2). Mir ist klar, dass diese Art von Beweis schwieriger zu schreiben ist, weil Sie den Wert von kennen müssenc1,c2zu verwenden, bevor Sie anfangen können, diesen Beweisstil aufzuschreiben. Aber weißt du was? Das ist ok. Sie können eine Seitenberechnung auf Rubbelpapier durchführen, um herauszufinden, welcher Wert vonc1,c2benutzen. Zeigen Sie uns diese Nebenberechnung nicht. finde einfach heraus, welchen Wert vonc1,c2 wäre gut zu tun, und dann beginnen Sie den Beweis mit Ihnen ziehen c1=1,c2=2magisch aus der Luft und zeigen, dass Ihre Wahl gültig ist. Diese Art des Beweises ist besser für Sie und besser für den Leser.

DW
quelle
Vielen Dank. Ich wollte nur sicherstellen, dass ich etwas nicht übersehen habe. Da ich neu in diesem Bereich bin, ist es schwer zu sagen, wann ich Recht habe, da es mehrere Lösungen gibt.
Harrison Nguyen
Das ist eigentlich ein sehr hilfreicher Einblick, wie man bessere Beweise schreibt. Es scheint, dass die meisten Beweise in dem von mir verwendeten Lehrbuch so geschrieben sind. Ich blieb eine Weile stecken und fand heraus, wie sie den Wert der Konstanten auf magische Weise aus der Luft zogen. Für das nächste Mal notiert.
Harrison Nguyen
In gewissem Sinne sind die mehreren Lösungen sind , wie Sie es den „richtigen“ kennen. Sie / wir beginnen, in die theoretischere Wissenschaft einzusteigen, wo Sie glauben, ein Modell zu haben, das Phänomene erklärt. Zum Beispiel glauben Sie (aber wissen es nicht wirklich), dass "Big Theta" im Einklang mit Mathematik und Logik usw. die Komplexität der Berechnungen beschreibt. Ihre Lösung untermauert diesen Glauben. Andere Lösungen untermauern dies weiter. So entsteht ein wissenschaftlicher Konsens.
Nobbynob Littlun
Die Beobachtung der DW über das Verfassen von Korrekturen ist scharfsinnig, und ich würde noch einen Schritt weiter gehen (wenn es die Zeit erlaubt). Anstatt nur eine Nebenberechnung zu haben, muss jede Schreibweise ein Zweig sein und sie parallel zur Fertigstellung ausführen. Wenn Sie vermasseln, sollte der Widerspruch sofort herausspringen. Wenn Sie nicht vermasseln, haben Sie eine verdammt gute Erklärung.
Nobbynob Littlun