Computer Science, 2014-12-11

Module: 
Computer Science
Examiner: 
Prof. Vornberger
Assessor: 
Jana Lehnfeld
Date: 
Thu, 2014-12-11

Vorbereitung


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

Info A: Vorlesungsaufzeichnungen und Skript
Info B: Vorlesungsslides und Galileo Computing

Prüfung

Prüfungsatum: 11.12.2014
Wiederholungsprüfung: nein
Note: 1.0
Anmerkung: Prof. Pulvermüller war leider zu meinem Prüfungstermin verhindert, sodass Prof. Vornberger die Prüfung vollständig, also in Info A und Info B, übernommen hat.

Fragensammlung

Fangen wie mal bei Graphen an, was ist denn ein Graph?
Ein Graph besteht aus einer Menge von Knoten und Kanten, welche die Knoten verbinden. Die Kanten können gerichtet oder ungerichtet und gewichtet oder ungewichtet sein.

Wie kann man Graphen denn implementieren?
Es gibt zwei Möglichkeiten Graphen zu implementieren. Man kann entweder eine Adjazenzmatrix benutzen, die einem einen wahlfreien Zugriff auf die Kanten erlaubt, die aber auch O(|V|^2) Speicherplatz verbraucht und mit der keine effiziente Abarbeitung der Nachbarn möglich ist. Oder man kann eine Adjazenzliste benutzen, die eine effiziente Verarbeitung der Nachbarn erlaubt nur O(|E|) Platz verbraucht, aber keinen wahlfreien Zugriff zulässt. Adjazenzmatrizen eignen sich also vor allem auch bei dicht besetzten Graphen, Adjazenzlisten eher bei dünnbesetzten Graphen.

Sie sagten jetzt gerade man kann einen Graphen mit einer Adjazenzliste implementieren...?
Achso, eigentlich braucht natürlich jeder Knoten eine Liste für seine Kanten. Die Einträge in der Liste enthalten dann einen Verweis auf den Zielknoten, die Kosten der Kanten und einen Verweis auf den nächsten Listeneintrag.

Und was kann man mit einem Graphen machen?
Ja, einen Graphen kann man zum Beispiel traversieren. Oder man benutzt einen der Graphenalgorithmen aus ihrer Veranstaltung.

Was für Graphenalgorithmen kennen sie denn so?
Da wäre zum Beispeil der Algorithmus von Kruskal, der einen minimalen Spannbaum berechnet. Ein minimaler Spannbaum ist sozusagen ein Netz, in dem jeder Knoten erreichbar ist. Also es sind nicht alle Knoten direkt mit allen anderen verbunden aber es gibt einen Weg um von einem beliebigen Knoten zu einem beliebigen anderen Knoten des Netzwerkes zu kommen. Eine Situation dafür wäre beispielsweise eine Inselgruppe, die man möglichst Kostengünstig mit Brücken verbinden will.

Kann denn in einem minimalen Spannbaum jede beliebige Kante enthalten sein?
Nein, nur die günstigsten Kanten, die benötigt werden, um alle Knoten zu verknüpfen.

(Verschiedene Zwischenfragen zum Algorithmus, in dem Zug durfte ich auch gleich noch einen Heap erläutern.)

Wie kann man effizient feststellen ob zwei Knoten schon verbunden sind?
Ein Knoten hat eine Variable chef, in der eingetragen wird, wer der momentane Chef dieses Knotens ist. Ein Knoten der Chef von sich selbst ist, repräsentiert dann jeweils einen Teilgraphen.

Was muss also passieren, wenn zwei Teilgraphen mit einer neuen Kante verknüpft werden?
Der Chef des einen Teilbaums muss den Chef des anderen Teilbaums bei sich als Chef eintragen.

Was müsste man also tun um den Chef eines Knotens zu finden?
Man muss die Verweiskette der Chefs solange abgehen, bis ein Knoten sich selbst als Chef hat.

Kann das nicht ineffizient sein?
Doch, deshalb benutzt man die Path halving Technik. (Kurz erklärt.)

Den Algorithmus inklusive Chefs durfte ich dann auch noch aufmalen.

Und welche Graphenalgorithmen gibt es noch so?

Es gibt zum Beispiel noch den Algorithmus von Floyd, von Dijkstra, den von Ford-Fulkerson. Oder man kann einen Graphen noch topologisch sortieren oder versuchen das Chinese Postman Problem zu lösen.

Dann erzählen sie doch mal etwas zum Chinese Postman Problem.
Das Chinese Postman Problem besteht darin eine möglichst günstige Kantenrundreise in einem Graphen zu finden, die am Ende wieder beim Ausgangsknoten herauskommt. Die Lösüng hängt mit dem Eulergraphen zusammen. (Alles kurz erklärt.)

Was muss man machen, wenn es auch Knoten mit ungeradem Eingangsgrad gibt?
Man muss für die Knoten mit ungeradem Grad mit dem Algorithmus von Floyd die kürzesten Wege finden und davon ein minimum Cost-Matching bestimmen. Die Kanten aus dem Matching werden dann im Graphen verdoppelt und es entsteht wieder ein Eulergraph.

Kann eine Kante denn auch drei mal in einer Rundreise enthalten sein?
Nein, denn dann könnte man sich die Kante zweimal sparen und hätte eine günstigere Rundreise gefunden.

Gut, dann jetzt noch einmal ein anderes Thema: Was können sie mir denn zu QuickSort sagen?
QuickSort ist ein Sortieralgorithmus der auf Vergleichen basiert. Er hat im best und average case die Laufzeit O(n*log(n)) und im worst case, bei unglücklicher Wahl des Pivot Elements, die Laufzeit O(n^2). Der Algorithmus funktioniert nach dem Prinzip divide & conquer und geht so vor, dass er zunächst das Element in der Mitte einer übergebenen Zahlenfolge auswählt, die Zahlen dann in eine elementweise größere und eine elementweise kleinere Partition aufteilt und die Partitionen dann nach dem gleichen Prinzip sortiert bis der Rekursionsanker greift, weil die Partitionen nur noch einelementig und damit sortiert sind.

Sie sagten ja, dass die für die Worst case Laufzeit immer ein schlechtes Pivot Element gewählt werden muss. Was wäre das denn für eine Pivotelement?
Ein schlechtes Pivotelement wäre das größte oder das kleinste Element aus der Zahlenfolge.

Kann man da denn nicht eine Möglichkeit finden immer ein gutes Pivotelement zu finden?
Man könnte zum Beispiel immer den Median als Pivotelement wählen. Den Median kann man sogar in O(n) bestimmen.

Und wie wirkt sich das asymptotisch auf die Laufzeit aus? (What?? Hat er das gerade wirklich gefragt? Wie sich die Suche nach dem Median auf QuickSort auswirkt insbesondere in der O-Notation und die Rekusionsgleichung hatte ich beim Lernen weggelassen. Damit hatte ich auf jeden Fall nicht gerechnet.)
Mit seiner Hilfe habe ich dann die Rekursionsgleichung für QuickSort hingeschrieben, wobei ich mich eigentlich nur daran erinnern konnte, dass es bei n=1 nur ein (konstanter) Schritt ist und das bei n>1 f(n/2) in der Gleichung vorkommt. Naja, aber er hat mir da ziemlich geholfen und am Ende haben wir bestimmt, dass die Asymptotische Laufzeit, wenn man bei jedem Rekursionsaufruf auch noch den Median bestimmt, trotzdem O(n*log(n)) ist, sich also nicht verändert. In der Praxis verlangsamt sich der Algorithmus dadurch aber natürlich und das ganze ist ein ziemlicher overkill, da die Fälle, in denen QuickSort im worst case landet eher selten auftreten.

(Dann kam ohne Anmerkung der Übergang zu Info B.) Was ist denn ein Konstruktor?
Ein Konstruktor kommt aus der Objektorientierten Programmierung und dient dazu einem Objekt einer Klasse bei seiner Erzeugung die initialen Werte bzw. sinnvolle Werte zu geben.

Was ist denn normalerweise das erste Statement in einem Konstruktor?
Das erste Statement ist normalerweise super(...), also der Aufruf eines Konstruktors der Oberklasse. super() kann nur an erster Stelle im Konstruktor stehen.

Was passiert, wenn man das nicht explizit hinschreibt?
Dann wird implizit super() aufgerufen, also der Default-Konstruktor der Oberklasse.

Was ist denn ein Default-Konstruktor?
Ein Default-Konstruktor ist ein parameterloser Konstruktor.

Gibt es den immer?
Den gibt es immer, wenn man nicht selber einen Custom-Konstruktor definiert.

Wie wird der Konstruktor denn ausgewählt?
Der Konstruktor wird zur Laufzeit anhand des Arguments durch dynamisches Binden ausgewählt.

Was ist denn dynamisches Binden?
Dynamisches Binden bedeutet, dass erst zur Laufzeit die an einem Objekt aufgerufene Methode tatsächlich ermittelt wird. Zur Kompilierzeit wird nur ermittelt, ob es eine solche Methode überhaupt gibt.

Werden Variablen auch dynamisch gebunden?
Nein, Variablen werden statisch, also schon zur Kompilierzeit, gebunden.

Dann mal weiter mit Exceptions? Was ist denn eine Exception bzw. was kann man damit machen?
Eine Exception beschreibt eine Ausnahmesituation in einem Programm. Wenn sie geworfen wird, ist irgendwo ein Fehler aufgetreten.

Wie kann man denn in Java eine Exception bauen?
Am einfachsten ist es, wenn man von der Klasse Exception erbt und dann die zwei vorgeschriebenen Konstruktoren, einmal parameterlos und einmal mit Stringargument, überschreibt.

Jetzt mal angenommen ich hätte so eine DatumsException, die immer in einer Methode geworfen werden soll, die eine Zahl für den Monat übergeben bekommt. Wie würde ich das machen?
Die Methode würde wahrscheinlich eine Zahl übergeben bekommen und man müsste dann prüfen ob die Zahl kleiner null oder größer 12 ist und dann eine Exception werfen.

Schreiben sie die Methode mal in Java auf.
Hab ich hingeschrieben, dabei hab ich gemerkt worauf er hinauswollte: Die DatumException ist wahrscheinlich checkt, dass heißt sie muss entweder in der Methode selbst gefangen werden (macht aber keinen Sinn) oder die Methode muss eine throws Klausel haben.

Was passiert denn jetzt, wenn diese Methode aufgerufen wird?
Dann merkt der Compiler, dass die Methode eventuell eine checkt-Exception werfen könnte und man muss diese dann auffangen.

Schreiben Sie mal so einen try-catch Block auf
Jap.

Dann noch mal zu Nebenläufigkeit: Wie kann man denn in Java Nebenläufigkeit erreichen?
Entweder man erbt von Thread oder man implementiert das Interface Runnable und die Methode run() und übergibt das dann an einen Thread.

Und in welchen Fällen würde man jetzt von Thread erben bzw. warum macht man das nicht immer? Warum schreibt man extra so eine Runnable Klasse?
Verantwortlichkeitesprinzip, bessere Modularisierung.

Gut, dann wars das auch schon.

Persönlicher Kommentar:

Da Frau Pulvermüller nicht da war, hat mir Prof. Vornberger (leicht verlegen) angeboten, dass entweder er mich in beiden Teilen prüft oder dass ich in ca. anderthalb Stunden noch einmal wieder kommen könnte. Ich hatte aber keine Lust weiter zu warten und habs dann direkt gemacht. Im Nachhinein war das sogar ziemlich gut, weil die Fragen zu Info B ziemlich einfach waren und der Teil zu Info B auch ziemlich schnell abgehandelt wurde. Prof. Vornberger war während der Prüfung ziemlich nett und hilfsbereit, hat manchmal bei meinen Antworten geschmunzelt oder kurz aufgelacht, aber alles super entspannt und freundlich. Nach der Prüfung wurde ich dann kurz rausgeschickt, aber auch nach einer Minute oder so wieder reingeholt. Das Ergebnis wurde mit dann direkt gesagt und Prof. Vornberger hat noch ein bisschen Smalltalk gemacht von wegen wie ich mich vorbereitet hätte und ob ich Informatik schon in der Schule hatte.