Fachrat Informatik - Forum

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.

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.

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

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

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.

Habe eine EMail von Prof. Parchmann bekommen, im Herbst wird es wohl noch eine Nachprüfungsmöglichkeit geben.

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

Irgendwer vom SE, je nachdem wer Zeit hat.

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

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

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.

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.

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.

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

Quoted from "nano"

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.

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.

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