FB18.de - Das Informatikforum
AD Blatt 2 - Druckversion

+- FB18.de - Das Informatikforum ( /mybb )
+-- Forum: Bachelorstudieng ( /forumdisplay.php?fid=112 )
+--- Forum: PM Praktische Informatik ( /forumdisplay.php?fid=98 )
+--- Thema: AD Blatt 2 ( /showthread.php?tid=10960 )

AD Blatt 2 - Anonymer User - 15.11.2009 20:55

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)?

RE: AD Blatt 2 - theorinix - 15.11.2009 21:37

Anonymer User schrieb:
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...

RE: AD Blatt 2 - Anonymer User - 16.11.2009 00:18

OK, danke sehr.

RE: AD Blatt 2 - Anonymer User - 17.11.2009 11:07

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?

RE: AD Blatt 2 - Anonymer User - 17.11.2009 11:21

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?

RE: AD Blatt 2 - doodles - 17.11.2009 16:36

Vielleicht wäre jemand bereit euch zu helfen, wenn er/sie die Aufgabe wüsste...

RE: AD Blatt 2 - Anonymer User - 17.11.2009 17:09

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.

RE: AD Blatt 2 - doodles - 17.11.2009 17:28

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.

RE: AD Blatt 2 - Anonymer User - 17.11.2009 17:37

Ah OK, danke Dir. Dann werd ich mal damit weiter versuchen.

RE: AD Blatt 2 - silentsea - 17.11.2009 19:20

Anonymer User schrieb:
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

RE: AD Blatt 2 - Anonymer User - 17.11.2009 20:12

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.

RE: AD Blatt 2 - theorinix - 18.11.2009 17:18

Anonymer User schrieb:
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:


RE: AD Blatt 2 - theorinix - 18.11.2009 17:20

Anonymer User schrieb:
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.


Wurde gerade korrigiert!