View Full Version : [FRAGE] - Theta-Notation
kann mir jemand bei flg. helfen
2^n = Theta(pi^n)
ist das wahr oder falsch?
müsste falsch sein...
meines erachtens nach findest du keine zahl mit der du pi^n multiplizieren kannst so dass 2^n immer kleiner ist... pi^n wächst einfach viel schneller an als 2^n
zb:
c1 = 0,1
n = 1
c2 = 5
weiß dass es schneller wächst, daher ist es ja auch nur für kl. n möglich wenn überhaupt, aber es geht ja nur darum ob es generell gehen würde!!!!!oder?????
Die Definition der Theta-Notation besagt, dass es fuer ALLE n >= einem Index n0 gelten muss. Dass es fuer (endlich viele) kleine n geht, ist nicht wichtig, es muss fuer _fast alle_ n gelten.
Die Aussage ist also falsch (wenn du statt dem pi, 3 einsetzt, kommst du uebrigens auf die Angabe eines der Uebungsblaetter).
MrFloppy
19-05-2002, 14:49
Genau das hab ich bei der Prüfung auch hingeschrieben. 0<=c1.pi^n<=2^n<=c2.pi^n nicht möglich da pi^n schneller wächst und somit die Theta-Notation nicht gültig ist. Reicht das als Anwort? (habe noch angemerkt, dass Pi = 3,1.... ist).
Eigentlich formt, man die Ungleichung noch ein bisschen um, um eben zu zeigen, dass das eine schneller waechst.
Zuerst dividiert man so, dass die Konstanten c1 und c2 alleine auf ihren Seiten stehen ->
c1 <= (2^n) / (pi^n) <= c2
Das kann man noch etwas umformen:
c1 <= (2 / pi)^n <= c2
Der Ausdruck (2 / pi)^n mit n gegen undendlich divergiert, dass heiszt man kann kein c2 finden, dass immer groesser ist als der Ausdruck.
Das waere der komplete formelle Beweis.
/edit 20.05.02:
Uups. Siehe den naechsten Post. Chris hat natuerlich recht.
sorry, wenn ich jetzt total auf der leitung stehe...
aber (2 / pi)^n für n gegen unendlich konvergiert doch gegen null, oder?
also würde ich eher sagen, dass man kein c1>0 finden kann, so dass der ausdruck für fast alle n gilt...
tricipitinus
25-04-2006, 20:02
was ist mit beispiel 1a) von der Prüfung am 27.Jänner 2005
f(n)=theta(n^3)
f(n)= 2/3n^3 - 7n² + sqrt(1/2n)
wenn ich nicht irgend einen denkfehler mache, kommt bei meiner umformung raus:
0<=c1<=2/3 - 7/n + sqrt2 *n<=c2
was heissen würde, dass f(n)!=theta(n^3), da sqrt2*n und es somit kein gültiges c2 gibt.
schön und gut, aber im schnellverfahren sagt man doch eig., die höchste potenz ist mein theta - macht uns die wurzel hier einen strich durch die rechnung oder mach ich irgendwo einen denkfehler?
Hmm... meine Überlegung: f(n) geht gegen minus Unendlich... daher kann ich kein c1 finden, so dass die Bedingung erfüllt ist.
Christoph R.
25-04-2006, 23:06
Ich habe da zu den Notationen noch eine prinzipielle Frage: laut Skriptum muss doch gelten dass 0 <= c1*g(n) <= f(n) <= c2*g(n) ist (bzw. bei Omega und O halt nur eine Grenze). Das wesentliche ist aber das 0 <= f(n). D.h. wenn f(n) < 0 ist kann es weder Omega, O noch Theta sein. Aber in Theoretische Informatik 1 ist heute auch kurz diese Notation angesprochen worden, und da wurde statt f(n) der Betrag von f(n) genommen, was das Ergebnis bei negativen f(n) natürlich ändern würde.
Weiß jemand warum?
Im Zweifelsfall werde ich mich an die Notation aus dem AlgoDat-Skriptum halten (finde ich auch logischer, weil negative Laufzeiten imho keinen Sinn machen).
mfg
Ich verstehs auch nicht was das zu beudeuten hatte. Ich hab noch eine zusätzliche Frage: Was ist, wenn ich eine Funktion hab und es stehen zwei Funktionen, die eine für n=gerade und die eine für n=ungerade.. was muss man dann machen? Nur O,Omega,Theta eintragen, wenns für beide Funktionen drinnen liegt?
Paulchen
25-04-2006, 23:20
Nur O,Omega,Theta eintragen, wenns für beide Funktionen drinnen liegt?ja.
wenn aber z.B. ein ausdruck für n<100 und einer für n>=100 gegeben sind, dann ist nur jener für n>=100 relevant, da die bedingungen für O, Theta bzw. Omega ohnehin erst ab einem bestimmten N gelten müssen, und es kann ja ohne weiteres N>100 gelten.
Danke!
Ja das war mir eh klar.. trivial, aber zurück zu Christophs Frage.. =)
Paulchen
26-04-2006, 00:11
Die Landau-Notation wird ursprünglich dazu verwendet, das asymptotische Verhalten zweier Funktionen zueinander zu beschreiben. Dabei bedeutet "f(x) liegt in Theta(g(x))" grundsätzlich, dass f und g gleiches asymptotisches Verhalten aufweisen, beispielsweise dass lim f(x)=unendlich impliziert, dass auch lim g(x)=unendlich ist. Dieses asymptotische Verhalten kann natürlich auch für Funktionen betrachtet werden, die (uneigentlich) gegen einen negativen Wert konvergieren. So liegt auch -x intuitiv in Theta(-x).
Nur wäre das mit der Definition, die in AlgoDat präsentiert wird, nicht möglich, weil dazu die Werte beider Funktionen ab einem bestimmten N alle größer als 0 sein müssten. Wenn man allerdings (für die Werte beider Funktionen!) Beträge einführt verwendet, hat man dieses Problem beseitigt, und der Vergleich des asymptotischen Verhaltens der beiden Funktionen ist wieder sinnvoll möglich.
Die Verwendung der Landau-Notation für die Beschreibung des asymptotischen Laufzeitverhaltens von Algorithmen ist lediglich eine Anwendung; mit der Eigenschaft, dass negative Laufzeiten keinen Sinn machen. Daher kann man die Beträge für diese Anwendung beiseite lassen.
Siehe auch http://de.wikipedia.org/wiki/Landau-Notation.
(Ich hab versucht, das einigermaßen verständlich zu erklären, man zerfleische mich nicht, wenn ich nicht mathematisch korrekt argumentiere.)
Danke, war verständlich. Also ist es richtig, dass es in der Laufzeitberechnung kein sin oder cos o.ä geben kann, da diese auch ins negative gehen und es gibt keine Negative Laufzeit. Trotzdem kanns auch Theta(-n) in anderen Bereichen geben, wo diese Notation eingesetzt wird. So hab ich das jetzt verstanden.
Paulchen
26-04-2006, 00:39
Danke, war verständlich. Also ist es richtig, dass es in der Laufzeitberechnung kein sin oder cos o.ä geben kann, da diese auch ins negative gehen und es gibt keine Negative Laufzeit. Trotzdem kanns auch Theta(-n) in anderen Bereichen geben, wo diese Notation eingesetzt wird. So hab ich das jetzt verstanden.korrekt.
Ich verstehs auch nicht was das zu beudeuten hatte. Ich hab noch eine zusätzliche Frage: Was ist, wenn ich eine Funktion hab und es stehen zwei Funktionen, die eine für n=gerade und die eine für n=ungerade.. was muss man dann machen? Nur O,Omega,Theta eintragen, wenns für beide Funktionen drinnen liegt?
hab dazu auch noch eine frage...bei solchen funktionen kanns eigendlich kein keines geben oder
weil entweder liegts drunter oder drüber oder genau irgendwie in der meißt stark springenden Funktion.
Wann kann eigendlich "keines" gelten? kann da irgendwie mir keinen fall vorstellen
Danke
Naja, "keines" wäre z.B. wenn die eine Funktion keine Untergrenze hat und die andere keine Obergrenze.
Naja, "keines" wäre z.B. wenn die eine Funktion keine Untergrenze hat und die andere keine Obergrenze.
wie sollte das gehen es ist ja nur EINE funktion die entweder eine unter/ober oder theta grenze haben kann
@sepp13
Sry, dachte mir du meinst jetzt allgemein. Wenn nur eine Funktion gegeben ist dann muss es entweder eine Ober- oder eine Untergrenze bzw. Beides geben. Also ein Fall wo nichts gilt, bei einer Funktion ,fällt mir nicht ein.
@sepp13
Sry, dachte mir du meinst jetzt allgemein. Wenn nur eine Funktion gegeben ist dann muss es entweder eine Ober- oder eine Untergrenze bzw. Beides geben. Also ein Fall wo nichts gilt, bei einer Funktion ,fällt mir nicht ein.
ja mir auch nicht weil bei den prüfungasangaben eben immer die möglichkeit keines angegeben wird und ich halt nicht sehe wann das der fall sein sollte
(bei den Aufgaben wo man ankreuzen soll)
vBulletin® v3.7.1, Copyright ©2000-2008, Jelsoft Enterprises Ltd.