+ Reply to Thread
Results 1 to 18 of 18

Thread: After Test 28.1.2010

Threaded View

  1. #1
    Elite
    Join Date
    Dec 2007
    Location
    Wien
    Posts
    254
    Thanks
    18
    Thanked 7 Times in 6 Posts

    After Test 28.1.2010

    Wie is es euch gegangen?

    Ich seh sie mal als Vorbereitung auf die Prüfung im Frühjahr
    War so klar, dass NICHT die Beispiele kommen die sonst immer dabei sind.
    Kein (ganzes) Suchbeispiel, keine Skipliste, kein Indexed Trie, kein Radix Trie, keine (mehrdimensionale) Suche ..

    War mMn ziemlich theorielastig diesmal ..
    Weil du nur einmal lebst!

  2. #2
    Baccalaureus Blutsturz's Avatar
    Join Date
    Jul 2006
    Location
    1200 Wien
    Posts
    606
    Thanks
    12
    Thanked 48 Times in 44 Posts
    fand die prüfung recht angenehm muss ich sagen, leider hab ich mir die tabu-suche viel zu wenig angeschaut um auch nur einen strich bei dem bsp machen zu können, aber was solls, der rest sollte zu 99,9 prozent passen

    @bobsch: entschuldige die fehlinformation bzgl. miller-rabin, aber im repetitorium hiess es, dass so ein beispiel nicht kommen werde (wahrscheinlich war gemeint, dass sicher keines kommt wo so große zwischenergebnisse rauskommen)
    "There's no such thing as Computer Science-it's witchcraft", math department of MIT, 1961

  3. #3
    Principal
    Join Date
    Apr 2008
    Posts
    85
    Thanks
    10
    Thanked 2 Times in 2 Posts
    Also der Miller-Rabin Algorithmus kam echt ziemlich überraschend, hab mir den fast garnicht angeschaut. Da konnte man bestenfalls noch 2 von den immerhin 7 Punkten rausschlagen, wenn man wusste, was ein entsprechendes Ergebnis aussagt.

    Das erste Beispiel war eigentlich recht machbar mit ein wenig überlegen. Wers sich bei BM einfacher machen wollte konnte auch einfach hinschreiben, dass er ne Variante ohne Suffixverschiebung nimmt

    Der Linienspaß war einfach, wenn mans alte Prüfungen gerechnet hat, die theoriefragen auch kein großes Problem (die letzte war glaub ich neu und das Kapitel hab ich leider nur überflogen)

  4. #4
    Principal
    Join Date
    Jun 2004
    Posts
    66
    Thanks
    18
    Thanked 1 Time in 1 Post
    mich hats mit miller-rabin und tabusuche leider auch am falschen fuss dawischt

    folgende fragen hats geben (gruppe a glaub ich):

    1) a)
    T=ababab.....ab (N zeichen)
    P=abb...b (7 zeichen)

    schätze möglichst genau ab, wieviele zeichen verglichen werden bei Naiver Suche, KMP, BM (jeweils 3 punkte)

    b) Signaturverfahren Ka und Rabin: Was sagt ein Macht/Missmatch (?) von Hashwert des Musters und Hashwert der Texts aus (1 punkt)

    2) a) Erkäre Monte Carlo vs Las Vegas Verfahren und nenne je ein Beispiel

    b) Miller-Rabin Primzahltest mit a=2 und n=10
    Alle Rechenschritte (5 punkte)
    Ergebnis erkären (2 punkte)

    3) a) Liniensegemente schneiden. Graph gegeben.
    Für 4 Schnittpunkte den Zeitpunkt angeben (8 punkte)

    b) Ereignisstruktur erklären. Womit wird sie initialisiert (2 punkte)

    4) Tabu-Suche
    Es gibt Funktürme die eine Frequenz von 1 bis q verwenden können fi ... {1,2,...q}
    Eine Matrix A besagt, ob sich zwei Funktürme bei gleicher Frequenz stören.
    Ziel ist es, die gegenseitigen Störungen der Funktürme zu minimieren.

    a) Beschreibe wie eine Kandidatenlösung für eine lokale Suche repäsentiert bzw gespeichert werden kann. Definiere eine Zielfunktion zur Bewertung einer Kandidatenlösung. (2 punkte)

    b) Beschreibe eine mögliche Nachbarschaftsstruktur in Worten. Beschreibe wie TL aufgebaut sein soll. Die TL soll Lösungsattribute speichern. (4 punkte)

    c) Gegebener Pseudo-Code für die Tabu-Suche
    Eigener Pseudo-Code war zu schreiben für die Einschränkung von Nachbarschaftslösungen anhand der TL und das finden einer besten Lösung aus der Teilmenge. (4 punkte)

    5) Theoriefragen, vergessen aufzuschreiben

  5. #5
    Baccalaureus Blutsturz's Avatar
    Join Date
    Jul 2006
    Location
    1200 Wien
    Posts
    606
    Thanks
    12
    Thanked 48 Times in 44 Posts
    Quote Originally Posted by dasjo View Post
    mich hats mit miller-rabin und tabusuche leider auch am falschen fuss dawischt

    folgende fragen hats geben (gruppe a glaub ich):

    1) a)
    T=ababab.....ab (N zeichen)
    P=abb...b (7 zeichen)

    schätze möglichst genau ab, wieviele zeichen verglichen werden bei Naiver Suche, KMP, BM (jeweils 3 punkte)

    b) Signaturverfahren Ka und Rabin: Was sagt ein Macht/Missmatch (?) von Hashwert des Musters und Hashwert der Texts aus (1 punkt)

    2) a) Erkäre Monte Carlo vs Las Vegas Verfahren und nenne je ein Beispiel

    b) Miller-Rabin Primzahltest mit a=2 und n=10
    Alle Rechenschritte (5 punkte)
    Ergebnis erkären (2 punkte)
    also:

    bsp 1) a)das Muster bestand aus 6 zeichen abbbbb, b) es war danach gefragt was ein MATCH heisst
    bsp 2) b) a=3
    "There's no such thing as Computer Science-it's witchcraft", math department of MIT, 1961

  6. #6
    Principal
    Join Date
    Jun 2007
    Posts
    85
    Thanks
    31
    Thanked 4 Times in 4 Posts
    Quote Originally Posted by Blutsturz View Post
    also:

    bsp 1) a)das Muster bestand aus 6 zeichen abbbbb, b) es war danach gefragt was ein MATCH heisst
    bsp 2) b) a=3
    Ich war Gruppe B, bin mir ziemlich sicher, dass es da 7 zeichen waren.
    So hab ich's gelöst:

    naiv: (N-7)*3
    KMP: (N-7) + (N-7)/3 = (4/3)(N-7)
    BM: (N-7)/6

  7. #7
    Principal
    Join Date
    Jun 2004
    Posts
    66
    Thanks
    18
    Thanked 1 Time in 1 Post
    Quote Originally Posted by totycro View Post
    Ich war Gruppe B, bin mir ziemlich sicher, dass es da 7 zeichen waren.
    So hab ich's gelöst:

    naiv: (N-7)*3
    KMP: (N-7) + (N-7)/3 = (4/3)(N-7)
    BM: (N-7)/6
    naiv: 2N
    kmp: N
    BM: N/7

    waeren meine loesungen dazu gwesen. vllt sollte hier noch ein rest dazu?

  8. #8
    Principal
    Join Date
    Oct 2007
    Posts
    44
    Thanks
    0
    Thanked 0 Times in 0 Posts

    anzahl der vergleiche für naive suche + KMP

    Quote Originally Posted by dasjo View Post
    naiv: 2N
    kmp: N
    BM: N/7

    waeren meine loesungen dazu gwesen. vllt sollte hier noch ein rest dazu?
    hi,

    bin grad bei der prüfungsvorbereitung für freitag und hab mich mal auf den test gestürzt...

    also bei naiv würde ich auf folgende lösung kommen:

    x = 4 * (N-6)/2

    ablauf:

    LABEL START
    *2 Matches, 1 Mismatch
    * shift um 1 stelle
    *1 Mismatch
    GOTO START

    pro durchlauf also 4 vergleiche
    die letzten 6 zeichen des textes brauchen nicht mehr verglichen zu werden
    pro durchlauf ist der 'vorschub' = 2

    ... kann das jemand bestätigen??

    KMP:

    soweit ich die angabe verstanden habe sollen nur die suchvergleiche im eigentlichen alg., nicht aber die NEXT-INIT - vergleiche gezählt werden.

    prinzipiell:

    START
    zeile 4 nicht ausgführt weil j=0, MATCH zeile 7, j erhöhen
    zeile 4 ausgeführt(MISMATCH), j++, MATCH zeile 7
    zeile 4 ausgeführt(MATCH), j=0, MISMATCH zeile 7
    GOTO START

    *also pro durchlauf 5 vergleiche(zeile 4 bzw. zeile 7)
    *es werden die letzten 5 BZW. 6 zeichen nicht mehr verglichen(5 für n=12, 16, ...; 5 für n = 10, 14, ...
    *'vorschub' ist immer 4

    damit würde ich auf folgende gleichungen kommen:

    x = 5 * (N-6)/4 für N=10, 14, ...
    x = 5 * (N-6)/4 + 4 f+r N=12, 16, ...

    BM hab ich mir noch nicht durgedacht... aber kann das jemand soweit bestätigen???

    harri
    go 4 powpow

  9. #9
    Principal
    Join Date
    Apr 2005
    Location
    Wien
    Posts
    85
    Thanks
    0
    Thanked 3 Times in 3 Posts

  10. #10
    Principal
    Join Date
    Nov 2005
    Posts
    96
    Thanks
    4
    Thanked 0 Times in 0 Posts
    teils sind schon noten da - ich habs zum glueck geschafft

  11. #11
    Baccalaureus Blutsturz's Avatar
    Join Date
    Jul 2006
    Location
    1200 Wien
    Posts
    606
    Thanks
    12
    Thanked 48 Times in 44 Posts
    mit dem 3er bin ich zufrieden...
    "There's no such thing as Computer Science-it's witchcraft", math department of MIT, 1961

  12. #12
    Principal
    Join Date
    Oct 2007
    Posts
    27
    Thanks
    3
    Thanked 1 Time in 1 Post
    4er... , naja hätt ich dacht das schon besser ist aber was solls

  13. #13
    Principal
    Join Date
    Oct 2008
    Posts
    50
    Thanks
    3
    Thanked 1 Time in 1 Post
    24 pkt... -.-

    damn... da kommt man vom schifahren back freut sich dass einige noten gut sind... und dann algodat 24 ... 1 pkt :'(

  14. #14
    Master freiBär's Avatar
    Join Date
    Jan 2010
    Posts
    146
    Thanks
    3
    Thanked 22 Times in 17 Posts
    Grad noch geschafft mit 28 Punkten....hät mir aber ein viel besseres Ergebnis erwartet....naja was solls....
    freiBär für alle!

  15. #15
    Master crux23's Avatar
    Join Date
    Nov 2005
    Location
    Wien _1100
    Posts
    164
    Thanks
    13
    Thanked 4 Times in 3 Posts
    wie kommt es das die prüfung dieses mal so theorielastig war??
    damit habe ich leider überhaupt nicht gerechnet.
    hab nur 19 pkt erreicht :'(

  16. #16
    Baccalaureus Blutsturz's Avatar
    Join Date
    Jul 2006
    Location
    1200 Wien
    Posts
    606
    Thanks
    12
    Thanked 48 Times in 44 Posts
    Quote Originally Posted by crux23 View Post
    wie kommt es das die prüfung dieses mal so theorielastig war??
    zeiten und auch prüfungen ändern sich...
    "There's no such thing as Computer Science-it's witchcraft", math department of MIT, 1961

+ Reply to Thread

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