Prüfungsprotokoll

Diplomvorprüfung Informatik
Praktische Informatik, Datenstrukturen

Vorbereitung

Die Prüfungsvorbereitung habe ich anhand der im Internet verfügbaren Prüfungsprotokollen durchgeführt. Dazu habe ich mir sortiert nach Kurseinheiten und Seiten diejenigen Abschnitte notiert, die von Prof. Klein abgefragt wurden. Diese Bereiche habe ich intensiv gelernt. Eine weitere Kursübersicht mit allen Themen, bei denen ich die jemals abgefragten rot markiert habe, sollte mir helfen, die sonstigen Abschnitte zumindest nicht zu vergessen.

Fragen

Folgende Fragen hat mir Prof. Klein gestellt:

• Welche einfachen Datenstrukturen gibt es? Welche Laufzeiten haben diese und was besagt diese Laufzeit?

  Listen und Arrays. Ich habe die O-Notation erklärt und die Zeiten für Listen und Arrays angeführt. Diese einzelnen Laufzeiten hatte ich nur mit überlegen und auch teilweise falsch wiedergegeben.

• Kann man solche Laufzeituntersuchungen sowohl für einen sehr alten Rechner als auch für heutige Supercomputer anstellen?

  Ich fügte an, daß die Laufzeit immer relativ zum System zu betrachten sei. Das wollte Prof. Klein aber nicht hören. Der Unterschied zwischen verschiedenen Computern kann man als konstant ansehen und dann spiele das in der O-Notation keine Rolle, da Konstanten eleminiert würden.

• Kommen wir jetzt zu Dictionaries. Was gibt es schnelleres als diese einfachen Verfahren? Wie sind diese Datentypen definiert?

  Binäre Bäume mit Definition.

• Prof. Klein schrieb einige Zahlen auf, die ich in einem binären Baum einfügen sollte. Dazu fragte er nach der Höhe des Baumes im Durchschnitt (1,386 * log n, also O(log n)), im worst case (n*n) und wie die Daten sortiert ausgelesen werden können (inorder Durchlauf).

• Welche Möglichkeiten gibt es, wenn man den worst case vermeiden muß?

  AVL-Bäume mit Definition. Ich habe die Strukturinvariante erklärt, das Rebalancieren mit Rotation und Doppelrotation, daß diese beim Löschen eventuell bis in die Wurzel wiederholt werden muß.

• Welche Höhe hat der AVL-Baum?

  O(log n) und maximal 44% höher als ein vollständig gefüllter Binärer Baum. Die Begründung mit Herleitung und Nennung der Fibonacci-Zahlen hatte Prof. Klein schon als zu ausführlich abgebrochen. Kurze Nennung von Fibonacci hätte ihm gereicht.

• Welche Sortierverfahren gibt es?

  Einfache Verfahren (Direktes Auswählen und Einfügen) mit Laufzeiten O(n*n), Divide-and-Conquer (Merge-, Quick- und clever Quicksort) mit Laufzeiten O(n log n) bzw. O(n*n) bei Quicksort im worst case. Bevor ich noch weiter Ausführen konnte und Heap und Baumsort erwähnte, stellte Prof. Klein die nächste Frage.

• Wie funktioniert Mergesort?

  Ich habe die Grundsätze der DAC-Algorithmen erklärt und Mergesort mit Unterschied zu Quicksort geschildert. Zur Laufzeit O(n log n) wollte Prof. Klein genau wissen, warum es »n * log n« und nicht »n + log n« lautet (weil in jeder Rekursionsstufe jedes Element »angefaßt« wird).

• Beim Quicksort ist der worst case schlecht. Ändert sich etwas, wenn z.B. immer das drittkleinste Element genommen wird?

  Dazu sagte ich erst, kaum etwas. Auf Nachfrage fiel mir aber ein, daß bei großen n sich nichts ändert. Bei der O-Notation fallen die Kontanten heraus. Eine Änderung tritt also nur ein, wenn in Abhängigkeit von n ein anderes Element genommen wird.

• Prof. Klein schilderte dann den Fall, daß er eintausend Bücher einsortieren musste. Mit welchen Algorithmus wäre das am schnellsten?

  Ich sagte erst AVL-Bäume. Aber Prof. Klein wollte Bucketsort und Radixsort hören. Als ich einwarf, daß es aber Autoren mit mehreren Veröffentlichungen gäbe und ich somit keine eindeutigen Schlüssel hätte (sonst wäre Bucket bzw. Radix sicher am schnellsten wegen O(n) Laufzeit), sagte er, daß man ja weitere Kriterien wie z.B. Titel zur eindeutigen Schlüsselerzeugung hinzunehmen könnte.

• Wie Sie wahrscheinlich aus anderen Prüfungen schon wissen, ahnen Sie, was ich jetzt frage. (Prof. Klein malte einige sich kreuzende Striche auf ein Papier.) Wie kann man die Schnittpunkte ermitteln, einmal ganz einfach und geht es dann noch besser?

  Die einfachste Methode ist ein Vergleich jedes Elements mit jedem anderen. Der Aufwand ist dann O(n²). Ich sollte noch erklären, wieso der Aufwand n² sei. Der genaue »Beweis« dazu fiel mir nicht ein und sagte nur, weil man eben jedes mit jedem vergleichen müßte. Da zeichnete Prof. Klein vier senkrechte und vier waagerechte Linien auf, die sich alle kreutzten und erklärte, daß das der worst case sei und daher O(n*n). Anschließend erklärte ich als bessere Alternative für das Problem das Plane-Sweep-Verfahren mit Status- und Event-Struktur, realisiert in einem balacierten Baum und einer Priority Queue.

• Wie ist denn die Laufzeit des Plane-Sweep-Verfahrens?

  O((e + k) log e), mit e als Anzahl der Segmente und k als Anzahl der Schnittpunkte.

Fazit

Prof. Dr. Klein ist ein sehr guter und ruhiger Prüfer. Er stellt die Fragen direkt und freundlich. In mehreren Fällen hatte ich keine »mathematisch« genaue Definition bereit sondern habe versucht, mit eigenen Worten zu erklären. Anhand der vorletzten Frage (der Zeichenbeweis für O(n*n) beim einfachen Vergleichen der Segmente anstatt eines mathematischen) sieht man, daß Prof. Klein viel mehr Wert auf das Verständnis legt als auf auswendig aufgesagte aber nicht verstandene Definitionen. Das gilt im Besonderen für die O-Notation. Er kam immer wieder auf die O-Notation zu sprechen oder wollte etwas mit dieser begründet haben (z.B. warum sich zwei unterschiedlich schnelle Rechner nicht auf die Laufzeitbestimmung auswirken; das worst case Verhalten beim Quicksort; ob es einen Unterschied mache, wenn beim Quicksort das drittkleinste Element genommen würde usw.). Es ist wichtig, den Sinn und die Aufgabe der O-Notation verstanden zu haben und diese auf praktische Fälle anwenden zu können.

Prof. Klein hat sich wie bei den anderen Prüfungsprotokollen auch auf das Wesentliche des Kurses (Grundlegende Datenstrukturen, Sortierverfahren, Geometrische Algorithmen und O-Notation) beschränkt (Dijkstr-Algorithmus für Graphen hat er nicht gefragt und den Beweis für die untere Schranke von Sortieralgorithmen hatte er angefangen zu fragen kam aber im Gespräch wieder davon ab). Es kamen keine ungewöhnlichen Fragen. Die Prüfung lief erher ab, wie ein Gespräch.

Ich kann Prof. Klein sehr empfehlen. Wer sich mit den vorhandenen Prüfungsprotokollen vorbereitet und nicht zuviel »Nebensächlichkeiten« lernt (Mut zur Lücke :-)), wird bei Prof. Klein die Prüfung problemlos bestehen. Viel Glück!

Copyright © 1999 Thomas Schwarze