In Übungsaufgabe 2.2.(a) soll die Substitutionsmethode angewandt werden. Leider ist dieser Begriff überladen.
Ist darunter "Substitutionsmethode" iSv Cormen zu verstehen (also Schrankenschätzen und anschließender Beweis, vgl.
http://de.wikipedia.org/wiki/Substitutionsmethode) oder "Substitutionsmethode", wie es im Skript Verwendung findet (iteratives Einsetzen der Formel in sich selbst, dann allgemeine Formel für k Iterationen finden; offenbar auch "Iterationsmethode" genannt)?
In Übungsaufgabe 2.2.(a) soll die Substitutionsmethode angewandt werden. Leider ist dieser Begriff überladen.
Ist darunter "Substitutionsmethode" iSv Cormen zu verstehen (also Schrankenschätzen und anschließender Beweis, vgl. http://de.wikipedia.org/wiki/Substitutionsmethode) oder "Substitutionsmethode", wie es im Skript Verwendung findet (iteratives Einsetzen der Formel in sich selbst, dann allgemeine Formel für k Iterationen finden; offenbar auch "Iterationsmethode" genannt)?
Eher das durch "Abwickeln" (≈ iteratives Einsetzen der Formel in sich selbst) die Funkton finden, mit der eine obere Schranke gem. O-Notation definiert wird.
Eine Funktion "Raten" und dann durch Einsetzen überprüfen ist eher nicht gemeint, da dies keine stets anwendbare Methode zu sein scheint…
Hmm ich habe mal angefangen mit Substitition, direkt für n=2 hake ich aber:
Die Gleichung wäre da
3*T(2/3) + 1/2
Laut Aufgabe ist T:N->N. T(2/3) wäre also gar nicht definiert weil 2/3 keine natürliche Zahl ist.
Heisst das jetzt die Funktion ist auch für n=2 nicht definiert?
Oder habe ich da irgendwo nen Denkfehler?
Und wenn mans einfach so einsetzen würde ohne drauf zu achten dass es keine natürliche Zahl ist käme man auf etwas mit T(2/3/3), im nächsten Schritt T(2/3/3/3) usw… das kanns ja auch nicht sein dann terminiert das ja schon für n=2 nicht?
Vielleicht wäre jemand bereit euch zu helfen, wenn er/sie die Aufgabe wüsste…
Oh Ja… also Aufgabe ist:
Sei T(n) :={c, für n=1
{3*T(n/3) + 1/n, sonst
eine Rekurrenzgleichung.
Für die Funktion T:= N-> N sollen Sie die Größenordnung bestimmen. Sie sollen dazu beide bekannten Methoden (Substitutionsmethode und MasterTheorem) verwenden, und die erzielten Ergebnisse vergleichen.
Was ich oben versucht habe ist (glaub ich zumindest…) Substitutionsmethode.
Dass T als N -> N definiert ist, liegt daran, dass n ja Einheiten darstellen sollen, irgendwelche Werte in einem Array oder Komponenten eines Baums oder was auch immer. Da ergeben nicht natürliche Zahlen logischerweise keinen Sinn.
Für das rekursive abwickeln geht man davon aus, dass man Werte von n hat, die genau passen. Also in eurem Fall n = 3^m. Da du ja nur eine Abschätzung für die Laufzeit suchst, kann man das machen. Hat man dann am ende eine nicht rekursive Form für die Gleichung gefunden benutzt man
Gaußklammern um es für belibige n passend zu machen. Damit begeht man dann zwar einen kleinen Fehler, weil die Zahl der Einsetzungen dann etwas zu groß oder zu klein ist aber das macht erstmal nicht so viel bei der Abschätzung.
Ah OK, danke Dir. Dann werd ich mal damit weiter versuchen.
Oh Ja… also Aufgabe ist:
Sei T(n) :={c, für n=1
{3*T(n/3) + 1/n, sonst
eine Rekurrenzgleichung.
Für die Funktion T:= N-> N sollen Sie die Größenordnung bestimmen. Sie sollen dazu beide bekannten Methoden (Substitutionsmethode und MasterTheorem) verwenden, und die erzielten Ergebnisse vergleichen.
Was ich oben versucht habe ist (glaub ich zumindest…) Substitutionsmethode.
Die Aufgabe stimmt so nicht, ich habe sie vor mir liegen und eben online nachgeschaut:
T(n) :=
bei n=1| 0
sonst | 4 * T(n/2)+n^2
Oha, gut dass du das sagst… ich hatte das Blatt vom letzten Jahr runtergeladen.
Der Link in STINE unter Studium>Modulliste>AD>Vorlseung AD ist falsch!
Unten bei Material der Link
2 zweites Übungsblatt
Die Lösungen finden Sie später unter der angegebenen Internetlink:
Datei: AuD09aufg2.pdf Internetlink:
http://www.informatik.uni-hamburg.de/TGI/lehre/vl/WS0809/AuD/Datei ist richtig verlinkt, aber "Internetlink" führt zu einer Seite vom letzten Jahr… da hatte ich das Aufgabenblatt runtergeladen.
Und wenn mans einfach so einsetzen würde ohne drauf zu achten dass es keine natürliche Zahl ist käme man auf etwas mit T(2/3/3), im nächsten Schritt T(2/3/3/3) usw… das kanns ja auch nicht sein dann terminiert das ja schon für n=2 nicht?
T(2/3/3) ist eigentlich:
[latex] T\left(\frac{2}{3\cdot 3}\right)=T\left(\frac{2}{3^2}\right)[/latex]
