Computer Science, 2013-08-14

Module: 
Computer Science
Examiner: 
Vornberger, Pulvermüller
Date: 
Wed, 2013-08-14

Formalia

Modulprüfung:
Informatik A, Informatik B
Fachsemester:
4

Prüfung

Wiederholungsprüfung?
nein
Note:
1.0
Bereiche nach Zeit:
jeweils 15min

Vorbereitung

Was hast du zur Prüfungsvorbereitung benutzt?
Was wir hilfreich, was war weniger hilfreich?

Videoaufzeichnungen der Aolgorithmen-Veranstaltung + Skript,
Info B Skript mehrmals detailiert durchgearbeitet,
ggf. zusätzliche Informationen aus "Java ist auch eine Insel"

Wie lauteten die Fragen im einzelnen?

Info A

Vornberger: Was ist denn ein Heap?
ich: Ein Heap ist ein binärer Baum, der entweder leer ist oder einen Knoten hat, dem zwei binäre Bäume zugeordnet sind. Die entscheidene Eigenschaft, die den Heap vom einem normalen binären Baum unterscheidet, ist, dass der Schlüssel eines Knotens immer kleiner oder gleich dem Schlüssel seiner Söhne ist. Deshalb wird der Heap als Datenstruktur verwenden, die das Entfernen des Minimums unterstützt.
Die zweite Kriterium, das einen binären Baum zum Heap macht, ist, dass alle Ebenen - bis auf die letzte - vollständig sind und die letzte bis zum letzten Knoten.
Vornberger: Malen Sie doch mal so einen Heap auf, indem in der Wurzel zum Beispiel 42 steht!
ich: *fange an zu zeichen*
Vornberger: Ja das reicht schon. Wie würden Sie den denn jetzt in Java implementieren?
ich: Bei n Knoten würde ich ein eindimensionales Integer-Array mit Platz für n ints anlegen. Die Knoten speicher ich dann in diesem Array und zwar den Vater eines Knoten i an der Stelle (i-1)/2, den linken Sohn eines Knoten i an der Stelle 2*i+1 und den rechten an der Stelle 2*i+2.
Vornberger: Sie hatten ja vorhin angesprochen, dass ein Heap eine gute Idee für das Entfernen des Minimus ist. Wie macht man denn das jetzt?
ich: Naja, man entnimmt dem Heap solange das kleinste Element (also das Wurzelelement) bis er leer ist und speichert diese Elemente im selben Array. Die können dann in absteigender Reihenfolge ausgegeben werden.
Vornberger: Ja, aber wie genau machen Sie das? Zeigen Sie das doch mal anhand ihres aufgemalten Baumes.
ich: Achso Sie spielen wahrscheinlich auf das Sickern an. Also ich nehme das kleinste Element und entferne es, dadurch wird die Baumstruktur verletzt, deshalb nehme ich das letzte Element der letzten Reihe, schreibe es in die Wurzel und tausche es jeweils mit seinem kleineren Sohn, solange bis er entweder ein Blatt ist oder die richtige Position erreicht hat. Den Vorgang nennt man sickern.
Vornberger: Gut. Warum nehme ich denn das letzte Element der letzten Reihe?
ich: Würde ich die leere Wurzel gleich durch den kleineren Sohn ersetzten, kann es sein, dass die Heapeigenschaften nicht mehr erfüllt sind.
Vornberger: Wie lange dauert es denn, wenn ich mir das kleinste Element anzeigen möchte?
ich: O(n log n)
Vornberger: Nene, erstmal nur anzeigen.
ich: Achsoo. Ja anzeigen geht mit der Methode get_min in konstanter Zeit, aber das Minimum mit del_min zu entfernen ist logarithmisch und den Heap anschließend mit init_heap wieder zu organisieren O(n).
Vornberger: Korrekt. Was wäre dann so der Average case?
ich: best, worst und average case sind alle O(n log n).
Vornberger: Warum dauert das Löschen O(log n).
ich: Das ist gerade genau die Anzahl der Ebenen. Das kann man ganz gut mithilfe des Entscheidungsbaum sehen, der ja bei n! Blättern und (n/4 log n) Ebenen im best case O(log n!) und im worst case O(n!) hat und das ist ja gerade die Anzahl der Ebenen. (*habs noch etwas ausführlicher erkläret*).
Vornberger: Welchen Soltieralgorithmus kennen Sie denn noch so, der aber ganz anders als der Heap funktioniert?
ich: Ja, also ganz anders funktioniert der BucketSort. Der basiert nämlich nicht auf Vergleichen.
Vornberger: Da haben Sie Recht, aber bleiben wir mal bei denen die auf Vergleichen basieren.
ich: Achso ok, da hätten wir zum Beispiel den Merge- oder Quicksort nach dem Prinzip "divide and conquer".
Vornberger: Ja. Erklären Sie doch mal den Quicksort anhand dieses Beispiels *malt unsortierte Zahlenfolge auf*.
ich:

- Vorteil Median
-

Info B

...
puh vervollständige das die Tage mal alles.
gerade kein Bock mehr. Die Sonne scheint ;)!

...

Was mußte schriftlich gelöst werden?

Info A: Heap aufmalen, Quicksort aufmalen
Info B: Constructor-Chaining implementieren, UML-Doagramm für Decorator-Pattern

Bewertung und Begründung:

Hatte die Tür noch nicht ganz geschlossen, da konnte ich auch schon wieder rein! Beide waren sich einig.
Herr Vornberger sagte noch "Da wünscht man sich doch, dass jede Prüfung so abläuft!"

Lässt sich der Prüfer von den Antworten leiten?

eher nicht

Man kann bestimmt um den heißen Brei reden, aber im Endeffekt haben beide gezielt auf bestimmte Schlüsselwörter gelauert und
waren dann zufrieden sobald sie diese gehört haben.

Zum Verhalten des Prüfers:

professionell + freundlich

Ich konnte sogar zwischendurch ein wenig mit ihnen rumspaßen, aber trotzdem eine gewisse Seriösität wahren!