Computer Science, 2013-04-04

Module: 
Computer Science
Examiner: 
Oliver Vornberger
Assessor: 
Elke Pulvermüller
Date: 
Thu, 2013-04-04

Formalia

Modulprüfung: Informatik Fachsemester: 5
Prüfer/2.Prüfer: Prof. Dr. Oliver Vornberger / Prof. Dr.-Ing Elke Pulvermüller

Vorbereitung

Was hast du zur Prüfungsvorbereitung benutzt?

Die Skripte von Info A und B, habe die jeweils durchgearbeitet und zusätzlich noch einige der Vorlesungsvideos aus Info A genutzt.

Prüfung

Wiederholungsprüfung? nein
Note: 1.0
Bereiche nach Zeit: Info A 15 Min, Info B 15 Min

Fragensammlung: wie lauteten die Fragen im einzelnen?

Die Antworten waren natürlich in der Situation weniger gut formuliert, geben aber inhaltlich wieder wie ich geantwortet habe. Nachdem ich die eine Frage zur unteren Schranke nicht so recht beantworten konnte, war ich recht nervös, das fiel aber scheinbar nicht so sehr ins Gewicht.

Info A

Vornberger: Wir haben uns in der Vorlesung ja mit Heaps beschäftigt, was ist das denn?
Ich: Ein Heap ist ein vollständiger binärer Baum, indem die Söhne eines Knotens größer sind als ihr Vater.
Vornberger: Wie würde man das denn implementieren?
Ich: In einem Array, durch die Vollständigkeit des Heaps ist jeder Knoten eindeutig identifizierbar.
Vornberger: Wie greift man denn dann auf einen Knoten zu?
Ich: Ein Knoten i ist im Array an Stelle i zu finden, seine Söhne an den Stellen i*2+1 und i*2+2.
Vornberger: Welche Funktionen stellt ein Heap zur Verfügung?
Ich: init_heap, get_min, del_min, ...
Vornberger: Was kann man denn mit diesem Heap jetzt genau machen?
Ich: Man kann sehr gut und effizient sortieren?
Vornberger: Wie sortiert man in einem Heap?
Ich: Die besondere Eigenschaft eines Heaps ist, dass das Minimum des Heaps immer in der Wurzel steht. Das Sortieren einer Folge in einem Heap läuft dann so ab, dass zuerst ein Heap konstruiert wird, und aus diesem Heap immer das Minimum entfernt wird und der Heap repariert wird, bis nur noch die Wurzel übrig ist.
Vornberger: Wie sieht das Array dann aus?
Ich: Man schreibt das entfernte Minimum des Heaps immer an das Ende des Arrays, dadurch ist das Array dann eine absteigend sortierte Folge der Zahlen.
Vornberger: Wie repariert man nach dem Entfernen des Minimums den Heap?
Ich: Man löscht das Minimum und schreibt dann den "letzten" Wert des Heaps (also der Wert, welcher in der untersten Ebene an der letzten Stelle steht) in die Wurzel des Heaps und lässt ihn nach unten sickern, bis die Heapbeziehung wieder eintritt.
Vornberger: Welche Laufzeit hat das Sortieren dann?
Ich: O(n*log(n))
Vornberger: Ist das gut?
Ich: Optimal, O(n*log(n)) ist die untere Schranke für Sortieren durch Vergleichen.
Vornberger: Was ist eine untere Schranke für ein Problem?
Ich: Die untere Schranke gibt die Laufzeit an, welche ein konkreter Algorithmus mindestens braucht um ein Problem P zu lösen.
Vornberger: Warum ist die untere Schranke für Sortieren durch Vergleichen O(n*log(n))?
Ich: Öhm..... weil man immer einen Aufwand von n für das aufbauen des Heaps und log(n) für das Finden von Objekten braucht?
Vornberger: Nein, wir hatten doch in der Vorlesung einen Entscheidungsbaum für Sortieren durch Vergleichen, wieviel Blätter hat der denn?
Ich: Äh... Vielleicht n? Oder 2^n? (auf mehrmaliges Kopfschütteln von Vornberger dann bis zu n! durchgeraten...)
Vornberger: Und warum braucht man jetzt O(n*log(n)), wenn der Entscheidungsbaum n! Blätter hat?
Ich: Äh... Hm... (schließlich mit Hilfe von Vornberger zusammengeraten, dass die Höhe dieses Baums dann der log(n)*n ist und deshalb die untere Schranke für Sortieren durch Vergleichen dadurch gegeben ist)
Vornberger: Mal was Anderes. Was ist denn eine sehr einfache Art, ein Programm zu formulieren?
Ich: Ein endlicher Automat
Vornberger: Was ist ein Endlicher Automat?
Ich: Ein endlicher Automat ist ein Fünftupel, bestehend aus endlicher Zustandsmenge, endlichem Eingabealphabet, Startzustand, Menge von Endzuständen und einer Überführungsfunktion.
Vornberger: Und kann man damit alle Java-Programme formulieren?
Ich: Nein, einem endlichen Automaten fehlt das "Gedächtnis".
Vornberger: Zeigen sie mal, wie so ein endlicher Automat aussehen könnte.
Ich: (male und erkläre das Beispiel aus der Vorlesung: endlicher Automat der für binäre Zahlen bestimmen kann, ob sie durch drei teilbar sind oder nicht)
Vornberger: Und wie sähe das dann in Java aus, nur so grob?
Ich: Durch ein zweidimensionales Array, welches die Zustandsüberführungsfunktion repräsentiert, in einer Zelle des Arrays steht jeweils, zu welchem Zustand aus Zustand X bei Eingabe Y überführt wird.
Vornberger: Dann mal noch was Anderes, was ist denn Rekursion?
Ich: Rekursion ist, wenn ein Programm sich selbst im Methodenrumpf aufruft. Die Idee dahinter ist, das ursprüngliche Problem zu reduzieren, und das kleinere Problem dann mit der gleichen Logik zu lösen.
Vornberger: Dann erklären sie doch mal, wie QuickSort rekursiv funktioniert.
Ich: Auswahl des Pivot-Elements, Partition der Folge in elementweise größere und elementweise kleinere Folge. Diese Folgen werden dann rekursiv wieder von Quicksort sortiert. (ich habe den Algorithmus da recht detailliert erklärt, mit Grenze Oben, Grenze Unten, etc.)
Vornberger: Welche Laufzeit hat das dann?
Ich: Im average und best Case O(n*log(n)), im worst Case O(n^2), weil es durch eine ungünstige Wahl des Pivot-Elements es passieren kann, dass pro Durchlauf die eine Folge immer nur ein Element enthält. Das Optimum wäre, den Median als Pivotelement zu wählen.
Vornberger: Ok, danke.

Info B:

Pulvermüller: Dann fangen wir mal an, was sind denn wichtige Konzepte der objektorientierten Programmierung?
Ich: Modularität, Kapselung, Geheimnisprinzip, Klasse, Objekt, Instanz.. (da habe ich dann noch ein bisschen von der Abbildung der realen Welt in Klassen und Objekte geschwafelt und mich noch in der Beschreibung von Geheimnisprinzip und Kapselung verwirklicht)
Pulvermüller: Und sonst noch?
Ich: Es gibt noch weitere Konzepte wie Typing, Polymorphism etc, die aber für OOP weniger wichtig sind.
Pulvermüller: Und sonst noch?
Ich: Ähh...
Pulvermüller: Vererbung!
Ich: Jaja, Vererbung!
Pulvermüller: Was kann es denn für Probleme bei der Vererbung geben?
Ich: Ein Problem der Vererbung ist das der fragile base class. Das bedeutet, wenn wir eine große Klassenhierarchie haben, in der viele Klassen von einer Klasse direkt oder indirekt erben, und diese Klasse verändert wird, müssen alle Klassen, an die vererbt wird, auch geändert werden. Ein weiteres Problem kann entstehen, wenn man Mehrfachvererbung in einer Programmiersprache hat. Das ist dann z.B. das Diamond Inheritance Problem, welches entsteht, wenn eine Klasse von zwei Klassen erbt, die wiederum beide von einer gemeinsamen Klasse erben. Dann weiß die Klasse, die von diesen beiden Klassen erbt, nicht, von welcher der beiden Klassen sie erben soll, weil beide auch die gleichen Methoden halten.
Pulvermüller: Wenn man das Konzept trotzdem in einer Programmiersprache haben möchte, was macht man dann?
Ich: Dann könnte man stattdessen Mehrfachimplementierung erlauben, wie es in Java geschieht. Eine Klasse darf mehrere Interfaces implementieren.
Pulvermüller: Kann es dann trotzdem Probleme geben?
Ich: Ja, es gibt da zwei Probleme. Erstens, könnten die gleiche Konstante in mehr als einem Interface enthalten sein (final static int ...), zweitens könnte es sein, dass beide Interfaces die gleiche Methode enthalten, allerdings mit einem unterschiedlichen Rückgabetyp.
(hier irgendwelche Fragen zur Sinnhaftigkeit von Schnittstellen oder Vererbung oder so, bliblablub)
Pulvermüller: Ok, dann mal ein anderer BereIch: Threads. Was ist denn Nebenläufigkeit?
Ich: Nebenläufigkeit heißt, dass zwei Programme in keinem kausalen Zusammenhang zueinander stehen und deshalb parallelisiert werden können. Da gibt es Multitasking und Multiprocessing. Während bei Multitasking Nebenläufigkeit nur vorgespielt wird, indem Prozesse jeweils abwechselnd ausgeführt werden, bedeutet Multiprocessing, dass tatsächlich auf verschiedenen Prozessoren gerechnet wird.
In Java gibt es das Sprachkonstrukt Thread, welches auf native Threads abbildet (Threads sind leichtgewichtige Prozesse).
Pulvermüller: Wie werden denn dann Threads implementiert? Schreiben Sie doch mal Beispielcode.
Ich: Entweder, man implementiert das Interface "Runnable" und übergibt das Objekt an einen Thread, welchen man mit t.start() startet. Alternativ erbt man von der Klasse Thread (welche das Interface Runnable implementiert) und startet diesen Thread direkt. Außerdem kann man noch ein Executer-Objekt erstellen, an welchen Threads / Runnables übergeben werden und der die Ausführung überwacht. (schreibe eine Klasse, die das Interface Runnable implementiert, inklusive leerer Methode "run", erzeuge Objekt dieser Klasse und übergebe es einem Thread, den ich mit t.start() starte)
Pulvermüller: Sie haben da run() implementiert, warum wird denn start() aufgerufen und nicht run()?
Ich: Der Aufruf von run() würde nicht zur nebenläufigen Verarbeitung führen, das sähe höchstens so aus, der Unterschied wäre aber schon an der Laufzeit zu bemerken.
Pulvermüller: Malen Sie doch mal ein UML-Diagramm der Klasse, die sie da implementiert haben.
Ich: (male UML-Diagramm mit MyRunnable, welches Runnable implementiert und male eine Aggregations-Beziehung zu einem Thread. Kurze Verwirrung, weil ich die Objekte unterstrichen habe, habe das dann einfach wieder durchgestrichten, außerdem falsch: Ich hatte den Pfeil unter <> durchgehend statt gestrichelt gemalt, er hat Jehova gesagt!!!)
Pulvermüller: Was kann es denn jetzt für Probleme bei der Nebenläufigkeit geben?
Ich: Immer, wenn zwei Threads auf eine gemeinsame Ressource zugreifen. Da gibt es dann z.B. Lost Update, wenn einer schreibt und einer liest und das Update des Schreibenden nicht mehr übernommen wird. Außerdem gibt es z.B. Dirty Read, wenn eine Inkonsistenz der gelesen Daten entsteht, weil während der Verarbeitung ein anderer Thread die Daten verändert.
Pulvermüller: Ist das Schlüsselwort "volatile" eine Lösung für das Problem?
Ich: Nein, nur teilweise. Das sperrt zwar den Zugriff auf eine Variable, allerdings nur für einen Byte. Falls wir eine Variable haben, welche mit 2 Bytes codiert ist, kann es wieder Probleme geben.
Pulvermüller: Was macht man also dann?
Ich: Dann sperrt man die "Critical Section", indem man ein Monitor Objekt einsetzt und den Block daran synchronisiert. Das geht für Methoden entweder über das Schlüsselwort synchronized oder für Blöcke mit synchronized(this) {...}. Außerdem könnte man eine Semaphore einsetzen, die es erlaubt, zu spezifizieren, wieviele Objekte in den kritischen Bereich eintreten dürfen.
Pulvermüller: Wir haben ja vorhin über Rekursion gesprochen, welche Eigenschaft der Synchronisation ist denn für die Rekursion vital?
Ich: Die Reentranz. Das bedeutet, das ein Objekt, welches einen kritischen Bereich betreten darf, den auch wieder betreten darf. Ohne die Reentranz wäre Rekursion nicht möglich, weil der rekursive Prozess diesen Abschnitt nur einmal bearbeiten dürfte.
Pulvermüller: Ok, dann mal noch zu einem anderem Thema: GUIs. Schreiben sie doch da mal ein bisschen Code für eine graphische Oberfläche.
Ich: (importiere java.awt.*, erstelle Frame, Panel, Button, mache Button visible, erkläre dass ich jetzt noch einen LayoutManager an das Panel basteln könnte und einen ActionListener an den Button).
Pulvermüller: Ja bauen sie doch da mal nen ActionListener dran!
Ich: (baue ActionListener mit anonymer innerer Klasse an den Button und implementiere public void actionPerformed(ActionEvent e)
Pulvermüller: Muss die Methode actionPerformed implementiert werden?
Ich: Ja, weil ich einen ActionListener implementiere. Wenn ich aber z.B. einen MouseListener bauen würde, wo ich nicht alle Methoden benötige, würde ich einen MouseMotionAdapter() erstellen, der alle notwendigen Methoden leer implementiert. Die benötigten Methoden würde ich dann überschreiben.
Pulvermüller: Ja. Was ist denn das Event Delegation Model?
Ich: (erkläre mit gestenreicher Visualisierung, wie im Event Delegation Model Event-Quelle, Event-Listener und Event zusammenhängen)
Pulvermüller: Und wie hängt das mit der JVM zu tun?
Ich: Ja, bestimmt irgendwie! (mal ernsthaft, was hängt denn NICHT mit der JVM zusammen?)
Pulvermüller: Tja, und wie wohl?
Ich: Hmm.... vielleicht übernimmt die das irgendwie, den EventListener anzuwerfen...?
Pulvermüller: Jaja. Dann sind wir fertig!

Die Beiden schicken mich raus, holen mich nach 2 sec wieder rein, geben mir 1.0 und machen ein bisschen Smalltalk, hatten Sie Java schon in der Schule, wo machen Sie die Bachelor-Arbeit, war das Ihre letzte Modulprüfung, wie haben sie gelernt...

Was mußte schriftlich gelöst werden?

Für Info A musste ich einen Beispiel-Heap malen, die Array-Implementation davon andeuten und den endlichen Automaten aufmalen. Für Info B habe ich einmal Beispiel-Kot bezüglich Threads und GUI geschrieben, außerdem musste ich das UML-Diagramm für die Implementation von MyRunnable aufzeichnen.

Welche Beispiele wurden wofür abgefragt?

s.O.

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

Die beiden waren sehr nett und korrekt, haben geholfen und nicht verunsichert.

Wie waren Einstieg, Ablauf, Ende, Bewertung und Begründung?

s.O.

Bewertung und Begründung:

Gab keine weitere Begründung zu der 1.0.

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

Ich habe es kaum versucht. Wenn man nun wirklich möchte, könnte man vermutlich in Info B z.B. vom Kleinen aufs Kleinste kommen und so lange reden, dass keine Fragen mehr dazwischen passen, aber das habe ich nicht getestet ;)

Zum Verhalten des Prüfers:

Beide sehr nett!