Computer Science, 2015-08-05

Module: 
Computer Science
Examiner: 
Prof. Vornberger
Assessor: 
Prof. Pulvermüller
Date: 
Wed, 2015-08-05

Vorbereitung

  • Ungesunde Mengen an Vorlesungsskript (10-mal alles durchlesen und hoffen, dass man nicht vor Langeweile stirbt). Detaillierte Implementierungen kann man gut aussparen, es sei denn es ist so simpel, das man das in 5 Minuten selbst hinkriegen würde.
  • Vorlesungsaufzeichnungen angucken
  • Bisschen googlen bei Unklarheiten (Wie funktionieren Wildcards mit Upper- und Lower Bounds? Interessant, aber für die Prüfung ziemlich sicher egal)

Prüfung

  • Wiederholungsprüfung? nein
  • Note: 1.0
  • Bereiche nach Zeit: 10/10

Informatik A

Was ist denn Rekursion?

Methode ruft sich selbst auf, blablabla. Habe dann gleich weitergeredet,
wozu das denn gut ist. Das is nützlich, wenn man ein Problem in kleinere
Teilinstanzen zerlegen kann, bis man dann bei einem ganz einfachen Fall
angekommen ist. z.B. bei Divide-And-Conquer-Algorithmen ist das
praktisch (so wie bei Quicksort).

Ok, wie benutze ich das denn bei Quicksort?

Man hat eine Folge von Zahlen und teilt die immer in 2 (idealerweise gleich
große Teile), indem man ein Pivotelement wählt, und immer
tauscht, wenn man links eins findet, das größer ist, und rechts
eins, das zu klein ist.

Wie lange dauert das denn? Also das teilen in 2 Teile

Dauert linear lange, man muss ja nur einmal durch das Array durch, evtl.
für jede Position tauschen.

Und der Gesamtaufwand?

Wenn man Glück hat, ist das Pivotelement immer der Median, dann
halbiert sich die Folge in jedem Aufruf, das geht dann logarithmisch oft,
bis die Länge der Folge 1 beträgt. Dann eben O(n · log n).

Und wenn es schlecht läuft?

Dann erwischt man in jedem Aufruf das kleinste oder größte
Element, welches dann beim ersten Tauschen ganz ans Ende wandert, sodass
man dann ein Intervall der Länge 1 hat und eins der Länge n - 1.
Dann ist das natürlich quadratisch.

Kann man denn sicherstellen, immer den Median zu finden?

Ja, das geht in Linearzeit, dann hätte man in jedem der log n Aufrufe
eben 2 · n Aufwand, das würde an der asymptotischen Laufzeit nichts
änern, aber da es sowieso ziemlich selten ist, dass der worst case
auftritt, lohnt sich der Mehraufwand in der Praxis nicht.

Wenn ich auch im Worst Case O(n · log n) haben will?

Dann würde ich ein anderes Sortierverfahren nehmen, z.B. Mergesort,
wenn Platz kein Problem ist, oder Heapsort, der O(n · log n) in-place
garantiert.

Ok, was ist denn ein Heap?

Ein binärer Baum, der bis auf die letzte Ebene voll besetzt ist. Dabei
erfüllt jeder Knoten die Heapbeziehung, also (beim Min-Heap, beim
Max-Heap wäre es andersrum) dass der Vaterschlüssel kleiner als
die Kindschlüssel sind.

Wie könnte man so einen Heap denn implementieren?

Auf 'nem Array, das geht, weil der Heap voll besetzt ist, sonst wären
Löcher im Array. So kann man aus dem Index des Vaterknotens die
Indizes der Söhne berechnen.

Generell, was kann der Heap so?

Habe etwas rumgeschwafelt, dass er aus einer Menge von Elementen, die eine
totale Ordnung haben, immer das kleinste/größte bereithalten
kann.

Wie lange dauert das Löschen des Minimums?

Das dauert logarithmisch lange. Damit der Heap danach immer noch voll
besetzt ist, schreibt man das letzte Element in die nun leere Wurzel und
muss dann sicherstellen, dass die Heapbeziehung wieder erfüllt ist. Der
Knotenschlüssel könnte ja größer als seine Kinder sein.
Also tauscht man immer mit dem kleineren Kind. Der Aufwand ist offenbar
proportional zur Tiefe des Baums, und die ist nunmal logarithmisch (weil
voll besetzt).

Ok, Themawechsel, was ist denn ein endlicher Automat?

Der hat Zustände, ein Eingabealphabet, Eine
Zustandsüberführungsfunktion, die Zustände und Eingaben auf
Folgezustände abbildet. Dann sollte er noch eine – idealerweise
nichtleere – Teilmenge der Zustände haben, die Endzustände sind.

Was kann so ein Automat?

Die Dinger sind äquivalent zu regulären Sprachen, es gibt also
für jede einen Automaten, der die Wörter einer bestimmten
regulären Sprache akzeptiert. (Weiß nicht genau, was Vornberger
eigentlich hören wollte, habe einiges erzählt, was mir aus Info D
noch in Erinnerung war).

Ok, malen sie mal eien Automaten, der alle Wörter akzeptiert, die
aus {0,1} bestehen und auf 1 enden.

Hab ich dann aufgemalt, 2 Zustände, fertig.

Könnte man jetzt auch einen bauen, der die Wörter akzeptiert,
die gleich viele Nullen und Einsen enthalten?

Ne, geht nicht, weil der Automat kein Gedächtnis hat, dafür
bräuchte man dann einen Kellerautomaten.

Ok, das ist jetzt ein einfaches Maschinenmodell, könnte so ein
Automat auch Java-Programme verarbeiten?

Ne, Programmiersprachen sind eigentlich kontextsensitiv, aber mit etwas
Trickserei macht man sie deterministisch kontextfrei, der Automat kann aber
eben nur reguläre Sprachen.

Wie haben wir den denn in der Vorlesung implementiert?

2-dimensionales Array, für jeden Zustand eine Zeile, für jede.
Eingabe eine Spalte, und in jeder Zelle (x,y) steht dann für Zustand x
und Eingabe y der Nachfolgezustand drin.

Springen wir mal woanders hin, ungerichtete Graphen. Was könnte
einen denn da so interessieren?

Man könnte einen minimalen Spannbaum suchen, oder
All-Sources-Shortest-Path oder Single-Source-Shortest-Path lösen.

Oder Chinese Postman, was können Sie dazu denn sagen?

Man sucht eine Kantenrundreise, die alle Kanten abläuft und
möglichst billig ist. Wenn der Graph ein Eulergraph ist, dann ist es
leicht, man fängt an wo man will und wählt von jedem Knoten aus
immer die erstbeste noch nicht besuchte Kante. Weil die Knoten geraden Grad
haben, kommt man von jedem Knoten auch immer wieder weg mit einer
unbesuchten Kante. Das kann nicht unendliche lange gehen, also ist man
irgendwann fertig.

Wenn das kein Eulergraph ist, sucht man die Knotenteilmenge mit ungeradem
Kantengrad, die Probleme macht. Auf der Clique (alle Knoten werden mit allen verbunden) sucht man dann ein
Minimum-Cost-Matching.

Ja, aber was müssen Sie vorher noch machen?

(Ich bin kurz baff.) Achso! Man muss mit Floyd die kürzesten Wege
zwischen den Problemknoten und die Kosten bestimmen. Dann kann ich diese
Info nutzen, um das Matching zu finden und verdopple im Originalgraphen
alle Kanten entlang dieser kürzesten Wege gemäß Floyd.

Informatik B

Allgemein hab ich ziemlich viel mehr oder weniger kohärentes Zeug
erzählt, ich denke, wenn genug Richtiges dabei ist, ist Frau
Pulvermüller zufrieden. Ein paar konkrete Details will sie aber schon
hören, die waren in meinem Wortschwall aber wohl meist immer schon drin.

Wie würden sie jemandem Vererbung erklären, der C++ & Java lernen will?

Allgemein modellieren Objekte Kategorien aus der Welt, man kann dann z.B. eine Klasse für Obst bilden und dann Äpfel und Birnen als Subtypen, die alle Eigenschaften des Supertyps haben und noch mehr. Habe irgendwie rumgesülzt, bis sie zum nächsten Thema übergegangen ist.

Welche Probleme gibt's denn da, und hängt das von der Sprache ab?

Mehrfachvererbung – wenn erlaubt – könnte problematisch sein. z.B. wenn verschiedene Supertypen die selbe Methodensignatur enthalten, wobei die Methode unterschiedliche Rückgabewerte hat (2 identische Signaturen in Java sind nicht in einer Klasse erlaubt).

Gibt es trotzdem ein Problem in Java bei der Sache (obwohl Mehrfachvererbung nicht erlaubt ist)?

Bei Interfaces in Java gibt es echte Mehrfachvererbung, da kann dann, wenn jemand ein Interface mit mehreren Superinterfaces implementieren soll, das selbe Problem wie vorher auftreten. Das würde dann halt gar nicht erst kompilieren. Was kompiliert, ist aber, wenn man aus mehreren Interfaces verschiedene Konstanten mit dem gleichen Namen bekommt. Das geht dann, man muss aber den Zugriff entsprechend qualifizieren, verwirrend ist es trotzdem.

Was ist denn ein Decorator, können sie das mal aufmalen?

UML gemalt so ähnlich wie im Skript. Es gibt die Component, die
ist abstrakt und definiert irgendein Verhalten. Davon erben tun konkrete
Components, die die Schnittstelle implementieren, und Decorators, die (mindestens) ein Objekt vom Typ Component aggregieren. Das könnte dann wieder ein Decorator sein, oder eine konkrete Component, der Client muss es nicht unbedingt wissen, weil durch die Vererbung beide den selben Typ haben (auf den Punkt wollte sie auf jeden Fall hinaus). Der Decorator wird dann, wenn der Client ihm sagt "mach mal", sein eigenes Verhalten ausführen, aber auch das von der Component, die er dekoriert. Das könnte dann rekursiv so weiter gehen.

Wo in der Java-Standardbibliothek wird das denn benutzt?

Bei den IO-Klassen, also Streams.

Können Sie mal ein Beispiel zur Serialisierung machen?

Bisschen auf Papier gecoded. Wir haben ein Objekt, dann bauen wir einen ObjectOutputStream und geben dem einen FileOutputStream. Letzterer wäre dann in dem UML-Diagramm die konkrete Component und wird vom OOS dekoriert. Dann ruft man writeObject() auf, fertig.
Deserialisieren geht dann andersrum mit ObjectInputStream und FileInputStream und readObject(). Die Klassen müssen dafür Serializable implementieren (was nur ein Markerinterface ist) und die Methoden private void readObject(ObjectInputStream in) und private void writeObject(ObjectOututStream out).

Kann es zu Problemen kommen? Also nicht konkrete Exceptions jetzt, sondern Fehler allgemein.

Ja, wenn wir was an der Klasse ändern, dann passt das serialisierte, gespeicherte Objekt vielleicht nicht mehr dazu. z.B. wenn eine Methode hinzugekommen ist. Wenn wir was weggenommen haben, wär das egal, weil das wird an dem deserialisierten Objekt ja eh nicht aufgerufen.
Der Compiler berechnet die SVUID aus Feldern, Signaturen und solchem Zeug und prüft bei der Deserialisierung, ob die noch stimmt. Wenn man als Entwickler weiß, dass die Änderungen keine Probleme machen, vergibt man die einfach selbst.

Was musste schriftlich gelöst werden?

UML für das Decorator-Pattern, ein endlicher Automat, etwas Code zur Serialisierung

Bewertung und Begründung

Sie hatten nichts auszusetzen, Vornberger hat noch ein wenig geschwärmt, viel zu begründen gab's da nicht.

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

Beide hatten glaube ich schon bestimmte Buzzwords/Sätze, die fallen sollten, ich habe jetzt nicht versucht, sie von ihrem Kurs abzubringen. Ich würde sagen eher nein.

Zum Verhalten des Prüfers

Sehr entspannt.