After Test 28.1.2010

[Campino]

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 ..

[Blutsturz]

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)

[rgta]

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)

[dasjo]

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

[Blutsturz]

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

[totycro]

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

[dasjo]

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?

[powpow]

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

[human]

Angaben sind online: http://www.ads.tuwien.ac.at/w/WS09/1...gsbl.C3.A4tter

[fabfab]

teils sind schon noten da - ich habs zum glueck geschafft

[Blutsturz]

mit dem 3er bin ich zufrieden...

[sKuLi]

4er... , naja hätt ich dacht das schon besser ist aber was solls

[Michi2]

24 pkt... -.-

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

[freiBär]

Grad noch geschafft mit 28 Punkten....hät mir aber ein viel besseres Ergebnis erwartet....naja was solls....

[crux23]

wie kommt es das die prüfung dieses mal so theorielastig war??
damit habe ich leider überhaupt nicht gerechnet.
hab nur 19 pkt erreicht :'(

[Blutsturz]

wie kommt es das die prüfung dieses mal so theorielastig war??

zeiten und auch prüfungen ändern sich...