O-Notation Bsp von alten prüfungsangaben
Results 1 to 17 of 17
  1. #1

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

    O-Notation Bsp von alten prüfungsangaben

    peace,

    aus den alten prüfungsangaben, zum thema o-notation. was ist richtig?

    1) aus f(n) = O(g(n)) folgt g(n) = O(f(n))
    imho: falsch

    2) f(n) = O(g(n)) --> 20f(n) = O(1/2 g (n))
    imho: wahr

    3) f(n) = O(5g(n)) --> g(n) = Omega(5f(n))
    imho: falsch

    4)f(n) = theta(g(n)) --> g(n) = omega(f(n))
    imho: wahr

    5)f(n) = omega(g(n)) --> f(n) = omega(n/1000 g(n)).
    imho: no comment

    6) f(n) + g(n) = theta(min(f(n),g(n)))
    imho: falsch

    7) f(n) = O((f(n)^2)
    imho: wahr

    8) f(n) = theta(f(n/2))
    imho: falsch

    9) f(n) = O(g(n)) --> log2(f(n)) = O(log2(g(n)))
    für log2(g(n)) > 0 und f(n) >= 1
    imho: questionmark

    anmerkung: ich hab nicht lange überlegt sondern spontan meine meinung dazugeschreibt.

    bitte miträtseln!

    mfg
    sony

  2. #2
    andras98's Avatar
    Title
    Baccalaureus
    Join Date
    Feb 2002
    Posts
    664
    Thanks
    4
    Thanked 0 Times in 0 Posts
    2) f(n) = O(g(n)) --> 20f(n) = O(1/2 g (n))
    imho: wahr

    Falsch

    n^2=O(n^3) => 20n^2=O(1/2 n^3)
    4 = 8 80 = 4


    3) f(n) = O(5g(n)) --> g(n) = Omega(5f(n))
    imho: falsch

    Wahr

    5) wahr warum no comment?

    7) Falsch

    8) Wahr

    9) Wahr

  3. #3
    steve's Avatar
    Title
    Baccalaureus
    Join Date
    Jan 2002
    Location
    planet earth
    Posts
    539
    Thanks
    14
    Thanked 2 Times in 2 Posts
    meine meinung:

    2) wahr (stimmt schon, denn du musst eine multiplikative konstante c auch mitberücksichtigen)
    3) wahr
    5) könnt falsch auch sein (1/1000 * n*g(n); das 1/1000 ist wurscht weil du ja eine multiplikative konstante miteinfließen lassen kanst)

    7) ist wahr, warum sollt das falsch sein?
    8) falsch (meiner meinung nach...)
    9) wahr

    vorschläge?
    -----BEGIN GEEK CODE BLOCK-----
    Version: 3.12
    GAT d-(+) s++: a- C++$>+$ U++>+++ P++>+++ L+++ !E W++>$ !N K? w(--)@ !O !M V? PS+ PE++(-)> Y+ PGP(+) t---(-) !5 X R- tv-(--) b++>$ DI+ D+(++) G(+) e>++++* h-- r++ y++
    ------END GEEK CODE BLOCK------ .

  4. #4

    Title
    Böser Wolf
    Join Date
    May 2002
    Location
    Institut 186
    Posts
    814
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Darf ich mitraten?

    Falsch: 1, 2, 5, 6, 7, 8
    Richtig: 3 4, 9

    Gegenbeispiele für die falschen Behauptungen:
    1: f(n) = 1, g(n) = n
    2: f(n) = g(n) = 2^n
    5: f(n) = g(n) = 1
    6: f(n) = 1, g(n) = n
    7: f(n) = 1/n
    8: f(n) = 2^n

    Grüße,
    Georg

  5. #5

    Title
    Hero
    Join Date
    Feb 2002
    Location
    Wien
    Posts
    185
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Original geschrieben von Georg Kraml
    5: f(n) = g(n) = 1
    wieso ist das falsch?
    5)f(n) = omega(g(n)) --> f(n) = omega(n/1000 g(n)).
    0 <= 1 <= (1/1000)*1*c stimmt doch oder?

  6. #6

    Title
    Böser Wolf
    Join Date
    May 2002
    Location
    Institut 186
    Posts
    814
    Thanks
    0
    Thanked 0 Times in 0 Posts
    > wieso ist das falsch?
    > 5)f(n) = omega(g(n)) --> f(n) = omega(n/1000 g(n)).

    Angenommen, f(n) = g(n) = 1.
    Dann wird die Behauptung

    f(n) = omega(g(n)) --> f(n) = omega(n/1000 g(n))

    zu

    1 = omega(1) --> 1 = omega(n/1000 * 1)

    Die Voraussetzung 1 = omega(1) ist trivialerweise richtig, die
    Folgerung 1 = omega(n/1000 * 1) ist trivialerweise falsch.
    Damit ist die Implikation durch Gegenbeispiel widerlegt.

    Grüße,
    Georg

  7. #7
    alpi's Avatar
    Title
    Elite
    Join Date
    Mar 2002
    Location
    Vienna/NYC
    Posts
    284
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Original geschrieben von Georg Kraml
    2: f(n) = g(n) = 2^n
    hmm entweder mach ich was falsch oder bei mir funktioniert das Gegenbeispiel mit 2^n nicht...

    HEEEEEEEEEEEEEELP

    alpi 8)

  8. #8
    shabby's Avatar
    Title
    Elite
    Join Date
    Jan 2002
    Location
    Schrödinger, 1040 Wien
    Posts
    267
    Thanks
    2
    Thanked 9 Times in 8 Posts
    Original geschrieben von alpi


    hmm entweder mach ich was falsch oder bei mir funktioniert das Gegenbeispiel mit 2^n nicht...

    Kann es auch nicht.
    f(n) <= c1 * O(g(n))

    Wähle c1 so, dass die Aussage auch für alle c1/40 gilt, also 40 mal so groß wie nötig.
    (c1 darf ja beliebig groß (aber fest) gewählt werden )

    c2 definiert durch c1/40

    dann folgt aus einer einfachen Multiplikation !!

    20 f(n) <= c2 / 2 * O(g(n))

    keine Ahnung woher das Gegenbeispiel kommt.

  9. #9

    Title
    Böser Wolf
    Join Date
    May 2002
    Location
    Institut 186
    Posts
    814
    Thanks
    0
    Thanked 0 Times in 0 Posts
    > keine Ahnung woher das Gegenbeispiel kommt.

    Mein Fehler. Das Gegenbeispiel ist stuß. Die fragliche Behauptung ist nicht falsch, sondern wahr -- wie shabby ja schon gezeigt hat.

    Grüße,
    Georg

  10. #10

    Title
    Baccalaureus
    Join Date
    Feb 2002
    Posts
    780
    Thanks
    25
    Thanked 18 Times in 8 Posts
    Original geschrieben von Georg Kraml

    Folgerung 1 = omega(n/1000 * 1) ist trivialerweise falsch.
    entspricht 1 e omega(n) oder?

    wenn man stur einsetzt:

    0<=1<=n*c

    was stimmt daran nicht???

    n ist doch obere schranke von 1

  11. #11

    Title
    Hero
    Join Date
    Feb 2002
    Location
    Wien
    Posts
    185
    Thanks
    0
    Thanked 0 Times in 0 Posts
    du hast da den gleichen fehler gemacht wie ich vorher. omega ist die _untere_ schranke, nicht die obere.

    also 0 <= c*n <= 1, und das stimmt trivialerweise nicht.

  12. #12

    Title
    Principal
    Join Date
    Jan 2002
    Posts
    46
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Original geschrieben von Georg Kraml
    > keine Ahnung woher das Gegenbeispiel kommt.

    Mein Fehler. Das Gegenbeispiel ist stuß. Die fragliche Behauptung ist nicht falsch, sondern wahr -- wie shabby ja schon gezeigt hat.

    Grüße,
    Georg
    2) f(n) = O(g(n)) --> 20f(n) = O(1/2 g (n))
    f(n)=g(n)=2^n

    2^n=O(2^n) wahr
    20*2^n=O(1/2*2^n) falsch
    weil
    5*2*2*2^n=O(1/2*2^n)
    5*2^(n+2)=O(2^(n-1))
    folglich falsch
    -----------------

  13. #13

    Title
    Baccalaureus
    Join Date
    Feb 2002
    Posts
    780
    Thanks
    25
    Thanked 18 Times in 8 Posts
    Original geschrieben von Lukas
    du hast da den gleichen fehler gemacht wie ich vorher. omega ist die _untere_ schranke, nicht die obere.

    also 0 <= c*n <= 1, und das stimmt trivialerweise nicht.
    asso... . naja.. .hat mich ein bisschen durcheinander gebracht die notation... also einmal O dann omega dann ... tja ... ich bin für OHM als untereschranke... wurscht...
    wenns so is is natürlich kein problem

    laborg

  14. #14

    Title
    Baccalaureus
    Join Date
    Feb 2002
    Posts
    780
    Thanks
    25
    Thanked 18 Times in 8 Posts
    Original geschrieben von andy


    2) f(n) = O(g(n)) --> 20f(n) = O(1/2 g (n))
    f(n)=g(n)=2^n

    2^n=O(2^n) wahr
    20*2^n=O(1/2*2^n) falsch
    weil
    5*2*2*2^n=O(1/2*2^n)
    5*2^(n+2)=O(2^(n-1))
    folglich falsch
    -----------------
    aehm??? und was is wenn ich 2^(n-1) mit sagen wir 60 multipliziere? ... jo so einfach geht des ned...

  15. #15

    Title
    Baccalaureus
    Join Date
    Feb 2002
    Posts
    780
    Thanks
    25
    Thanked 18 Times in 8 Posts
    wie zeigt man das 3 wahr is

    gruss laborg

  16. #16

    Title
    Principal
    Join Date
    Jan 2002
    Posts
    46
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Original geschrieben von laborg


    aehm??? und was is wenn ich 2^(n-1) mit sagen wir 60 multipliziere? ... jo so einfach geht des ned...
    ok danke
    habs verstanden

  17. #17
    shabby's Avatar
    Title
    Elite
    Join Date
    Jan 2002
    Location
    Schrödinger, 1040 Wien
    Posts
    267
    Thanks
    2
    Thanked 9 Times in 8 Posts
    Original geschrieben von andy


    2) f(n) = O(g(n)) --> 20f(n) = O(1/2 g (n))
    f(n)=g(n)=2^n

    2^n=O(2^n) wahr
    20*2^n=O(1/2*2^n) falsch
    weil
    5*2*2*2^n=O(1/2*2^n)
    5*2^(n+2)=O(2^(n-1))
    folglich falsch
    -----------------
    2^(n+c) = O(2^(n-d)) für c,d fest

    eben genau weil

    2^(n+c) = 2^n * 2^c
    2^(n-d) = 2^n / 2^d

    Da c,d FEST, wählst du die Konstante c mit
    c = 1 / (2^c*2^d) woraufhin die Gleichung für alle n erfüllt ist.

    2^n * 2^c <= Konst * 2^n / 2^d
    2^n <= Konst * 2^n / (2^d*2^c)

    wobei die Konstante genau 2^d*2^c mal größer gewählt wird als notwendig.
    also gilt auch

    Konst' = Konst / (2^d*2^c)
    2^n <= Konst' * 2^n

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
  •