close

Anmelden

Neues Passwort anfordern?

Anmeldung mit OpenID

Gedächtnisprotokoll Zeichenketten Prüfer: Parchmann - janwy.de

EinbettenHerunterladen
Gedächtnisprotokoll Zeichenketten
Prüfer: Parchmann, ein Beisitzer (k.A. wie der heißt)
Prüfling: Jan Wyszynski
Prüfungsart: mündlich
Note: 1.3
Allgemeines
Die Atmosphäre bei der Prüfung war sehr nett, obwohl es für Herrn Parchmann auch
schon die zehnte an diesem Tag war. Ich hätte mich nicht gewundert, wenn er mir noch
Kaffee und Kuchen angeboten hätte. Die Prüfung war für 20-30 Minuten veranschlagt,
dieser Zeitraum scheint aber sehr individuell dehnbar zu sein. Ich wurde ca. 40 Minuten
geprüft, was ich aber nicht als schlimm empfunden habe. Der Beisitzer hat nur Protokoll
geführt und selbst keine Fragen gestellt.
Prüfungsinhalt
Ich sollte zunächst Algorithmen erklären, die etwas einfacher sind, und die ein Pattern von
links nach rechts mit dem Text vergleichen. Angefangen hat er mit Morris-Pratt, malte mir
ein Pattern und einen Text hin (wie so oft in der Vorlesung) und markierte eine Textstelle,
bei der eine Nichtübereinstimmung aufgetreten sein sollte. Dann sollte ich den Algorithmus
erklären, insbesondere die h-Funktion. Außerdem wollte er wissen, wie man die hFunktion effizient berechnet, also wie sie implementiert ist (Annahme, h[1] bis h[i] stehen
fest, wie sieht dann h[i+1] aus? --> bei p[i] = p[h[i]]: h[i+1] = h[i] + 1 usw.). Zusätzlich hat er
mich noch nach der Laufzeit gefragt. Er hat überhaupt sehr häufig nach Laufzeit und
Speicherverbrauch gefragt. Danach ging er über zur next-Funktion (also Knuth-MorrisPratt). Die musste ich erklären. Und schließlich hat er auch noch nach dem ApostolicoCrochemore gefragt, hier wollte er zusätzlich zu meiner Erklärung an einem Beispiel
erläutert haben, wie Apostolico im Vergleich zu KMP arbeitet. Als Beispiel hatte er das
Pattern „ab“ und den Text „aaaaaaa“ gegeben. Er erwähnte dann selbst, dass der ja nur
O(1.5n) Vergleiche braucht, dass wir das aber in der Vorl. nicht bewiesen haben. Den
Quick-Search Algorithmus wollte er danach erklärt bekommen. Die last- und shiftFunktion sollte ich aber nicht im Detail erläutern. Wieder kam die obligatorische Frage
nach der Laufzeit. Ich sollte zusätzlich noch ein Beispiel nennen (Pattern & Text), wann
die maximale Laufzeit O(n*m) erreicht wird, und wann O(n/m) erreicht wird. Da wusste ich
nicht erst nicht so recht bescheid, er hat mir aber ein bisschen auf die Sprünge geholfen
und ich bin drauf gekommen.
Es ging dann mit Tries, Suffix Tries und Suffix Bäumen weiter. Er wollte wissen was das ist
und was man damit machen kann. Vor allem wollte er wissen, wie man Suffix Bäume für
die Suche nach dem Auftreten eines Pattern im Text nutzen kann. Ich hatte leider keine
Ahnung. Man macht das wohl so, dass man einen Suffix Baum für den Text erstellt und
dann nach dem Pattern im Suffix Baum sucht. Dafür braucht man dann nur noch O(n) Zeit,
verbraucht aber wesentlich mehr Speicher und Zeit in der Vorverarbeitung um den Baum
aufzubauen. Schließlich wollte er noch wissen, wie man Suffix Bäume konstruiert. Ich
erklärte das an einem Beispiel. Dann fragte er noch nach dem Speicherbedarf und wie
man den verringern könnte. Zu diesem Zeitpunkt hatten wir schon 10 Min überzogen,
dennoch meinte er „wenn Sie jetzt schon mal hier sind, dann können wir sie ja auch noch
ein bisschen Quälen. Er wollte noch Ukkonen (die naive Methode) erklärt bekommen und
fragte auch hier nach dem Speicherbedarf. Zuletzt fragte er noch nach den Tricks, mit
denen man die Laufzeit auf O(m) runterbekommt. Die hatte ich zum Glück noch am Abend
vorher gelernt, das konnte ich ziemlich fix.
Das mit dem Überziehen begründete er dann auch damit, dass ich am Anfang wohl ein
bisschen langsam gewesen sei. Aber im Endeffekt hätte ich alles gekonnt.
Tipps
Häufig fragt er auch nach einem Algorithmus mit konstantem Delay. Das ist der Shift-or
Algorithmus, weil der im Prinzip nach jedem Vergleich ein Textzeichen weiterspringt. Das
wurde in der Vorlesung nur nebenbei erwähnt. Außerdem fragt er wohl nach
zweidimensionaler Suche (z.B. Mustersuche in Bildern), obwohl auch das in der Vorlesung
kaum dran war. Höchstens beim Karp Rabin Algorithmus. Laufzeiten und Speicherbedarf
der einzelnen Algorithmen sollte man ebenfalls kennen. Manchmal will er da auch ein
Beispiel für haben, geht dann aber i.A. nicht tiefer ins Detail.
Document
Kategorie
Seele and Geist
Seitenansichten
1
Dateigröße
36 KB
Tags
1/--Seiten
melden