Zitat von moonylo
Ankündigung
Einklappen
Keine Ankündigung bisher.
User helfen Usern - Mathe
Einklappen
X
-
Bin das mal im Kopf durchgegangen, sollte wirklich gehen mit 1) und 2). Noch kurz zur Erklärung der doppelten Inklusion:
Wenn man 2) zeigt, dann ist also die Menge T(n) enthalten in der Menge S(L(n),n).
Wenn man 1) zeigt, dann ist also die Menge S(L(n),n) enthalten in der Menge T(n).
Wenn die jeweils ineinander enthalten sind, dann sind die Mengen gleich.
Muss man halt nur Schritt für Schritt durchgehen. Zu 2):
a) Wenn t T(n), dann ist t ein Teiler von n. Sei t^2 n, dann ist | n/t | L(n) und damit auch in S(L(n),n). Warum ist | n/t | L(n) ? Nennen wir | n/t | mal k. also |t|*k = |n|. Damit ist k schonmal ein Teiler von n. Also müssen wir noch zeigen, dass k^2 n (aus der Fallunterscheidung) folgt.
1) Darfst du selber machen :)
Die andere Teilaufgabe würde ich genau so angehen und schauen wann du nicht mehr weiterkommst und ob das überhaupt sein kann. Dann findet sich da an der Stelle auch ein Gegenbeispiel - oder es geht durch und es stimmt ;)
Kommentar
-
danke für die ausführlichen schritte :-)Zitat von moonyloBin das mal im Kopf durchgegangen, sollte wirklich gehen mit 1) und 2). Noch kurz zur Erklärung der doppelten Inklusion:
Wenn man 2) zeigt, dann ist also die Menge T(n) enthalten in der Menge S(L(n),n).
Wenn man 1) zeigt, dann ist also die Menge S(L(n),n) enthalten in der Menge T(n).
Wenn die jeweils ineinander enthalten sind, dann sind die Mengen gleich.
Muss man halt nur Schritt für Schritt durchgehen. Zu 2):
a) Wenn t T(n), dann ist t ein Teiler von n. Sei t^2 n, dann ist | n/t | L(n) und damit auch in S(L(n),n). Warum ist | n/t | L(n) ? Nennen wir | n/t | mal k. also |t|*k = |n|. Damit ist k schonmal ein Teiler von n. Also müssen wir noch zeigen, dass k^2 n (aus der Fallunterscheidung) folgt.
1) Darfst du selber machen :)
Die andere Teilaufgabe würde ich genau so angehen und schauen wann du nicht mehr weiterkommst und ob das überhaupt sein kann. Dann findet sich da an der Stelle auch ein Gegenbeispiel - oder es geht durch und es stimmt ;)
Kommentar
-
Zum ersten Teil gebe ich dir vollkommen recht.Zitat von moonyloDas zweite ohne Induktion würde ich so gelten lassen. Aber um das korrekt aufzuschreiben fehlt da noch etwas:
1) Wenn du das mit Äquivalenzumformungen machst, dann fang immer mit der Gleichung an, die korrekt ist. Sprich du musst, wenn du den Beweis hinschreibst, die letzte Gleichung zuerst hinschreiben.
Ich fand das auch immer bescheuert, als mein Prof mir das gesagt hat, aber irgendwo hat er recht. Denn wenn man das mit Worten erklärt, dann würde man bei deiner Form sagen:
Wenn 2 * F(n) >= F(n+1) gelten würde, dann würde auch gelten, dass
.... und dann auch das
.... und dann würde auch gelten dass
F(n-2) >= 0. Und das gilt und deshalb gilt auch die erste Gleichung.
Das hört sich absolut bescheuert an :) Viel besser:
Es gilt F(n-2) >= 0. Daraus folgt, dass
... Und daraus folgt, dass
... und damit ist
2 F(n) >= F(n+1).
Wenn man dann nur bestimmte n N nimmt, hört sich das erste noch blöder an.
2) Du bist noch schuldig, dass F(n-2) > 0 ist für alle n >= 2 (oder 3 oder was auch immer). Keine große Sache das zu zeigen, aber fehlt halt noch (Sowas ist bei Induktion implizit mit drin).
------
Bei der "Induktion", also erster Teil, ist da die zweite Zeile falsch. Mal unabhängig von dem was ich in 1) gesagt hab:
2*F(n) >= F(n+1) = F(n) + F(n-1)
F(n) >= F(n-1)
Im Endeffekt brauchen wir dafür aber keine Induktion mehr, sondern wie bei 2) noch eine zusätzliche Gleichung, die wir allgemein zeigen müssen bzw auch können.
Ich sehe allerdings den Fehler in der zweiten Zeile der ersten Aufgabe nicht. Natürlich kann man die Aufgabe auch so ohne Verwendung der Induktionsannahme lösen, wie du es vorzeigst. Allerdings ist meine Herleitung mit Induktionsannahme deswegen ja nicht falsch, oder?
Kommentar
-
Sitze auch gerade an Induktionsbeiweisen. Leider sind meine Umformungsskills etwas eingerostet. Hab die Induktion quasi fertig, aber im letzten Schritt muss ich die Gleichheit ja irgendwie ersichtlich machen (via Taschenrechner geprüft ist sie schon). X N
-2^(-X-1) = -2^(-X) + 2^(-X-1)
Jemand ne Idee ?
Kommentar
-
Ich meinte da nur, dass du da was falsch gerechnet hast. Und dann raffe ich auch nicht wo du die Induktionsannahme anwendest (mit korrigiertem Fehler) :(Zitat von HagiZum ersten Teil gebe ich dir vollkommen recht.
Ich sehe allerdings den Fehler in der zweiten Zeile der ersten Aufgabe nicht. Natürlich kann man die Aufgabe auch so ohne Verwendung der Induktionsannahme lösen, wie du es vorzeigst. Allerdings ist meine Herleitung mit Induktionsannahme deswegen ja nicht falsch, oder?
Kommentar
-
Deine beiden Sätze sind wohl nicht komplett unabhängig.Zitat von moonyloIch meinte da nur, dass du da was falsch gerechnet hast. Und dann raffe ich auch nicht wo du die Induktionsannahme anwendest (mit korrigiertem Fehler) :(Zitat von HagiZum ersten Teil gebe ich dir vollkommen recht.
Ich sehe allerdings den Fehler in der zweiten Zeile der ersten Aufgabe nicht. Natürlich kann man die Aufgabe auch so ohne Verwendung der Induktionsannahme lösen, wie du es vorzeigst. Allerdings ist meine Herleitung mit Induktionsannahme deswegen ja nicht falsch, oder?
Bis hier sind wir uns ja einig:
2 F(n) >= F(n+1)
= F(n) + F(n-1)
= 2 F(n-1) + F(n-2)
jetzt verwende ich die Induktionsannahme, 2 F(n-1) >= F(n), das gibt dann
2 F(n) >= F(n) + F(n-2)
und nach Vereinfachung
F(n) >= F(n-2)
Da hat es doch keinen Fehler drin, oder?
Kommentar
-
function Order1(v)
if v = null then return
else
Print(v)
Order1(leftChild)
Order1(rightChild)
end if
end function
function Order2(v)
if v = null then return
else
Order2(leftChild)
Print(v)
Order2(rightChild)
end if
end function
function Order3(v)
if v = null then return
else
Order3(leftChild)
Order3(rightChild)
Print(v)
end if
end function
Als Eingabe erhalten die Algorithmen einen binären Baum. Jetzt soll ich dazu die Laufzeiten bestimmen. Die Print Operation kostet O(1)
Folgender Lösung hab ich:
T(n) = 2T(n/2) + O(1) => O(n), durch Master-Theorem.
Das kann doch irgendwie nicht sein oder?
Kommentar
-
Sollst du die Laufzeit bestimmen, oder den Aufwand der elementaren Operationen bestimmen?
Weil wenn es echt die Laufzeit ist, dann musst du folgendes bestimmen:
1) Codierungslänge Input (bei dir der binäre Baum, kommt dann auf Speichermethode an)
2) #elementarer Operationen
3) Codierungslänge größte Zahl
Laufzeitfunktion f ist dann #elementarer Operationen * Codierungslänge der größten Zahl
Kommentar
Kommentar