You are not logged in.

Kiki der Gecko

Regenbogeneidechse

  • "Kiki der Gecko" started this thread

Posts: 513

Date of registration: Oct 1st 2008

1

Monday, February 4th 2013, 7:11pm

Approximative Zeichenkettensuche

In der Themenliste zur Prüfung gibt es unten auf der ersten Seite eine Punkt namens "Berechnung der Distanzfunktion auf Basis einer Menge allgemeiner Edit-Operationen. Zeit- und Speicherkomplexität.". Das Thema wird im Skript in Abschnitt 3.3.1 behandelt und zur Laufzeit findet man auch Angaben, allerdings nicht zur Speicherkomplexität. In den Übungen habe ich ebenfalls nichts dazu gefunden. Kann mir da jemand mit helfen?
"Alles ist eins - außer der Null." - Wau Holland

Helicase

Trainee

  • "Helicase" is male

Posts: 85

Date of registration: Oct 3rd 2006

2

Monday, February 4th 2013, 7:40pm

Hey,

ist zwar schon etwas her bei mir, aber verwendet man da nicht trotzdem einfach den Wagner-Fischer Algorithmus? Der baut wieder eine Tabelle auf, also hat man eine Speicherplatzbedarf von O(n*m) (n=Länge des ersten Wortes, m=Länge des zweiten). Das ist ja recht typisch für die dynamische Programmierung.

Kiki der Gecko

Regenbogeneidechse

  • "Kiki der Gecko" started this thread

Posts: 513

Date of registration: Oct 1st 2008

3

Monday, February 4th 2013, 8:13pm

Ja, das könnte sein. Allerdings wird in der Bemerkung auf S. 30 oben noch der Aho-Corasick-Algorithmus erwähnt (wurde auch in der Vorlesung erwähnt, darum messe ich dem so viel Gewicht bei), nur finde ich nirgends eine Angabe zur Speicherkomplexität. Selbst im Original-Paper werden verschiedene Speichermethoden erwähnt, um die Laufzeit zu beschreiben.

Ich muss aber dazu sagen, dass ich mittlerweile auch schon ziemlich unkonzentriert bin, vielleicht ist die Lösung ja auch ganz einfach und ich sehs nur nicht ;)
"Alles ist eins - außer der Null." - Wau Holland

Helicase

Trainee

  • "Helicase" is male

Posts: 85

Date of registration: Oct 3rd 2006

4

Monday, February 4th 2013, 10:48pm

Hmm laut wiki

Quoted

The data structure has one node for every prefix of every string in the dictionary.
Also angenommen es gäbe nur ein Wort im Dictionary mit m Zeichen, dann hat man m-1 Prefixe.. Bei zwei Wörtern m1,m2 wären es m1-1 + m2-1 viele Präfixe.. ich würd auf linearen Speicherbedarf tippen. Ein endlicher Automat braucht ja keinen Extra-Speicher.

XAX

Junior Schreiberling

  • "XAX" is male

Posts: 207

Date of registration: Dec 25th 2004

5

Sunday, March 17th 2013, 4:50pm

Inzwischen waren ja schon einige Prüfungstermine. Wie verliefen die denn so? Für Erfahrunsberichte wäre ich dankbar.

Kiki der Gecko

Regenbogeneidechse

  • "Kiki der Gecko" started this thread

Posts: 513

Date of registration: Oct 1st 2008

6

Monday, March 18th 2013, 7:42pm

Du solltest auf jeden Fall die verschiedenen auf Matrizen basierenden Verfahren können und skizzieren, erklären und daraus die Laufzeiten ableiten. Formeln zu repetitieren war eher nicht so gefragt.
"Alles ist eins - außer der Null." - Wau Holland

mar1k

Trainee

Posts: 41

Date of registration: Oct 17th 2009

7

Monday, March 18th 2013, 9:49pm

Also gefragt wurden zum einen die grundlegenden Sachen: Ausrichtungen, Korrespondenzen, abstrakte Distanzfunktion, lcs/scs (auch über Distanzfunktion) und Ähnliches. Dann kam ein Abschnitt in dem es über die Matrizenverfahren ging - man sollte hier vor allem erklären können wie sie genau funktionieren, was deren Laufzeiten sind und warum bestimmte Verfahren besser oder schlechter sind als andere. Die eine oder andere Formel sollte man schon drauf haben, so wurde ich z.B. gefragt, ob man lcs mit dem Ukkonen-Verfahren berechnen kann, was schon voraussetzt dass man weiß, wie die Grenzen für die Diagonalen berechnet werden.

Aber eigtl. wenn du zu jedem Punkt in der Themen-pdf was sagen kannst kann nichts schief gehen ;)

hamena314

Zerschmetterling

  • "hamena314" is male

Posts: 2,032

Date of registration: Aug 31st 2003

Location: Hannover

Occupation: Informatikstudent (d'uh)

8

Monday, March 18th 2013, 10:37pm

Wenn man in der Prüfung durchfällt, wird im kommenden Semester noch eine Prüfung für die Durchfaller / Dann-Teilnehmer angeboten? Prof. Parchmann hört ja irgendwann auf.
Nicht der Wind bestimmt die Richtung, sondern das Segel! (Lao Xiang, China)

Kiki der Gecko

Regenbogeneidechse

  • "Kiki der Gecko" started this thread

Posts: 513

Date of registration: Oct 1st 2008

9

Monday, March 18th 2013, 10:48pm

Also gefragt wurden zum einen die grundlegenden Sachen: Ausrichtungen, Korrespondenzen, abstrakte Distanzfunktion, lcs/scs (auch über Distanzfunktion) und Ähnliches. Dann kam ein Abschnitt in dem es über die Matrizenverfahren ging - man sollte hier vor allem erklären können wie sie genau funktionieren, was deren Laufzeiten sind und warum bestimmte Verfahren besser oder schlechter sind als andere. Die eine oder andere Formel sollte man schon drauf haben, so wurde ich z.B. gefragt, ob man lcs mit dem Ukkonen-Verfahren berechnen kann, was schon voraussetzt dass man weiß, wie die Grenzen für die Diagonalen berechnet werden.

Aber eigtl. wenn du zu jedem Punkt in der Themen-pdf was sagen kannst kann nichts schief gehen ;)


Bei mir gings (leider) gleich mit den fortgeschrittenen Themen los: Erweiterte Edit-Distanz, Ukkonen-Verfahren, Lückenkosten etc.
"Alles ist eins - außer der Null." - Wau Holland

hamena314

Zerschmetterling

  • "hamena314" is male

Posts: 2,032

Date of registration: Aug 31st 2003

Location: Hannover

Occupation: Informatikstudent (d'uh)

10

Tuesday, March 19th 2013, 9:51am

Habe eine EMail von Prof. Parchmann bekommen, im Herbst wird es wohl noch eine Nachprüfungsmöglichkeit geben.
Nicht der Wind bestimmt die Richtung, sondern das Segel! (Lao Xiang, China)

suey

M.Sc.

  • "suey" is female

Posts: 485

Date of registration: Sep 29th 2009

11

Tuesday, March 26th 2013, 10:59am

Wer protokolliert eigentlich? Herr Wichers ist ja schon seit einiger Zeit nicht mehr dabei.

12

Tuesday, March 26th 2013, 12:54pm

Irgendwer vom SE, je nachdem wer Zeit hat.
٩(͡๏̯͡๏)۶

Shorty86

Trainee

  • "Shorty86" is male

Posts: 32

Date of registration: Oct 11th 2007

13

Tuesday, March 26th 2013, 4:17pm

Wurde in den bisherigen Prüfungen nach Beweisen gefragt oder nur allgemein gehalten und dabei nach Laufzeit und Speicher gefragt?

Oelkstul

random classifier

  • "Oelkstul" is male

Posts: 60

Date of registration: Oct 9th 2007

14

Tuesday, March 26th 2013, 4:39pm

Mich würde auch interessieren ob schon jemand zum Verfahren von Wu-Manber gefragt wurde und wie gut man das Verfahren verstehen muss.

This post has been edited 1 times, last edit by "Oelkstul" (Mar 26th 2013, 4:39pm)


Sharados

Praktikant

Posts: 10

Date of registration: Sep 11th 2010

15

Tuesday, March 26th 2013, 9:03pm

Bei mir wurde direkt mit Wagner-Fischer Angefangen, danach Semi-Globales und lokales Ausrichteproblem, dann Sellers als k-Differenz-Algorithmus und zum Schluss noch Ukkonen und Hirschberg-Verfahren.

Beispielswiese fragte er beim lokalen bzw. semi-globalen Ausrichteproblem, wieso man die Matrix mit 0 initialisiert und hat auch gefragt, inwiefern der Sellers Algorithmus ähnlichkeit zum Semi-Globalen Ausrichteproblem aufweist. (Präfixe/Suffixe)

Also die Verfahren sollte man schon verstehen und auch die Speicher/Zeitkomplexität herleiten können.

ProNoob

Trainee

  • "ProNoob" is male

Posts: 72

Date of registration: Oct 1st 2010

Location: Hannover

16

Wednesday, March 27th 2013, 9:06pm

Bei mir ging es gleich in der ersten Frage um das k-Differenzen Problem. Anschließend um die entsprechenden Algorithmen: Sellers, die modifizierte Version mit Cut-off, das angepassten Diagonalenverfahren von Ukkonen und auch Wu-Manber. Insgesamt lag der Schwerpunkt darauf verstanden zu haben, wie die jeweiligen Algorithmen funktionieren, was man wie initialisiert und warum. Fragen zu allem was vorher im Skript stand kamen bei mir nicht dran. Hintergrundwissen zu haben (z.B. dass das angepasste Ukkonen Verfahren auf der Diagonaleneigenschaft basiert und wie das dem Algorithmus hilft) war aber trotzdem wichtig. Formeln exakt auswendig zu wissen war nicht gefordert. - aber erklären können. Beispiel: beim angepassten Diagonalenverfahren von Ukkonen hat er die L_p,e Formel aufgeschrieben (die aus drei Teilen besteht) und ich sollte erkären, was die einzelnen Therme bedeuten (mit Skizze) und wo jeweils eine +1 dazukommt und warum. Interessanterweise kam nichts zu Kapitel 6 dran. Benotung war mehr als fair.

Viel Glück an alle, die morgen noch ran müssen.

nano

Alter Hase

  • "nano" is male

Posts: 146

Date of registration: Oct 11th 2010

Location: Hannover

Occupation: THI

17

Thursday, March 28th 2013, 10:45am

Ich sollte die abstrakte Distanzfunktion nicht-rekursiv und rekursiv angeben und sagen, warum die rekursive vorteilhaft ist, bzw letztendlich sollte ich sagen, warum Wagner-Fischer funktioniert.
Dort sollte ich dann auch die Matrix für globale, semiglobale und lokale Ausrichtungssuche angeben und den Aufbau erklären und sagen, wo man das Ergebnis findet.

Danach ging es direkt zu Kapitel 6, wo allerdings auch nichts ausgelassen wurde.

Laufzeit war bei Wagner-Fischer, beim Erstellen des Sterngraphen und für das Matrixerstellen für multiple Ausrichtungen gefragt.

Oelkstul

random classifier

  • "Oelkstul" is male

Posts: 60

Date of registration: Oct 9th 2007

18

Thursday, March 28th 2013, 11:30am

Wow. Hat er auch nach Steiner-Distanz und Konsensus-Fehler gefragt?

Ich sollte die abstrakte Distanzfunktion nicht-rekursiv und rekursiv angeben und sagen, warum die rekursive vorteilhaft ist, bzw letztendlich sollte ich sagen, warum Wagner-Fischer funktioniert.
Dort sollte ich dann auch die Matrix für globale, semiglobale und lokale Ausrichtungssuche angeben und den Aufbau erklären und sagen, wo man das Ergebnis findet.

Danach ging es direkt zu Kapitel 6, wo allerdings auch nichts ausgelassen wurde.

Laufzeit war bei Wagner-Fischer, beim Erstellen des Sterngraphen und für das Matrixerstellen für multiple Ausrichtungen gefragt.


Meine Prüfung verlief in etwa wie die von ProNoob.
k-Differenzenproblem - Sellers, 2 Leute und Ukkonen, Diagonalenverfahren und Wu-Manber (jeweils mit Zeit und manchmal Speicherkomplexität).
Die Formeln durfte ich mir selbst basteln, aber gefordert war das zumindest bei Wu-Manber nicht. Voranging ging es darum dass er sieht, dass man die Verfahren und Probleme wirklich verstanden hat.
Wenn man bei einer Kleinigkeit ( O(d) statt O(k) oder ein index falsch) etwas unsicher ist, dann ist das nicht fatal.

nano

Alter Hase

  • "nano" is male

Posts: 146

Date of registration: Oct 11th 2010

Location: Hannover

Occupation: THI

19

Thursday, March 28th 2013, 11:32am

Ja, Steiner-Zeichenketten und Konsensuszeichenketten wollte er erklärt haben, sowohl die Definition als auch die Approximation über den Zentrumstern mit dem Faktor 2. Das aber alles ohne tiefere Begründung.

Anselm

borlark

Posts: 164

Date of registration: Oct 13th 2010

Occupation: WiMi ThI

20

Thursday, March 28th 2013, 2:42pm

Bei mir kam folgendes dran:
Der Distanzbegriff über Edit-Sequenzen definiert:
Wie kann man ihn darüber definieren, was ist daran problematisch/warum ist es nicht entscheidbar (also auf Typ 0 Sprache verweisen)
Dann Einschhränkung auf die *-Eigenschaft bei den zu prüfunden Editsequenzen, was die *-Eigenschaft ist, wie sie hilft.
Dazu sollte ich dann auch die rekursive Vorschrift anhand der Matrix erklären, aber nicht genau die Terme aufschreiben. Auch der Zeitbedarf dieses Verfahrens wurde gefragt und, wie man daraus eine Ausrichtung gewinnt (wobei er da sogar selbst angemerkt hat, dass es nicht im Skript steht).
Dann ging es weiter mit Lückenkosten: Definition, Berechungsvorschrift anhand der Matrix erklären (wobei er da lieber was von I- und D-Matrix gehört hätte anstatt einer direkten Erklärung anhand der d-Matrix), Laufzeit.
Selbiges dann auch nochmal für affine Lückenkosten.
Danach sollte ich erklären, was das k-differenzen-problem ist und wie man es lösen kann (wobei ihm Sellers reichte).
Zuletzt sollte ich dann noch multiple ausrichtungen definieren (bzw ihre eigenschaften erklären), sagen warum bei denen ein direkter Ansatz zu aufwendig ist und selbiges auch nochmal für Sum-of-Pairs (wobei er da die Definition genannt hat und nach dem Namen gefragt hat). Dann sollte ich erläutern, wie man die Sum-of-Pairs-Distanz approximieren kann (da hab ich dann entsprechend noch kurz erklärt, was zu einem Graphen konsistente Ausrichtungen sind und, dass man eine konsistente Ausrichtung zu einem zykelfreien Graphen auf jeden Fall findet, das braucht man ja irgendwie an der Stelle). Approximation dann eben über den Zentrums-Stern.

Insgesamt kann man sagen, dass er auch selbst nicht wenig sagt und dass man dadurch meist, bis er seine Frage stellt schon ganz gut im Thema ist. Außerdem verlangt er keine allzu detaillierten Erklärungen. Dafür kann wohl potentiell wirklich jedes Thema der Vorlesung dran kommen.

Viele Grüße,
Anselm
"Once you figure out what a joke everything is, being the comedian's the only thing makes sense."
~The Comedian