Computer Science, 2010-10-11

Module: 
Computer Science
Examiner: 
Oliver Vornberger
Assessor: 
Elke Pulvermüller
Date: 
Mon, 2010-10-11

Vorbereitung

Was hast du zur Prüfungsvorbereitung benutzt?
Info A/B Skript, alte Protokolle, Google
Was wir hilfreich, was war weniger hilfreich?
Sehr, sehr hilfreich: Vorher Termin mit Pulvermüller machen. Wenn man in der Klausur gut war, darf man sich drei Themen aussuchen, über die man geprüft wird, "weil man ja schon einmal alles gelernt hat" (ich hatte Grundlagen+Vererbung/Interfaces, GUI, Netzwerkprogrammierung). Das macht das lernen erheblich entspannter :)

Prüfung

Wiederholungsprüfung? nein
Note: 1.0
Bereiche nach Zeit: Inf A: 15 min, Inf B: 10 min

Fragensammlung: wie lauteten die Fragen im einzelnen?

(Kann mich nicht mehr an alle erinnern, die Antworten sind auf das Wesentliche gekürzt)

**** A:

Was ist topologisches sortieren?
- Nummerierung der Knoten eines gerichteten Graphen mit der Vorschrift, wenn A Vorgänger von B -> f(A) < f(B)
Wie ist das implementiert?
- Durchgehen und Eingangsgrade bestimmen, alle mit Eingangsgrad 0 in Schlange, dann jeweils einen aus Schlange nehmen, Eingangsgrad reduzieren etc.
Funktioniert das immer?
- Nein.
Sie haben eine Schlange erwähnt... warum gerade eine Schlange?
- Kann auch Keller etc. sein, Hauptsache man kann die Knoten speichern und muss nicht jedes Mal aufs neue durchgehen.
Das war Traversierung, wir hatten aber auch noch andere Graphenalgorithmen mit Rundwegen...
- Zum Beispiel Hamiltonweg -> alle Knoten oder Chinese Postman -> alle Kanten
Erläutern Sie dann doch bitte mal den Chinese Postman:
- Eulergraph gesucht, da einfach lösbar mit Vereinigung von Kreisen. Wird erstellt durch bestimmen aller Knoten mit ungeradem Grad -> Minimum-Cost-Matching
Was matche ich denn da?
- Je zwei Knoten sollen über die billigste Kantenfolge verbunden werden.
Und kann es vorkommen, dass eine Kante dann dreimal benutzt wird?
- Ja, weil der kürzeste Weg von einem Knoten zu einem anderen über einen mit ungeradem Grad gehen kann.
Das ist Unsinn, warum?
- Weil ich dann zwei Kanten "wegkürzen" kann.
Sie hatten auch den Hamiltonkreis erwähnt... wie funktioniert der denn so?
- Mit Keller und Tiefensuche, bei der backgetrackt wird. Bereits besuchte Knoten werden markiert?
Was hat das für eine Laufzeit?
- O(n!), da ich im schlimmsten Fall nach jedem Knoten n Kanten zu den jeweils angrenzenden Knoten habe.
Kann man das verbessern?
- Bestimmt irgendwie, aber es bleibt ein NP-Problem, und außer der neue P=NP beweis hat recht, bleibt es damit nicht polynomiell lösbar
Und dann gebe ich auf?
- Es kann jedenfalls kein effizienter Algorithmus gefunden werden.
Und wenn ich jetzt eine LKW-Spedition bin, gebe ich einfach auf?
- Dann kann ich approximieren.
Okay, jetzt noch mal was ganz anderes: Rekursion... wir haben da vorne die Türme von Hanoi stehen, wie funktioniert denn das?
- Algorithmus erklärt. Laufzeit: O(2^n), da n immer ums eins erniedrigt und zwei Aufrufe nach jedem Aufruf.
Da haben wir ja jetzt zwei mal einen Aufruf mit je ums eins erniedrigter Funktion... wo kommt das noch in ähnlicher Weise vor?
- Naja... Mergesort hat 2 mal mit je halbierter Funktion (Kopfschütteln) ... ... Fibonacci ist rekursiv ähnlich, aber Laufzeit etwas kleiner weil f(n-1) und f(n- 2 ).
Genau, schreiben Sie doch mal die entscheidende Zeile auf:
- gemacht.
Ist Rekursion denn die einzige Möglichkeit sowas zu lösen?
- Nein, jede Rekursion lässt sich auch über einen Stack simulieren.
Und ist die Laufzeit dann immer gleich?
- ja...?
Überlegen Sie nochmal... sagen sie mal die ersten Fibonacci zahlen auf ... wie hatten wir Fibonacci früher implementiert... da gabs so eine for-Schleife...
- Genau, die hat immer die vorherigen Zahlen addiert. Das heißt bei der Zahl nten Fibonaccizahl war die Laufzeit = O(n).
Noch mehr Rekursion... erläutern Sie Quicksort anhand von diesem Beispiel: (malt ein paar Punkte auf einen Zettel)
- Pivot-Element suchen (z.B. mit Mediansuche, die ist aber umständlich) und in zwei Hälften teilen -> meistens O(n*log(n), bei schlechtem Pivot =(n²)

*** B

(Die Fragen waren viel weniger eindeutig, ich habe oft nicht verstanden, was Frau Pulvermüller von mir will -> nachfragen!):
Dann kommen wir jetzt mal zu InfoB: Was ist der Vorteil von Schnittstellen?
- zwei Programmierer können unabhängig voneinander arbeiten.
Und wenn Sie jetzt irgendeine Programmiersprache vorgeworfen bekommen, wonach würden Sie dann suchen, wenn sie eine Schnittstelle erstellen wollen?
- ??? nach Interfaces, Abstrakten Klassen, Vererbung
Irgendeine Sprache
- ich würde in eine Dokumentation gucken. (wird wohl nicht die richtige Antwort gewesen sein)
Jetzt kam irgendeine Frage, die entweder auf die Implementation von mehreren Interfaces, oder auf Mehrfachvererbung innerhalb von Interfaces herauswollte
- ich habe die Probleme bei der Mehrfachvererbung von Interfaces angesprochen (Gleiche Signatur, anderer Rückgabewert; Variablen mit unterschiedlichen Werten) und Mehrfachimplementation -> Mehrere sichten auf das gleiche Objekt erwähnt
Wenn Sie entweder Interfaces oder abstrakte Klassen implementieren können, was würden Sie lieber tun?
- ? Das hängt von der Situation ab. Wenn ich nur Methoden vorgeben will ein Interface, wenn aber alle erbenden Klassen schon meine Methode haben sollen die Abstrakte Klasse
Ja, aber [hier obrige Frage einfügen]
- [hier letzte Antwort + Beispiel Component aus GUI einfügen]
Das ging jetzt noch ein bisschen so weiter... Vornberger ist an dieser Stelle mit seinem Stuhl an den PC gerollt und hat kurz was gemacht.
Kommen wir zum nächsten Thema: GUI. Was ist ein Listener/Adapterklassen? Schreiben Sie doch mal ein Beispiel auf:
- Button erstellt, ActionListener drangebastelt und erklärt was eine Adapterklasse in diesem Fall tun würde
Was fehlt jetzt noch? (*5)
- Containerklasse -> Frame gebastelt
- LayoutManager? -> Drangebastelt
- Importe? -> ein java.awt.* hat gereicht
- setVisible -> gemacht
- nichts?
Okay, jetzt zum letzten Thema: Netzwerkprogrammierung... Was ist ein Protokoll?
- Menge an Regeln zur Datenübertragung, Beispiel des Briefs gebracht -> Protocol Stack erwähnt
Was ist peer-to-peer Kommunikation?
- Kommunikation auf einer Ebene (IP-Protkoll als Beispiel)
Was ist ein Socket, wofür ist der gut?
- Schnittstelle zum Netzwerk, ähnlich wie Datei -> get input/outputstream, java: Socket/Serversocket für TCP, DatagramsSocket für UDP, definiert durch Adresse + Port zum Ansprechen des Prozesses
Was macht ein Client/Server?
- Client: Verbindungsaufnahme, Server: horcht, erstellt neuen Socket an neuem Port (und am besten in neuem Thread), der dann wie der Client-Socket genutzt werden kann

Was musste schriftlich gelöst werden?

A: Fibonaccirekursionszeile, zwei Striche in eine Quicksortpunktefolge
B: GUI basteln

Welche Beispiele wurden wofür abgefragt?

Graphen: TopoSort, Chinese Postman, Hamiltonkreis
Rekursion: Türme von Hanoi, Fibonacci, Quicksort

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

Nachdem bei Vornberger die Kantenfrage kam, war ich relativ gestresst. Die Fragen sollten wohl die Grenzen des Verständnisses abtasten. Pulvermüller war nicht so ganz verständlich für mich... vielleicht hätte ich öfter die Vorlesung besuchen sollen.

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

Einstieg: Sie studieren also Coxi? Wann haben Sie InfoAB gemacht?
Ende: Ich soll mir das nächste Mal schon Antworten zurecht legen (Frau Pulvermüller: "Man hat gemerkt dass alles in deinem Kopf ist, nur nicht so ganz strukturiert"). Wäre auf jeden Fall eine gute Idee gewesen. Sonst Noten abgefragt und noch ein bisschen Smalltalk.
Begründung: Vornberger meinte es wäre schon zu Anfang relativ klar gewesen... zum verwirrten InfoB-Teil haben sie nichts gesagt

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

Von den Antworten nicht so sehr, aber es wurde ja oft gefragt, was ich denn so für Graphenprobleme / Rekursionsprobleme kenne, und das hat natürlich geleitet. Bei Pulvermüller hatte ich das Gefühl, dass sie immer auf eine bestimmte Sache gewartet hat und Antworten da auch nicht woanders hin leiten konnten.