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.Quoted
The data structure has one node for every prefix of every string in the dictionary.
Zerschmetterling
Date of registration: Aug 31st 2003
Location: Hannover
Occupation: Informatikstudent (d'uh)
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
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.