Prüfung kaum zu schaffen!

  • Prüfung für Informatiker, neuer Studienplan:
    Gruppe A: Theta(n), Theta(log n), Theta(log n), Theta(n log n)
    Gruppe B: Theta(n), Theta(log n), Theta(n log n), Theta(log n)
    Gruppe C: Theta(log n), Theta(n), Theta(log n), Theta(n log n)
    Gruppe D: Theta(n), Theta(log n), Theta(log n), Theta(n log n)

  • nachtmensch:
    > ist 3log n eigentlich in theta 2log n??
    > will damit sagen: ist die basis egal??


    Sei a>1, seien f(n), g(n): |N -> |R+ positivdefinite reellwertige Funktionen.


    a^(log_a x) = x
    => log_2 (a^(log_a x)) = log_2 x
    => log_a x * log_2 a = log_2 x (wegen log_2 a^m = m * log_2 a)
    => log_a x = 1/log_2 x * log_2 x
    => log_a x = Theta(log_2 x).


    Aus der Transitivität von Theta-Relationen, d. h. aus der Implikation


    f(n) = Theta(g(n)) ^ g(n) = Theta(h(n)) => f(n) = Theta(h(n))


    folgt, dass


    f(n) = Theta(log_a x) => f(n) = Theta(log_2 x)


    Aus der Reflexitivät von Theta-Relationen, d. h. aus der
    Implikation


    f(n) = Theta(g(n)) => g(n) = Theta(f(n))


    folgt dann weiters, dass


    f(n) = Theta(log_2 x) => f(n) = Theta(log_a x)


    Wir sehen: ja, die Basis ist komplett blunzn.

  • Zitat

    Original geschrieben von Georg Kraml
    Prüfung für Informatiker, neuer Studienplan:
    Gruppe A: Theta(n), Theta(log n), Theta(log n), Theta(n log n)
    Gruppe D: Theta(n), Theta(log n), Theta(log n), Theta(n log n)


    (iv) m = n
    solange m>0 {
    für i = 1,....,m+3 {
    k = k +i;
    }
    m = [m/2]; //abrunden!
    }


    weiß nicht mehr genau welche gruppe, a oder d wahrscheinlich
    aber wieso Theta(n log n)?


    n+(n/2)+(n/4)+(n/8)+(n/16)+...
    das sind ca. log n glieder
    ergibt Theta(n)

  • Einfach so die Laufzeitzeit anschreiben, wie wir es ganz am Anfang gemacht haben (ich hoffe das da unten ist genau genug):
    /edit: ist wohl falsch, will mich aber auch gerade nicht mehr damit beschaeftigen


    T(n) = 1 * c1 + log n * c2 + log n * (n + 3) * c3 + log n * (n + 2) * c5 --> Theta(n log n)


    /edit:
    uups, zu langsam ;-)

    Damn, here I was, minding my own business, just enjoying my second amendment rights, and you people have to FREAK out on me!

  • > andy (theta(n))
    1> (iv) m = n
    2> solange m>0 {
    3> für i = 1,....,m+3 {
    4> k = k +i;
    5> }
    6> m = [m/2];
    7> }


    nein, ich stimme andy zu.


    da drinn ist noch eine innere Schleife(3), die ca. m-mal pro Schleifendurchlauf von (>2) exekutiert wird, von ihr hängt die Laufzeit ab.(da sie am öftesten ausgeführt wird).


    Zur Veranschaulichung:
    1. 4> wird n-mal ausgeführt
    2. 4> wird n/2-mal ausgeführt
    3. 4> wird n/4-mal ausgeführt
    ....


    daher ergibts sich die Laufzeit der Zeile 4 zu:
    n + n/2 + n/4 + n/8 ...
    und dass ist, wie schon Prof.Kaiser anschaulich demonstriert hat ->
    2n also theta(n)


    und bevor wieder jemand fragt, ja, die Reihe verhält sich im endlichen genauso wie im Unendlichen (eigentlich ist die Summe etwas kleiner)


    wäre Zeile 3,4,5 von der Form
    k=k+i*m würde ich lt. den Spezifikationen der RAM auf theta(log n) plädieren, da wir aber Schleifen ausdrücklich nicht als eine einzige arithmetische Funktion zusammenfassen dürfen, es das hier nicht anwendbar.


    theta(n log n) würde gelten wenn Zeile 4 in jedem Durchlauf von Zeile 2 n-mal ausgeführt würde.


    @yucrem


    T(n) = 1 * c1 + log n * c2 +


    summe( n/i + 3 | i={1,2,4,8,...}) * c3 +
    summe( n/i + 3 | i={1,2,4,8,...}) * c4 +

    + log n * c5 --> Theta(n)


    sollte es lauten

  • laborg : hab gruppe d, die funktion war bei mir so ca. x/n^5 + x/n^7 + x/n^9. (statt den kostanten schreib ich immer x, weiss nicht mehr welche zahlen es waren und is ja auch unwichtig).
    die anderen funktionen und die lösungen waren bei mir soweit ich mich erinnern kann:


    a) x/n^5 --> O, theta, omega
    b) logn/n --> O
    c) x/n^9 --> omega

  • also wenn ich mir das hier so durchlese, dann bin ich immer wieder glücklich, dass ich mich noch rechtzeitig von der prüfung abgemeldet habe. cu next year!


    mfg philipp

    Philipp function beer no well without!
    -----------------------------------
    I was elected to LEAD, not to READ!