Fachrat Informatik - Forum

Also,

die Prüfung lief eher wie ein Gespräch über die in der Vorlsg. behandelten Alogrithmen ab. Dabei hat Prof. Parchmann nur ein paar Alogrithmen ausgewählt, zu denen er dann recht detailliert gefragt hat. Die Idee des Algo ist natürlich das Wichtigste, ebenso die gängigen Definitionen -aber es wurden auch oft spezielle Dinge (Laufzeiten in verschiedenen Phasen, Besonderheiten bei der Implementierung, ...) gefragt.
Wäre also gut, wenn man den Ablauf und die Einzelnen Phasen der Algos verstanden hat. Auch die Quelltexte im Lecroq ansehen kann dabei helfen. Auf keinen Fall sollte man auf die Java-Applets auf der Seite zum Buch verzichten (http://www-igm.univ-mlv.fr/~lecroq/string/).
Vorrechnen von übungszettelartigen Aufgaben war nicht angesagt, jedoch kann es nicht schaden, die auf den Zetteln geforderten Überlegungen im Hinterkopf zu haben.

Ich würde eine sehr umfassende Vorbereitung empfehlen; "Auf Lücke" lernen geht hier sicherlicht garnicht, da nur eine Auswahl des Stoffes abgeprüft werden kann, diese jedoch ausführlich.

Die Athmosphäre während der Prüfung war sehr angenehm.

Ich hoffe, die Infos helfen ein bisschen ...so richtig genaue Erinnerungen hab ich leider nicht mehr, der Speicherplatz im Hirn musste schonwieder mit neuem Prüfungswissen überschrieben werden

cu cowhen

mich würde noch interessieren, ob in der prüfung auch auf tries, trees, suffix-trees (und was es da noch so gibt) eingegangen wird. oder wird das thema nur oberflächlich oder gar garnicht behandlet?

vielen dank im voraus.

Quoted

Original von Diktator
mich würde noch interessieren, ob in der prüfung auch auf tries, trees, suffix-trees (und was es da noch so gibt) eingegangen wird. oder wird das thema nur oberflächlich oder gar garnicht behandlet?

Im meiner Prüfung kam das auch dran. Nicht mehr oder weniger ausführlich als anderes auch. Ist ja Grundlage für einige Algos und hat einen nicht kleinen Teil der Vorlsg ausgemacht.

hallo,

ich habe folgende fragen:

1. wie kommt man beim apostolica-algorithmus darauf, dass die maximale anzahl von vergleichen bei 3/2*n liegt.

2. ich habe nicht ganz verstanden, wie man im allgemeinen delay(m) berechnet. morris-pratt hat zum beispiel ein delay beschränkt durch m. wieso?

vielen dank für antworten.

Quoted

Original von Obi-Wan Kenobi
2. ich habe nicht ganz verstanden, wie man im allgemeinen delay(m) berechnet. morris-pratt hat zum beispiel ein delay beschränkt durch m. wieso?

Hab' ich mir heute auch nochmal angeschaut. Das delay(m) gibt an, wieviel Zeit zwischen 2 Leseoperationen auf Zeichen des Textes s verstreichen kann.
Bei dem Morris-Pratt Algorithmus steht im Skript das Beispiel p = a^m und s = a^n.

In diesem Falle wird mit der h-Funktion das Pattern zeichenweise verschoben, also erst nach m Schritten wird ein neues Zeichen aus dem Eingabetext gelesen. Somit vergeht maximal m Zeit zwischen zwei Leseoperationen.

So habe ich das jetzt verstanden.