Übung 2 - H2

Benutzeravatar
Twister11
Mausschubser
Mausschubser
Beiträge: 48
Registriert: 26. Nov 2005 14:18
Kontaktdaten:

Übung 2 - H2

Beitrag von Twister11 »

H2: T(n) = T(n/2 +17) + n

Ein Rekursionsanker ist nicht angegeben. Das hat mich schon bei der G2 aufgeregt, wobei der Tutor der Übungsgruppe verkaufen wollte das so ein Anker ja nicht notwendig wäre. Nunja, man konnte einfach mal ins blaue hinein annehmen, dass T(1)=1 ist und dann war dsa lösen auch möglich, auch wenn diese Annahme absolut willkürlich ist.

Darf ich denn bei der H2 annehmen das T(33) = 1 ist ? Vielleicht steh ich nur auf dem Schlauch und die Aufgabe macht absolut Sinn, aber im Moment habe ich den Eindruck das das eine inkompetente Aufgabenstellung ist und das macht mich ziemlich wütend. Ich hab mit einem Mathematik-Studet drüer gesprochen und der hat mir zugestimmt. Wenn die Aufgabe wirklich falsch gestellt ist und ich nicht etwas wichtiges übersehen have, dann frage ich mich ernsthaft, WIE KANN SOWAS PASSIEREN ?!?!? Sowas ist echt zum heulen!

zb.
T(18) = T(26) + n
= T(30) + 2n
= T(32) + 3n
= T(33) + 4n = T(33) + 5n = T(33) + 6n ...

....aber wer braucht schon einen Anker. Vielleicht ist die Loesung auch: Es liegt nicht in O(nlogn) sondern in O(unendlich)


Sorry falls ich mich irre und nen Denkfehler drin habe, aber falls nicht verfestigt das nur wieder mal meine Meinung von der TUD.

Benutzeravatar
s!mon
Computerversteher
Computerversteher
Beiträge: 373
Registriert: 20. Okt 2007 18:24
Wohnort: Höchst i. Odw

Re: Übung 2 - H2

Beitrag von s!mon »

scheiß Emos :P

Irgendwann ist dein n klein genug und das Problem ist trivial lösbar. Das macht für die Lösung der Gleichung keinen Unterschied. Guck doch mal ins Algorithmenbuch, da ist auch nie ein Rekursionsanker angegeben..
Zuletzt geändert von s!mon am 21. Apr 2008 21:15, insgesamt 1-mal geändert.

Benutzeravatar
Georg
Mausschubser
Mausschubser
Beiträge: 60
Registriert: 15. Okt 2007 19:02

Re: Übung 2 - H2

Beitrag von Georg »

s!mon hat geschrieben:scheiß Emos :P

Irgendwann ist dein n klein genug [...] meiner Meinung nach dein Rekursionsanker immer bei n=1/0 (je nachdem ob und wie gerundet wird), da du ja sonst eine Endlosschleife hättest.[...]
wenn du twisters post nochmal genau liest, siehst du dass das n eben gegen 33 oder 34 geht und NICHT immer kleiner wird (in twisters fall sogar grösser)
Zuletzt geändert von Georg am 21. Apr 2008 21:12, insgesamt 1-mal geändert.
Alle Angaben ohne Gewähr
_________________
"there is no such word as 'impossible' in my dictionary. In fact, everything between 'herring' and 'marmalade' appears to be missing"
-- Dirk Gently

Benutzeravatar
s!mon
Computerversteher
Computerversteher
Beiträge: 373
Registriert: 20. Okt 2007 18:24
Wohnort: Höchst i. Odw

Re: Übung 2 - H2

Beitrag von s!mon »

Hm ich habe das nich komplett gelesen, stimmt :P

Ich kann nur trotzdem nochmal auf das Algorithmenbuch verweisen, in dem sogar ein Bsp mit +17 drin ist..

Benutzeravatar
Twister11
Mausschubser
Mausschubser
Beiträge: 48
Registriert: 26. Nov 2005 14:18
Kontaktdaten:

Re: Übung 2 - H2

Beitrag von Twister11 »

Na da freu ich mich ja das mein Posting nicht genau durchgelesen wird und dann irgendwas von "scheiss emos" planlos in den Raum gestellt wird :) ...aber das bin ich an der TUD auch schon lange gewöhnt, also insofern ==> who cares ^^

Was ist aber die Lösung für das Problem?
Das was hier mit "steht im Buch" gemeint ist bezieht sich wahrscheinlich auf Seite 63/64 und da steht bei Beispiel 1 das einfach mal
T(1)=1 angenommen wird... ach wie schön das das angenommen wird :)

Dann wird behauptet das das Beispiel mit der 17 ja völlig analog dazu wäre und es wird auf die Buchübungsaufgabe 4.1-5 verwiesen zu der es natürlich keine Lösung gibt :) SUPER !!!

Ich denke der Rekursionsanker ist genauso wesentlich wie die Rekurenzgleichung selbst. Das der nicht gegeben wird und da einfach so larifari drüber hinweggegangen wird sagt mir ds das Buch schrott ist, aber ich hab es ja zum Glück nicht gekauft :)

Was ist denn nun die Lösung des Problems? Ich kann ja auch einfachmal annehmen, das T(33) = 1 ist... so analog dazu wie das im Buch vorgeschlagen wird, nur hab ich das Gefühl das dann irgendwer auf die Idee kommen wird mir nicht volle Punkte für die Übung zu geben.
Das gleiche denke ich passiert wenn ich hinschreibe: Aufgrund mangelnder 'Verankerung' nicht lösbar ^^ :(

Benutzeravatar
Georg
Mausschubser
Mausschubser
Beiträge: 60
Registriert: 15. Okt 2007 19:02

Re: Übung 2 - H2

Beitrag von Georg »

wir sollen ja zum glück nur die obere schranke beweisen, daher vermittelt mir das Buch (keine ahnung, ob das so vorgesehen war), dass wir uns auch auf die höheren n beschränken (alles unter - erfinden wir mal eine völlig zusammenhanglose zahl - 35 ingorieren) können (dass eine implementation mit dieser laufzeitcharakteristik unweigerlich eine endlosschleife darstellt ignorieren wir mal)
Alle Angaben ohne Gewähr
_________________
"there is no such word as 'impossible' in my dictionary. In fact, everything between 'herring' and 'marmalade' appears to be missing"
-- Dirk Gently

Benutzeravatar
s!mon
Computerversteher
Computerversteher
Beiträge: 373
Registriert: 20. Okt 2007 18:24
Wohnort: Höchst i. Odw

Re: Übung 2 - H2

Beitrag von s!mon »

Ich habe nur gesehen, dass da viel Geheule war. Man doch auch normal Fragen ob da vielleicht ein Fehler drin ist..

Hast dus denn mal ausprobiert die Aufgaben wie in der Übung zu verifizieren? Das sollte ganz analog gehen. Abschätzen und so :P

Ich würde mich jetzt nicht zu weit aus dem Fenster lehnen, aber: Du sollst ja die Laufzeit berechnen und nicht zeigen, dass der Algorithmus korrekt terminiert. Das heißt für dich, dass du davon ausgehen kannst, dass es ein bestimmtes n gibt, für den das halt so ist (egal ob T(1) oder sonst was). Welches genau das ist, kann dir ja erstmal egal sein. Du zeigst nur, wie schnell generell die Rekursionstiefe ab- oder zunimmt usw..

edit: is quasi analog zu dem Post über mir was ich gemeint habe..

Benutzeravatar
taufrisch
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 107
Registriert: 30. Sep 2007 02:42
Wohnort: 127.0.0.1

Re: Übung 2 - H2

Beitrag von taufrisch »

Twister11 hat geschrieben:Ich denke der Rekursionsanker ist genauso wesentlich wie die Rekurenzgleichung selbst.
Ich würde mir mal das Mastertheorem durchlesen, und bevor ich das verstanden habe die Füße ganz still halten...
Premature optimization is the root of all evil.

Don't anthropomorphize computers: They hate that.

Benutzeravatar
Twister11
Mausschubser
Mausschubser
Beiträge: 48
Registriert: 26. Nov 2005 14:18
Kontaktdaten:

Re: Übung 2 - H2

Beitrag von Twister11 »

Ok, also hab mal nachgerechnet. Meine Rechnung ganz am Anfang stimmt nicht. Das ist alles noch ein wenig komplexer als ich dachte.
Für die Substitutionsmethode konnte ich keine Variante finden bei der man keinen Anker gebraucht hätte. Alle haben einen verwendet um das geratene mittels Induktion zu beweisen. Beim Master-Theorem kann man den wohl einfach ignorieren, denn es wird wohl angenommen das T(1), bzw. T(33) ..oder bei welchem T(q) sich die Rekursion, ...ich nenn es mal 'einpendelt'... ein beliebiger aber konstanter Wert herauskommt. ...und der macht den Bock net fett, aendert also nichts mehr an der Komplexitätsklasse.

Falls ich das so richtig sehe hätte ich mich gefreut wenn mir das einfach mal jemand erklärt hätte. Versteh garnicht warum ihr euch da so schützend vor die Veranstalter werft ohne scheinbar selber zu wissen warum man keinen Rekursionsanker braucht.
Angenommen einer von euch hätte es genau gewusst, was ja sein kann, dann frage ich mich weiter warum ihr es nicht einfach erklärt oder nen Tipp gebt und damit mein Problem aus der Welt schafft :P

Anmerkung:
Ich weiss zb. nicht ob es nicht auch Fälle gibt in denen Programme keinen Rekursionsanker besitzen (wozu auch immer das gut sein sollte...), aber Streams sind ja auch theoretisch von unendlicher länge, was weiss ich was es da noch so gibt. Ausserdem wurde das Master-Theorem ja soweit ich weiss nicht hergeleitet sondern nur aufgestellt und die Benutzung erklärt. Ich hab doch keine Ahnung ob es da Fälle geben kann in denen bestimmte 'Rekursionsanker' oder fehlende Rekursionsanker vielleicht doch noch was an der Komplexitätsklasse ändern können. Deshalb hätte ich es schon in Ordnung gefunden dazu nen genaueren Hinweis zu bekommen. Ich denke auch an das ich nicht der einzige Student bin der dadurch verwirrt wird.

Benutzeravatar
taufrisch
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 107
Registriert: 30. Sep 2007 02:42
Wohnort: 127.0.0.1

Re: Übung 2 - H2

Beitrag von taufrisch »

Twister11 hat geschrieben:Angenommen einer von euch hätte es genau gewusst, was ja sein kann, dann frage ich mich weiter warum ihr es nicht einfach erklärt oder nen Tipp gebt.
Kann es sein das Dir das schon mal jemand erklärt hat?
Twister11 hat geschrieben:Das hat mich schon bei der G2 aufgeregt, wobei der Tutor der Übungsgruppe verkaufen wollte das so ein Anker ja nicht notwendig wäre.
Ich glaube das Echo wäre viel freundlicher wenn Du einfach zugeben würdest, daß Du die die Aufgabe nicht verstanden hast, statt einen auf dicke Hose zu machen...
Premature optimization is the root of all evil.

Don't anthropomorphize computers: They hate that.

michael2k5
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 117
Registriert: 2. Dez 2005 19:22
Wohnort: Darmstadt-Eberstadt
Kontaktdaten:

Re: Übung 2 - H2

Beitrag von michael2k5 »

ich hab mich auch mal an dieser aufgabe versucht und irgendwie komme ich da auch nicht weiter mit dem buch.
im wikipedia steht da allerdings zum artikel zum mastertheorem eine ganz interessanter punkt unter "bemerkung"
http://de.wikipedia.org/wiki/Master-Theorem

hab im buch nach einer ähnlichen information gesucht, allerdings nichts gefunden. kann mir auch kaum vorstellen, wir die aufgab lösen können, indem wir sagen, dass gilt c = 0 für hinreichend große n. es ist inutitiv einsichtig, dass das für große n stimmt. wenn man aber die rekursionen ausführt sucht man vergeblich nach einem anker und gerät in die ENDLOSSCHLEIFE *seufz*

der andere ansatz, den ich im kopf hatte, wäre mit der variablentransformation, die auf s65 unten vorgestellt wird. damit und mit hilfe des mastertheorems könnte man zeigen, dass T(n) in O(nlgn) liegt zumindest für die substituierte variante. auch noch nicht so ganz schlüssig :(

Stumpf.Alex
Nerd
Nerd
Beiträge: 647
Registriert: 1. Okt 2007 12:40
Wohnort: Darmstadt
Kontaktdaten:

Re: Übung 2 - H2

Beitrag von Stumpf.Alex »

-- deleted --

Schädelkeks
Erstie
Erstie
Beiträge: 22
Registriert: 30. Apr 2004 14:24

Re: Übung 2 - H2

Beitrag von Schädelkeks »

In der Aufgabestellung zur G2 steht, dass man die Aufgabe mit der Substitutionsmethode lösen soll. Hierbei benötigt man dann auch keinen Rekursionsanker.

Die H2 soll wie ich das sehe dann auch mit der Substitutionsmethode gelöst werden.

michael2k5
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 117
Registriert: 2. Dez 2005 19:22
Wohnort: Darmstadt-Eberstadt
Kontaktdaten:

Re: Übung 2 - H2

Beitrag von michael2k5 »

zum induktiven beweis muss gezeigt werden, dass die abgeschätzte funktion die randbedingungen erfüllt.
herr buchmann hat in der vl als er die substitutionsmethode vorgestellt hat zb T(1) bis T(6) ausgerechnet und gezeigt, dass seine abschätzung damit funktioniert.
es ist tatsächlich so, dass die abschätzung nicht für alle n sondern erst für n ab einer hinreichenden größe zutreffen muss. deshalb können wir als randbedingung auch einfach T(1337) nehmen und zeigen, dass unsere abschätzung dafür stimmt.

das problem ist jetzt nur, dass wir kein T(n) ausrechnen können, da bei T(34) eine endlosschleife auftritt und auch keine sonstige randbedingung gegeben ist.
und ohne induktionsanfang kein vollständiger induktionsbeweis.

Benutzeravatar
taufrisch
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 107
Registriert: 30. Sep 2007 02:42
Wohnort: 127.0.0.1

Re: Übung 2 - H2

Beitrag von taufrisch »

michael2k5 hat geschrieben:das problem ist jetzt nur, dass wir kein T(n) ausrechnen können, da bei T(34) eine endlosschleife auftritt und auch keine sonstige randbedingung gegeben ist.
Bei Gleichungen gibt es keine Endlosschleifen. Du kannst getrost davon ausgehen, daß die Gleichung für n = 34 nicht gilt (hat was mit 0 != 34 zu tun), und also \(T(34) = \Theta(1)\) annehmen, wenn es dir bei der Lösung hilft auch \(T(34) = c\), siehe auch Abschnitt 2.3.2 in "Algorithmen - Eine Einführung".
Premature optimization is the root of all evil.

Don't anthropomorphize computers: They hate that.

Antworten

Zurück zu „Archiv“