Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Rekursive Zeitgleichungen

Rekursive Zeitgleichungen

Universität / Fachhochschule

Sonstiges

Tags: Algorithmen, Mastertheorem, O-Notation, Omega-Notation, Rekursive Zeitgleichung, Theta-Notation

techniker123

16:28 Uhr, 18.06.2014

Hallo Zusammen!

Ich sitze gerade an einer Übungsaufgabe zur Prüfungsvorbereitung. Da ist mir folgende Frage untergekommen und ich komme einfach auf kein vernünftiges Ergebnis.

Gegeben ist folgende rekursive Zeitgleichung:

T (n) = T (n - \sqrt{n})

.

Gesucht ist die genaue asymptotische Schranke von

T (n)

\in θ (?)

. Das Master-Theorem ist hier ja nicht anwendbar, da die Zeitgleichung ganz und gar nicht die Form

T (n) = a \cdot T (\frac{n}{b}) + f (n)

hat. Da bleibt nur noch die Möglichkeit des iterativen Einsetzens oder eine Schranke "erraten" und mit Induktion zu beweise. Letzteres ist jedoch zum finden der Theta-Schranke relativ schwierig, weshalb ich mit der iterativen Methode begonnen habe:

T (n) = T (n - \sqrt{n}) = T (n - n^{\frac{1}{2}})

T (n - n^{\frac{1}{2}}) = T (n - n^{\frac{1}{2}} - (n - n^{\frac{1}{2}})^{\frac{1}{2}})

.

Ich möchte ja nicht so schnell aufgeben, aber ich glaube kaum, dass dies hier zu einem guten Ergebnis führt.
Kann mir vielleicht jemand einen Tipp geben, ob ich auf dem richtigen Weg bin, und wenn ja, wie man da weiter macht bzw. wenn nicht, wie man so ein Problem angeht.

Wo ich jetzt schon dabei bin, ist mir auch noch ein ähnliches Beispiel unter gekommen:

T (n) = T (n - \log (n))

.

Same here: ich glaube ich steh auf der Leitung... ;-)

Danke und LG

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."

Hierzu passend bei OnlineMathe:

Zu diesem Thema passende Musteraufgaben einblenden

Herleitung der Kreiszahl Pi

Wie kann man die Kreiszahl

π

herleiten?

DrBoogie aktiv_icon

12:48 Uhr, 19.06.2014

In beiden Fällen ist

T (n) = θ (n)

, dass kann man durch Induktion zeigen.

techniker123

12:54 Uhr, 19.06.2014

Danke für deine schnelle Antwort!

Das bedeutet also, dass man solche Zeitgleichungen also nur durch "gezieltes Raten" lösen kann? User Prof. ist jedoch sehr kreativ. Und bei der Prüfung mit irgendwelchen Annahmen anzufangen könnte auch nach hinten los gehen, wie ich befürchte. Kann ich also davon ausgehen, dass Zeitgleichungen dieser Form:

T (n) = T (n - f (n))

oft

\in Θ (n)

sind? Ich meine jetzt keine Verallgemeinerung, nur so als Tipp, ob es eine gute Idee ist, mit diesem Ansatz zu beginnen.

Wie geht man hier dann vor? Mache ich das so richtig? Wenn ich zeigen will, dass

T (n) \in Θ (n)

gilt, kann ich dies ja aufteilen und zeigen, dass sowohl

T (n) \in O (n)

als auch

T (n) \in Ω (n)

gilt. Also fange ich also an.
Lt. Definition gilt ja:

f \in O (g) : \exists c > 0, \exists n_{0} > 0, \forall n > n_{0} : ∣ f (n) ∣ \leq c \cdot ∣ g (n) ∣

.

Und ich stelle die Annahme, dass:

T (n) \in O (n)

.

Also muss gelten (n>0):

T (n) \leq c \cdot ∣ n - \log (n) ∣ = c \cdot n - c \cdot l o g (n) \leq c \cdot n \in O (n)

.
Kann man das so sagen? Kommt mir irgendwie nicht ganz korrekt vor.

Aber machen wir mal weiter... das selbe macht man dann für

Ω

:
Lt. Definition gilt ja:

f \in Ω (g) : \exists c > 0, \exists n_{0} > 0, \forall n > n_{0} : ∣ f (n) ∣ \geq c \cdot ∣ g (n) ∣

.

Und ich stelle die Annahme, dass:

T (n) \in Ω (n)

.

Also muss gelten:

T (n) \geq c \cdot ∣ n - \log (n) ∣ = ∣ c \cdot n - c \cdot l o g (n) ∣ \geq ∣ c \cdot n ∣ - ∣ c \cdot \log (n) ∣ \in Ω (n)

.

Und dadurch gilt,

T (n) \in Θ (n)

? Irgendetwas stimmt hier glaube ich noch nicht. Vielleicht könnt ihr mir ja ein klein wenig weiterhelfen...

LG

DrBoogie aktiv_icon

14:55 Uhr, 19.06.2014

"Kann ich also davon ausgehen, dass Zeitgleichungen dieser Form:

T (n) = T (n - f (n))

oft

\in Θ (n)

sind?"

Wenn

f (n)

"klein" im Vergleich zu

n

ist, dann ja.

Für

f (n) = \log (n)

kann man z.B. nutzen, dass

\log (n) < \frac{n}{2}

für alle

n

's,
deshalb

\frac{n}{2} < n - \log (n) < n

für alle

n

's.

Sonst scheint mir Deine Argumentation OK zu sein, allerdings kenne ich mich mit diesem Thema nicht wirklich aus. Wie wurde denn das Master-Theorem bewiesen?

techniker123

15:43 Uhr, 19.06.2014

Oh... Beweis davon finde ich nicht mal im Skriptum (ist eigentlich sehr untypisch für diesen Prof., nehme mal an, dass ist nicht ganz so trivial zu zeigen).
Hier der Wiki-Eintrag dazu: de.m.wikipedia.org/wiki/Master-Theorem

Danke für deine Hilfe!

DrBoogie aktiv_icon

17:12 Uhr, 19.06.2014

Ach so. Dann ist die Sache komplizierter als ich dachte und meine Ideen wohl falsch.
Aber da hast Du ja das allgemeine Resultat:
http//de.m.wikipedia.org/wiki/Akra-Bazzi-Theorem
Deine Fälle fallen auch darunter, z.B. für

T (n) = T (n - \log (n))

musst Du

g = 0, k = 1, a_{1} = 1, b_{1} = 1

und

h_{1} = - \log

wählen (das Theorem sagt in diesem Fall:

T (n) = θ (n)

)

techniker123

17:27 Uhr, 19.06.2014

Das Akra-Bazzi-Theorem wollte ich auch schon verwenden, nur steht ja, dass

0 < b_{i} < 1

sein soll, wobei bei diesem Bsp.

b_{i} = 1

sein müsste. Daher kann ich es hier ja nicht anwenden, oder sehe ich das falsch?

Laut Wiki gilt ja für eine Zeitgleichung der Form:

T (x) = g (x) + \sum_{i = 1}^{k} a_{i} T (b_{i} x + h_{i} (x))

für

x \geq x_{0}

.
Unter den Vorraussetzungen:

\to

a_{i}

und

b_{i}

konstant

\forall i

\to

a_{i} > 0 \forall i

\to

0 < b_{i} < 1 \forall i

\gets

P r o b l e m . . .

\to

usw...

DrBoogie aktiv_icon

17:45 Uhr, 19.06.2014

"Daher kann ich es hier ja nicht anwenden, oder sehe ich das falsch?"

Direkt wohl nicht. Aber vielleicht kann der Beweis trotzdem benutzt werden.

techniker123

18:11 Uhr, 19.06.2014

Danke soweit!

Vielleicht stolpert ja noch jemand über dieses Thema, der sich häufiger mit solchen Problemen beschäftigen muss/darf/soll und einen Hinweis hat... ;-)
Ich glaube nämlich nicht, dass diese Art von Problemen derart schwierig zu lösen sind, da so ein Bsp. einen Unterpunkt eines Unterpunktes einer

90

Minuten dauernden Prüfung darstellt und es daher dafür vermutlich einen "Trick" gibt.

LG

Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.

1173625

1173452

	Status: nicht eingeloggt	Noch nicht registriert?