Computer Science, 2016-04-06

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

Formalia

Modulprüfung: Info A, Info B
Fachsemester: 7
Wiederholungsprüfung? nein
Note:1.0
Bereiche nach Zeit: jeweils ca 10min

Vorbereitung

Info A: Skript, Vorlesungsvideos
Info B: Skript, Wikipedia
wichtig ist sich auch mal abfragen zu lassen, damit man sich gute Formulierungen einprägt.

Wie lauteten die Fragen im einzelnen?

Info A

Rekursion was ist denn das?

Methode kann im Methodenrumpf den eigenen Namen verwenden, sprich sich selber aufrufen. Dies ist ein Rekursvier Aufruf. Dort werden die Parameter verkleinert, z.b. mit Aufruf mit n-1. Das heißt das Problem schrumpft mit jedem Aufruf bis es nicht mehr vorhanden ist. Dann ist der Rekursionsanker erreicht und das Programm bricht ab.

Wie wird das in den Türmen von Hanoi benutzt?

Man hat 3 Plätze:Start, Zwischen und Ziel und N Scheiben von klein nach groß auf Start. Das Ziel ist jetzt alle Scheiben nach Ziel zu verlegen, wobei immer nur eine Scheibe zur Zeit verlegt werden darf und nie eine größere Scheibe auf einer kleineren liegen darf.
Die rekursive Lösung ist, wenn man n-1 Scheiben von Start über Ziel nach Zwischen legt, dann kann man die nte Scheibe auf Ziel legen und dann n-1 Scheiben von Zwischen über start nach Ziel.

Und was ist die Laufzeit bzw Rekursionsgleichung?

1 für n=1 sonst f(n) = 2*f(n-1) + 1

Und was ist jetzt die explizite Funktion?

Hier stand ich erst relativ auf dem Schlauch. Ich wusste, dass die Laufzeit exponentiell ist, also 2^n. Aber das hat ihm nicht gereicht.
Dann hat er mich eine Tabelle zeichnen lassen mit wieviele Operationen wir bei n=1,2,3,4 Eingaben haben. Und damit bin ich dann auf f(n)= 2^n - 1 gekommen.

Und was ist an dieser Laufzeit schlecht?

Steigt sehr schnell proportional zur Eingabe. Er wollte aber noch wissen wie das Proportional steigt. Auch hier war ich wieder etwas überfordert. Er wollte darauf hinaus, dass sich z.b wenn man für eine Eingabe 1 Stunde Rechenzeit hat und jetzt eine weitere Eingabe hat, dass sich die Laufzeit verdoppelt, also (1+1)^2 = 4

Rekursion wird ja noch bei Sortieralgorithmen verwendet. Erklären sie mal Quicksort.

Folge von Daten in elementweise kleinere und Elementweise größere Folge teilen und diese dann rekursiv mit der gleichen Methode sortieren.

Und wie macht Quicksort das?

2 Zeiger einer von links einer von rechts. Wenn Element links größer als Pivot und links kleiner als Pivotelement --> Tauschen. Dies macht man bis die Zeiger sich kreuzen. Und dann das gleiche mit den Hälften.

Und die Laufzeit?

n fürs elementweise Sortieren und log(n) für das rekursive Aufrufen der Hälften. Also n*log(n).

Ist das immer so?

Nein, im Worstcase, also wenn das Pivotelement immer das größte/kleinste ist, wird die Laufzeit n^2.

Nun zu ungerichteten und auch noch gewichteten Graphen. Was gibt es denn da?

Minimum Spanningtree nach Kruskal. Billigste Verbindung aller Knoten.
Erst Wald von einzelnen Knoten und Heap mit Kanten(Da oben Minimum).
Billigste Kante aus Heap nehmen, wenn die Knoten der Kante noch nicht im gleichen Baum --> verbinden. Solange bis alle Knoten verbunden.
Um zu überprüfen ob 2 Bäume schon verbunden ist gibt es eine Chef Variable. Jeder Knoten zeigt auf einen weiteren Knoten, der sein Chef ist. Der letzte Knoten ist sein eigener Chef und übernimmt quasi die Rolle des Chefs für den ganzen Baum. Wenn jetzt " Bäume nicht den gleichen Chef haben, kann man sie verbinden und muss dann nurnoch den einen Verweis auf den andren Chef umbiegen.

Info B

Was ist ein Singleton

Entwurfsmuster bei dem immer nur eine Instanz von einer Klasse existieren darf. Etwas Code aufgezeichnet(Den Logger aus dem Skript). Muss private Klassenvariable haben von der Instanz der Klasse, privaten Konstruktor undeine public Klassenmethode zur Erzeugung eines Loggers.
Natürlich muss es auch noch eine Instanzmethode log geben die irgendwas tut.

Könnte die static Instanz der Klasse auch eine Isntanzvariable sein?

War erst etwas verwirrt, aber sie wollte darauf hinaus, dass das nicht möglich ist, da ja die getInstance Methode static ist und nicht auf Instanzvariablen zugreifen kann, da es ja sein kann das es noch garkein Objekt der Klasse geben muss.

Jetzt zur Serialisierung. Was ist das und was kann es für Probleme geben?

Bisschen Code aufgemalt. write Methode vom ObjectOutputStream macht die Serialisierung. Klasse muss Serializable implementieren(Sonst notSerializable Exception).

Und Probleme bei der Deserialisierung?

Wenn sich die Klasse verändert, kann es sein, dass das serialisierte und das aktuelle Objekt nichtmehr zusammenfassen, dann dürfte man nicht mehr deserialisieren. Dafür könnte man eine Versionsnummer einführen die sich ändert wenn sich das Programm ändert. Kritische Änderungen wären, wenn man Instanzvariablen weglässt oder von non transient auf transient wechselt.

Was sollte nicht serialisiert werden?

Sensible Daten, da man sonst auf diese von außen zugreifen könnte.
Klassenvariablen, weil sie ja nicht zu einem speziellen Objekt gehören.

Serialisierung und Vererbung wie läuft das?

Wenn die Superklasse serialisierbar ist ist auch die Subklasse serialisierbar. Wenn in der Subklasse auf Objekte der Superklasse verwiesen wird werden diese auch serialisiert.
Wenn nur die Subklasse serialisierbar ist, können Referenzen auf die Superklasse nicht serialisiert werden. Bei der deserialisierung würde der Defaultkonstruktor(parameterlos) der Superklasse aufgerufen. Wenn dieser nicht mehr existiert gibt es einen Fehler.

Jetzt noch etwas zu Synchronisation und Nebenläufigkeit. Was für Probleme kann es bei Synchronisation geben?

Deadlocks, am Beispiel der Dining Philosophers erklärt...Alle nehmen das linke Stäbchen und dann kann nichts weitergehen.

Und ein anderes Problem?

Producer-Consumer.
Producer tut etwas in ein begrenzt großen Speciherbereich und Consumer nimmt etwas heraus. Wenn voll muss Producer warten, wenn leer Consumer.
Busy wait Situation, welche sehr rechenintensiv ist. Daher sollte man Semaphoren benutzen(wait und notify bei synchronized)

Und am Schluss noch eine Frage, wie läuft das mit den inneren Warteschlangen bei wait und notify?

Hier hatte ich leider eine Lücke, aber wusste das es eine äußere und innere Warteschlange gibt. Worauf sie hinauswollte, war, dass wenn ein Objekt in der innern Warteschlange mit notify "geweckt" wird muss es trotzdem mit denen aus der äußeren um den Platz kämpfen.

Das wars dann auch schon.

Was musste schriftlich gelöst werden?

Man darf und soll durchaus auch eigenständig was Zeichen zur Verdeutlichung.

Info A

Rekursionsgleichung Türme von Hanoi, sowie Wertetabelle.

Info B

Etwas Code zum Singleton und zur Synchronisation.

Wie war der Ablauf?

War etwas früher da, sollte dann Frau Pulvermüller holen und dann ging es direkt los mit Info A und dann nahtlos zu info B über.
Nach 25 Minuten war die Prüfung auch schon vorbei.

Bewertung und Begründung

Haben nur 20 Sekunden beraten. Haben gesagt, man hat gemerkt das ich den Stoff komplett verstanden und durchdrungen habe, aber noch etwas präziser hätte antworten können. Daher als Tip noch mehr abfragen lassen.

Zum Verhalten der Prüfer:

Beide waren gut gelaunt und freundlich. Wenn man etwas ins stocken kam, wurde nochmal nachgehakt und ich hatte das Gefühl sie haben sich Mühe gegeben mich in die richtige Richtung zu lenken.
Auch wenn man eine Kleinigkeit nicht ganz richtig war, wurde nicht böse geguckt oder so.