[FRAGE] - Theta-Notation
Results 1 to 21 of 21

Thread: Theta-Notation

  1. #1
    fraka79

    Theta-Notation

    kann mir jemand bei flg. helfen

    2^n = Theta(pi^n)

    ist das wahr oder falsch?

  2. #2
    Bomple's Avatar
    Title
    Elite
    Join Date
    Mar 2002
    Location
    Wien
    Posts
    333
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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

  3. #3
    fraka79
    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?????

  4. #4

    Title
    Dipl.Ing
    Join Date
    Mar 2002
    Location
    Wien 12
    Posts
    1,135
    Thanks
    72
    Thanked 366 Times in 208 Posts
    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).

  5. #5

    Title
    Veteran
    Join Date
    May 2002
    Posts
    12
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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).

  6. #6

    Title
    Dipl.Ing
    Join Date
    Mar 2002
    Location
    Wien 12
    Posts
    1,135
    Thanks
    72
    Thanked 366 Times in 208 Posts
    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.
    Last edited by yrucrem; 20-05-2002 at 22:23.

  7. #7

    Title
    Elite
    Join Date
    Jan 2002
    Posts
    314
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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...
    hi, i'm a signature virus. copy me into your signature to help me spread.

  8. #8
    tricipitinus's Avatar
    Title
    Baccalaureus
    Join Date
    Feb 2002
    Location
    Purkersdorf bei Wien
    Posts
    598
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Question

    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?
    ash nazg durbatulûk, ash nazg gimbatul,
    ash nazg thrakatulûk, agh burzum-ishi krimpatul.

  9. #9
    Fugo's Avatar
    Title
    Baccalaureus
    Join Date
    Sep 2005
    Posts
    855
    Thanks
    26
    Thanked 14 Times in 4 Posts
    Hmm... meine Überlegung: f(n) geht gegen minus Unendlich... daher kann ich kein c1 finden, so dass die Bedingung erfüllt ist.



  10. #10
    Christoph R.'s Avatar
    Title
    Dipl.Ing
    Join Date
    Oct 2005
    Posts
    2,343
    Thanks
    74
    Thanked 255 Times in 145 Posts
    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

  11. #11
    Swoncen's Avatar
    Title
    Dipl.Ing
    Join Date
    Oct 2005
    Location
    Vienna
    Posts
    2,793
    Thanks
    8
    Thanked 2 Times in 2 Posts
    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?
    640K ought to be enough for anybody.

  12. #12
    Paulchen's Avatar
    Title
    Super Moderator
    Join Date
    Oct 2004
    Location
    /home/paulchen
    Posts
    8,097
    Thanks
    1,943
    Thanked 1,460 Times in 998 Posts
    Quote Originally Posted by Swoncen
    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.

  13. #13
    Swoncen's Avatar
    Title
    Dipl.Ing
    Join Date
    Oct 2005
    Location
    Vienna
    Posts
    2,793
    Thanks
    8
    Thanked 2 Times in 2 Posts
    Danke!
    Ja das war mir eh klar.. trivial, aber zurück zu Christophs Frage.. =)
    640K ought to be enough for anybody.

  14. #14
    Paulchen's Avatar
    Title
    Super Moderator
    Join Date
    Oct 2004
    Location
    /home/paulchen
    Posts
    8,097
    Thanks
    1,943
    Thanked 1,460 Times in 998 Posts
    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.)

  15. #15
    Swoncen's Avatar
    Title
    Dipl.Ing
    Join Date
    Oct 2005
    Location
    Vienna
    Posts
    2,793
    Thanks
    8
    Thanked 2 Times in 2 Posts
    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.
    640K ought to be enough for anybody.

  16. #16
    Paulchen's Avatar
    Title
    Super Moderator
    Join Date
    Oct 2004
    Location
    /home/paulchen
    Posts
    8,097
    Thanks
    1,943
    Thanked 1,460 Times in 998 Posts
    Quote Originally Posted by Swoncen
    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.

  17. #17

    Title
    Elite
    Join Date
    Dec 2005
    Posts
    384
    Thanks
    0
    Thanked 2 Times in 1 Post
    Quote Originally Posted by Swoncen View Post
    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

  18. #18
    Beppo's Avatar
    Title
    Elite
    Join Date
    May 2006
    Posts
    307
    Thanks
    14
    Thanked 2 Times in 2 Posts
    Naja, "keines" wäre z.B. wenn die eine Funktion keine Untergrenze hat und die andere keine Obergrenze.

  19. #19

    Title
    Elite
    Join Date
    Dec 2005
    Posts
    384
    Thanks
    0
    Thanked 2 Times in 1 Post
    Quote Originally Posted by Beppo View Post
    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

  20. #20
    Beppo's Avatar
    Title
    Elite
    Join Date
    May 2006
    Posts
    307
    Thanks
    14
    Thanked 2 Times in 2 Posts
    @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.

  21. #21

    Title
    Elite
    Join Date
    Dec 2005
    Posts
    384
    Thanks
    0
    Thanked 2 Times in 1 Post
    Quote Originally Posted by Beppo View Post
    @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)

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •