Computer Science, 2017-04-05

Module: 
Computer Science
Examiner: 
Oliver Vornberger
Assessor: 
Elke Pulvermüller
Date: 
Wed, 2017-04-05

Modulprüfung: Informatik A und B Fachsemester: 5. Fachsemester
Prüfer/2.Prüfer: Vornberger, Pulvermüller

VORBEREITUNG

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

Ich habe vor allem mit den Skripten sowie meinen Zusammenfassungen derselben gelernt und bei Unklarheiten das Internet sowie Vorlesungsaufzeichnungen zu Rate gezogen.

PRÜFUNG

Prüfungsdatum: 05.04.2017
Wiederholungsprüfung? nein Beisitzer: /
Note: 1.0 Bereiche nach Zeit: 10/10

Fragensammlung: wie lauteten die Fragen im einzelnen?

Info A

Was ist der Chinese Postman?
Ich habe dann allgemein von Graphen erzählt (Knoten, Kanten, Gewichtung) und das Chinese Postman Problem erklärt. Dann bin ich auf den Algorithmus zur Lösung eingegangen: Eulergraph -> Eulertour, wenn nicht mit Knoten mit ungeradem Grad Floyd anwenden und danach ein Minimal-Cost-Matching durchführen.

Welche anderen Probleme kennen Sie mit ungerichteten Graphen?
Minimaler Spannbaum: Definition und Algorithmus erklärt (Kanten in Heap, jeder sein eigener Repräsentant, oberste Kante entnehmen, falls Repräsentanten verschieden wird ein Knoten Repräsentant des anderen, solange bis n-1 Kanten gefunden, zum Finden der Repräsentanten Path-halving)

Wie würden Sie denn einen Heap implementieren?
Array mit erstem Eintrag = Wurzel, andere Einträge aufgereiht in Ebenen
Dann habe ich erklärt, wie man einen Heap aufbaut und warum man von unten anfängt (weil man dann sicher sein kann, dass darunter alles sortiert ist).

Wie ist die Laufzeit des Aufbauens eines Heap?
O(n), da eigentlich nur die Wurzel wirklich log(n) Schritte siften kann und der Rest immer nur 1-2 Ebenen

Wofür kann man Heap noch verwenden?
Dijkstra Algorithmus erklärt (alle Knotenkosten auf unendlich, Startknoten auf 0, Startknoten in den Heap, Wurzel entnehmen und alle Kanten durchlaufen und zugehörige Knoten evtl. updaten und in den Heap einfügen, solange bis Heap leer ist)

Weshalb kann man den Heap aus der Vorlesung dafür nicht verwenden?
Man kann einzelne Knoten im Heap nicht herausholen und updaten -> die Knoten werden doppelt eingefügt und falls durchlaufen, auf seen gesetzt

Wie funktioniert denn jetzt HeapSort und was ist die Laufzeit?
Wurzel entnehmen, hinten ins Array kopieren und mit letztem Blatt tauschen, Wurzel siften bis komplettes Array sortiert (rechte Grenze = 1)
O(n*log n) -> n * Wurzel entnehmen und siften (log n)
Ist das eine gute Laufzeit für Sortieralgorithmen?
Ja, die bestmögliche Laufzeit für Sortieren mit Vergleichen. Wenn man sich das anhand eines Entscheidungsbaums vorstellt: n Elemente zu sortieren, n! Blätter, Höhe log(n!) > n/4 * log(n) = O(n*log n)

Welche Sortieralgorithmen kennen Sie noch?
SelectionSort, BubbleSort, MergeSort, QuickSort

Wie funktioniert QuickSort und was ist die Laufzeit?
Pivot-Element, i läuft von links solange xPivot, tauschen und weiterlaufen bis i>j, Aufruf von linker und rechter Hälfte
Best & average case: O(n*log n), worst case: O(n2) falls Pivot kleinstes/größtes Element

Info B

Erklären Sie das Substitutionsprinzip.
Objekt der Unterklasse sollte Objekt der Oberklasse ersetzen können -> Unterklasse spezialisiert und erweitert Oberklasse
Kovarianz, Kontravarianz und Invarianz erklärt und Beispiele im Hinblick auf Rückgabetyp und Parameter aufgezeichnet

Themenwechsel: wir würden Sie eine GUI implementieren?
Ich habe allgemein über AWT, Components, Container erzählt und danach Beispielcode mit einem Panel, einem Button und einem LayoutManager aufgeschrieben.

Und was fehlt jetzt noch?
Das Event-Handling: MouseListener extends (habe erst implements geschrieben, aber Adapterklassen sind abstrakte Klassen) MouseAdapter beispielhaft aufgeschrieben und an Button gehängt, zusätzlich erklärt, welche Informationen ein Event enthält und woher es kommt (von der Source, in diesem Fall der Button)

Welches Pattern wird bei der GUI Implementierung häufig genutzt?
Observer-Patter mit Subject und Observern erklärt sowie das UML Diagramm aufgezeichnet und die Reihenfolge der Aufrufe bei Änderung des Subject dargelegt

Was mußte schriftlich gelöst werden?

- Dijkstra-Algorithmus anhand einer Zeichnung erklären
- Substitutionsprinzip anhand eines UML-Klassendiagramms erklärt sowie Beispielcode in Form von Methoden mit versch. Rückgabetypen und Parametern
- Beispielcode für die GUI Implementierung
- UML-Diagramm zum Observer Pattern

Persönlicher Kommmentar, Was war toll? Was war doof? Was war auffällig?

Beide waren sehr freundlich und haben aufmerksam zugehört, wobei derjenige, der gerade keine Fragen gestellt hat, Protokoll geführt hat. Falls man etwas verwechselt hat, wurde noch einmal freundlich nachgefragt und das wurde auch bei der Bewertung nicht negativ berücksichtigt.

Wie waren Einstieg, Ablauf, Ende, Bewertung und Begründung?
Vornberger: Legen Sie sich ab, setzten Sie sich hin und beantworten Sie alle Fragen.
Ich: Ich hoffe, dass ich das kann.
Und dann gings auch schon los.

Am Ende wurde ich für eine Minute rausgeschickt und nach der Beratung mit den Worten „wir haben Ihnen eine 1,0 verpasst“ entlassen. Eine Begründung dafür gab es nicht.

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

Beide Prüfer haben sich vorher eine Liste mit Dingen gemacht, auf die Sie eingehen wollten. Abgesehen von kleinen Hilfestellungen und Zwischenfragen bei Ungenauigkeiten haben meine Antworten den Verlauf der Prüfung meiner Meinung nach nicht beeinflusst.