Übung 2 - H2

tmx-master
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 253
Registriert: 25. Okt 2006 17:44

Re: Übung 2 - H2

Beitrag von tmx-master »

Schädelkeks hat geschrieben: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.
Also das sehe ich auch so. Warum sonst hat man in der Übung 2 solcher Aufgaben gemacht? Es steht eben nur nicht explizit in der Aufgabenstellung. Im Cormen-Buch wird diese Aufgabe ja auch als Übung empfohlen.Und wir sollen das üben. Deshalb halte ich die ganzen Diskussionen hier fürwenig fruchtbar. Vielleicht sollte bei weiteren Fragen zur Substitutionsmethode ein neuer Thread aufgemacht werden, damit das von den Themen hier abgetrennt wird.
Gruß TM

Benutzeravatar
Panulli
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 110
Registriert: 20. Apr 2005 07:20

Re: Übung 2 - H2

Beitrag von Panulli »

Sollte nicht eine 2 vor dem T stehen??? Sonst komme ich doch nicht auf O(nlgn)...wäre dann O(n)...oder?!?
Grüßlich ULI

http://www.SGE4ever.de

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 »

O(n) ist doch in O(nlogn) falls du das rausbekommst (hab sie noch nicht gemacht, kann nich sagen was rauskommt)

verklixt1
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 156
Registriert: 29. Dez 2007 20:22

Re: Übung 2 - H2

Beitrag von verklixt1 »

Warum hört der Algorithmus ab T(34) nciht mehr auf????

Das verstehe ich nicht, wie kommt Ihr drauf????




MfG

Benutzeravatar
JanEisklar
Mausschubser
Mausschubser
Beiträge: 48
Registriert: 18. Okt 2007 13:29
Kontaktdaten:

Re: Übung 2 - H2

Beitrag von JanEisklar »

Frage: In Wikipedia steht beim Master-Theorem(http://de.wikipedia.org/wiki/Master_Theorem#Bemerkungen), dass für \(T(n) = a T(\textstyle \frac{n}{b}+c) + f(n)\) gilt:
Wenn n hinreichend groß gewählt wird, fällt die Konstante c nicht ins Gewicht. Aus diesem Grund kann man solche Rekurrenzen so behandeln, als wäre c=0.
Im Cormen wird dies nicht erwähnt, dürfen wir es trotzdem anwenden?

Benutzeravatar
plane
Computerversteher
Computerversteher
Beiträge: 337
Registriert: 21. Okt 2005 00:18

Re: Übung 2 - H2

Beitrag von plane »

Wird auch in Cormen erwähnt:

S64: "Die Intuition sagt uns jedich, dass dieser zusätzliche Term keinen substantiellen Effekt auf die Lösung der Rekursionsgleichung ausüben kann."

Ich denke, der Satz ist ähnlich zu dem aus Wikipedia...

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

Re: Übung 2 - H2

Beitrag von Georg »

problem: wie hilft unsere intuition, das formal brauchbar zu beweisen?
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

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

Re: Übung 2 - H2

Beitrag von Stumpf.Alex »

Für das Mastertheorem direkt noch nichts, aber für die Substitutionsmethode...durch eine geschickt gewählte Substitution ist die Aufgabe definitv beweisebar, wenn man dann zum Schluss die Gültigkeit der Randbedingungen zeigen kann.

Student20
Mausschubser
Mausschubser
Beiträge: 89
Registriert: 2. Jun 2006 14:41

Re: Übung 2 - H2

Beitrag von Student20 »

Hallo,

habe eine Frage zur H2:


Kann mir jemand bitte erklären, wie man von 2cn/3lg3/2 größer gleich n auf c größer gleich 9 kommt?

Irgendwie stehe ich auf dem Schlauch... .
Wäre echt dankbar, wenn mir jemand helfen könnte :D .

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 »

Brauchst ja keine genaue Schranke sondern kannst das was du da als Bruch hast nochmal großzügig abschätzen

Benutzeravatar
Jo(h)nny
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 197
Registriert: 19. Dez 2007 23:39

Re: Übung 2 - H2

Beitrag von Jo(h)nny »

nun ja sie haben umgeformt, man erhält dann c >= 3 / (2 * lg(3/2)) also c >= 8,5.... und dann auf 9 aufrunden:)
Atomenergie ist wie Sex - im Prinzip genial, wenn man nur wüsste wohin mit den Endprodukten.

Antworten

Zurück zu „Archiv“