laufzeit-notation bsp von alten prüfungsangaben [weitere]
Results 1 to 22 of 22
  1. #1

    Title
    Principal
    Join Date
    Jun 2002
    Location
    1040 vienna
    Posts
    91
    Thanks
    0
    Thanked 1 Time in 1 Post

    laufzeit-notation bsp von alten prüfungsangaben [weitere]

    gefragt sind jeweils

    a) f(n) = omega(g(n))
    b) f(n) = theta(g(n))
    c) f(n) = O(g(n))


    die angaben:
    f(n) steht in der ersten zeile
    g(n) drunter

    1)
    sqrt(n)
    750n
    2)
    2n^2
    5nlogn
    3)
    n^4 + 26n^3 + 6n^2 + n + 8
    100n^4
    4)
    n!
    7^n

    5)
    10^50 n log n
    0.00001n^2
    6)
    n^5-3n^4+4n^2-13
    35 sqrt(n) + 1/2 n^5
    7)
    sqrt(n)
    log(n)
    8)
    1/n
    e ^ -n

    x) neue aufgabe.
    28n^6 - 12n^2 + 14n - 13logn + 10 = theta(n^6)

    y)
    beweise oder wiederlege
    f(n) = O(sqrt(2)) <==> f(n) = O(pi)


    mfg .. vielleicht kennts ihr euch da aus.

    sony

  2. #2
    AntiBit's Avatar
    Title
    Baccalaureus
    Join Date
    Feb 2002
    Location
    Wien
    Posts
    738
    Thanks
    0
    Thanked 6 Times in 3 Posts
    Also ich hab da:

    1a)falsch
    1b)falsch
    1c)wahr

    2a)wahr
    2b)falsch
    2c)falsch

    3a)wahr
    3b)wahr
    3c)wahr

    4a)wahr
    4b)falsch
    4c)falsch

    Bsp x) Das ist wahr z.B. für alle n0 ab 1000, c1=1 und c2=33

    y) Keine Ahnung ?
    Hätten uns Spiele wie Pac-Man in unserer Jugend beeinflusst, würden wir heute durch dunkle Räume irren, elektronische Musik hören und Pillen fressen.

  3. #3
    Länz's Avatar
    Title
    Principal
    Join Date
    Feb 2002
    Posts
    78
    Thanks
    0
    Thanked 0 Times in 0 Posts
    also zu y würde ich sagen wahr, weil:

    pi =3.141....
    sqrt(2)=1.414.....

    wenn also die Wurzel aus 2 schon die obere Schranke von f(n) ist, dann ist pi die oberere Schranke
    0<=f(n)<=c*g(n)
    c*g(n) wird mit pi noch größer und somit ist die Ungleichung noch immer erfüllt.....

    erfüllt für z.B.: f(n)=12345678 (bzw irgendeine andere konstante Funktion)
    Last edited by Länz; 21-06-2002 at 00:36.

  4. #4
    bla's Avatar
    Title
    Master
    Join Date
    Jun 2002
    Posts
    174
    Thanks
    0
    Thanked 0 Times in 0 Posts
    angabe y muss in beide richtungen gelten oder?
    wenn ja dann stimmt die aussage nicht oder
    sonst stimmts auf jedenfall

  5. #5
    sCHmIkOla's Avatar
    Title
    Baccalaureus
    Join Date
    Feb 2002
    Posts
    532
    Thanks
    0
    Thanked 0 Times in 0 Posts
    ich denke antibit hat recht...so habe ich es auch gelöst

    bsp x habe ich auch so gelöst, jedoch etwas andere zahlen für c....is aber egal und bsp y ist falsch, weil es nur von li nach re gilt, aber nicht <==> ! weil wenn von F(n)=2 die obergrenze 3,14 ist stimmts noch, jedoch stimmt dann sqrt(2) nicht mehr als obergrenze!
    Last edited by sCHmIkOla; 21-06-2002 at 08:45.
    Der folgende Satz ist falsch,
    Der vorherige Satz ist richtig!

  6. #6

    Title
    Baccalaureus
    Join Date
    Feb 2002
    Posts
    780
    Thanks
    25
    Thanked 18 Times in 8 Posts
    4... wächst nicht die fakultät schneller als alles andere?

    dh. 7^n = O(n!)

    oder? das andere is falsch

    laborg

  7. #7
    sCHmIkOla's Avatar
    Title
    Baccalaureus
    Join Date
    Feb 2002
    Posts
    532
    Thanks
    0
    Thanked 0 Times in 0 Posts
    simmt n! wächst schneller als alles andere ....daher ist ja auch 7^n eine untergrenze von n!
    Der folgende Satz ist falsch,
    Der vorherige Satz ist richtig!

  8. #8

    Title
    Baccalaureus
    Join Date
    Feb 2002
    Posts
    780
    Thanks
    25
    Thanked 18 Times in 8 Posts
    5 c is auch noch wahr

  9. #9

    Title
    Baccalaureus
    Join Date
    Feb 2002
    Posts
    780
    Thanks
    25
    Thanked 18 Times in 8 Posts
    bei 6 müsste abc stimmen oder?

  10. #10

    Title
    Baccalaureus
    Join Date
    Feb 2002
    Posts
    780
    Thanks
    25
    Thanked 18 Times in 8 Posts
    und zu y: ich glaub das es eine wahre aussage ist:

    denn falsch <=> falsch stimmt ja


    oder?

    laborg

  11. #11

    Title
    Mag.rer.soc.oec
    Join Date
    Nov 2001
    Location
    dzt. München
    Posts
    1,270
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Original geschrieben von *]sCHmIkOla[*
    simmt n! wächst schneller als alles andere ....daher ist ja auch 7^n eine untergrenze von n!
    n^n wächst noch schneller als n!

  12. #12
    sCHmIkOla's Avatar
    Title
    Baccalaureus
    Join Date
    Feb 2002
    Posts
    532
    Thanks
    0
    Thanked 0 Times in 0 Posts
    natürlich ....sorry hab ich vergessen.....aber gleich nach n^n kommt n!

    und @laborg: zu y .....ist insgesamt falsch...weil wenn f(n) ist 2 ....dann stimmt die gremze für pi jedoch nicht für sqrt(2)!
    ODER?


    lg
    Der folgende Satz ist falsch,
    Der vorherige Satz ist richtig!

  13. #13
    Länz's Avatar
    Title
    Principal
    Join Date
    Feb 2002
    Posts
    78
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Original geschrieben von Länz
    also zu y würde ich sagen wahr, weil:
    0<=f(n)<=c*g(n)
    c*g(n) wird mit pi noch größer und somit ist die Ungleichung noch immer erfüllt.....
    also erstmal hab ich den Pfeil nur von li nach re gesehen, allerdings müsste es auch von re nach li passen, weil f(n) sowieso ein konstante Funktion (ohne n) sein muss und damit jede beliebige Zahl seine Ober Schranke sein kann......
    ich frage mich nur ob das Bsp sinnvoll ist, da ich für die beiden Schranken genausogut O(1) schreiben kann und die Frage dann trivial ist!

  14. #14
    shabby's Avatar
    Title
    Elite
    Join Date
    Jan 2002
    Location
    Schrödinger, 1040 Wien
    Posts
    267
    Thanks
    2
    Thanked 9 Times in 8 Posts
    warum sollte dass y nicht wahr sein ???

    f(x) = O(sqrt(2)) bedeutet ja nicht, dass die Wurzel 2 eine Oberschranke ist, sondern
    dass f(x) zu der Menge von Funktionen gehört
    die asymptotisch durch
    Wurzel 2 mal eine feste Konstante c
    beschränkt sind, also stellen alle O(Konstante) im Prinzip die selbe Schranke dar.

    wie schon erwähnt könntest genausogut
    f(x) = O(1) <==> f(x) = O(1)
    schreiben

  15. #15

    Title
    Baccalaureus
    Join Date
    Feb 2002
    Posts
    780
    Thanks
    25
    Thanked 18 Times in 8 Posts
    shabbys überlegung stimmt meines erachtens

    laborg

  16. #16
    sCHmIkOla's Avatar
    Title
    Baccalaureus
    Join Date
    Feb 2002
    Posts
    532
    Thanks
    0
    Thanked 0 Times in 0 Posts
    irgendwie schon....aber irgendwie nicht.....hmmm....jetzt bin i verwirrt....
    Der folgende Satz ist falsch,
    Der vorherige Satz ist richtig!

  17. #17
    AntiBit's Avatar
    Title
    Baccalaureus
    Join Date
    Feb 2002
    Location
    Wien
    Posts
    738
    Thanks
    0
    Thanked 6 Times in 3 Posts
    n^n wächst noch schneller als n!
    Das stimmt aber nur am Anfang. Für sehr grosse n wächst doch die Fakultät um einiges schneller, oder. Ich würd sagen dass unser Beispiel stimmt.

    Nimm mal an 7^1000 = 7*7*7*7*7*7*7*7*7*7..... bla bla

    Und 1000! = 1000*999*998*997*996.... bla bla

    Da ist doch sicher ! grösser und schneller.
    Last edited by AntiBit; 21-06-2002 at 11:50.
    Hätten uns Spiele wie Pac-Man in unserer Jugend beeinflusst, würden wir heute durch dunkle Räume irren, elektronische Musik hören und Pillen fressen.

  18. #18

    Title
    Mag.rer.soc.oec
    Join Date
    Nov 2001
    Location
    dzt. München
    Posts
    1,270
    Thanks
    0
    Thanked 0 Times in 0 Posts
    ich sagte ja N!!! ^n und nicht a^n

    bei deinem Bsp wäre das:

    1000^1000
    und
    1000! .... und da wächst ersteres schneller


    PS: hat aber nix mit dem Bsp zu tun, denn da wars a^n und das wächst langsamer als n! wie du richtig erkannt hast ... nur stimmt die aussage: nichts wächst schneller als n! eben nicht (und nur diese habe ich widerlegt)
    Last edited by phlow; 21-06-2002 at 12:02.

  19. #19

    Title
    Veteran
    Join Date
    Jun 2002
    Posts
    3
    Thanks
    0
    Thanked 0 Times in 0 Posts
    hmm mir kommt beim 2ten alles wahr raus. wie habts ihr das gerechnet?

  20. #20

    Title
    Mag.rer.soc.oec
    Join Date
    Nov 2001
    Location
    dzt. München
    Posts
    1,270
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Original geschrieben von SInc
    hmm mir kommt beim 2ten alles wahr raus. wie habts ihr das gerechnet?
    na jo:
    f(n)=2n²
    g(n)= 5*n log n

    ich berechne mal ob
    a) f(n) = omega(g(n))
    zutrifft:

    0<=c*g(n) <= f(n)
    0 <= c* (5*n log n) <= 2n² ...... /5*n log n
    0<= c <= 2n / 5 log n .... n wächst schneller als log n => der rechte teil geht für n=unendlich gegen unendlich => ich kann ein c finden das kleiner ist (=> a = korrekt) aber keines das grösser ist => b,c nicht korrekt



    b) f(n) = theta(g(n))
    c) f(n) = O(g(n))

  21. #21
    AntiBit's Avatar
    Title
    Baccalaureus
    Join Date
    Feb 2002
    Location
    Wien
    Posts
    738
    Thanks
    0
    Thanked 6 Times in 3 Posts
    ich sagte ja N!!! ^n und nicht a^n
    Aso hehe, ja ich hb mich verschaut. So gesehen hamma beide recht
    Hätten uns Spiele wie Pac-Man in unserer Jugend beeinflusst, würden wir heute durch dunkle Räume irren, elektronische Musik hören und Pillen fressen.

  22. #22

    Title
    Master
    Join Date
    Feb 2002
    Location
    irgendwo im nirgendwo
    Posts
    124
    Thanks
    3
    Thanked 0 Times in 0 Posts
    7) a wahr
    8) hm... auch a wahr

    x) is auf den ersten blick war da die höhe derpotenz der theta funktion zumindest gleich der, der anderen funkt. ist

    y) ist wahr...siehe shabbys erklärung
    'über das kommen mancher leute erfreut uns nichts mehr als das hoffen auf ihr gehen'
    __________________

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
  •