Computer Science, 2016-03-02

Module: 
Computer Science
Examiner: 
Prof. Dr. Oliver Vornberger
Assessor: 
Prof. Dr. Markus Chimani
Date: 
Wed, 2016-03-02

Formalia

Modulprüfung: Info A, Info D
Fachsemester: 7
Wiederholungsprüfung? nein
Note: 1.3 / 1.0 (Dieses Protokoll umfasst zwei Prüfungen, wir haben es zu einem Protokoll zusammengefasst, weil wir beide genau die gleichen Fragen bekommen haben)
Bereiche nach Zeit: jeweils 10min

Vorbereitung

Info A: Skript, Vorlesungsvideos
Info D: Skript
und dann gegenseitig abfragen

Wie lauteten die Fragen im einzelnen?

Info A

Was können Sie mir zu ungerichteten Graphen erzählen?

Knoten, verbunden durch Kanten, Kanten gewichtet oder ungewichtet

Wie implementiert man das?

Adjazenzmatrix und Adjazenzlisten erklärt

Und wann benutzt man welche Implementation?

Matrix wenn dicht besetzt (=viele Kanten), direkter Zugriff auf Kosten
Listen wenn dünn besetzt => schneller Zugriff auf Nachbarn eines Knoten, bei der Matrix müsste man die ganze Zeile durchgehen

Was für Probleme kennen Sie denn auf ungerichteten Graphen?

Minimal Spanning Tree, Chinese Postman, Matching

Dann erzählen Sie mir mal was zum Minimal Spanning Tree

Hier unterscheiden sich die beiden Prüfungen jetzt in der Erklärreihenfolge und den Zwischenfragen
- Problemdefinition gegeben
- Implementation, indem man die Kanten in einen Heap steckt (-> Minimum aus Heap entfernen erklärt)
- Überprüfung ob ein Kreis entsteht, indem jeder Knoten einen Chef bekommt etc.pp.
- Path-Halving um Zeit zu sparen
- Laufzeit bei m Kanten (wenn man das mit der inversen Ackerman mal außen vor lässt): m*log(m) + Begründung -- Hier hat er nochmal nachgefragt, wie die Laufzeit in Abhängigkeit von den Knoten ist. Da wollte er hören, dass es bei n Knoten ja n^2 Kanten geben kann, aber log(n^2) = log(n)+log(n) = immer noch O(log(n)), also asymptotische Laufzeit dann n^2*log(n) bzw. m*log(n) bzw. m*log(m) -> alles das gleiche

Und was wissen Sie über den Chinese Postman?

Wieder kleine Unterschiede zwischen beiden Prüfungen, aber in beiden Fällen lief es darauf hinaus halt alles zu erklären^^
- Problemdefinition
- Wenn Eulergraph: Eulertour -> Alle Kanten einmal
- Sonst: Knoten mit ungeradem Grad betrachten -> Kürzeste Wege mit Floyd, dann als Clique aufschreiben und Matching
-> Alle Kanten einmal, die Kanten auf den kürzesten Wegen jeweils zwischen den gematchten "ungeraden Knoten" doppelt

Info D

Was sind P und NP?

Komplexitätsklassen für Entscheidungsprobleme, Definition über Turingmaschinen gegeben

Und wieso unterscheiden wir das?

- Evtl. ist es zwar das gleiche, aber für viele Probleme aus NP weiß man nicht, ob/wie man sie deterministisch polynomiell lösen könnte
- Computer sind quasi deterministische Turingmaschinen
-> Probleme aus P polynomiell lösbar, das geht in der Praxis gut, Probleme außerhalb von P exponentiell, das ist für große Datenmengen nicht gut...

Was hatten wir denn noch innerhalb von NP?

NP-vollständig, das sind quasi die schwersten Probleme aus NP, Definition gegeben

Was ist denn eine Reduktion?

Reduktion von Problem A auf Problem B:
Allgemeine Instanz von A, finde eine Instanz von B, so dass die äquivalent sind (also wenn eines "ja sagt", das andere auch und umgekehrt)
=> B ist also mindestens so schwer wie A

Dann hatten wir noch Co-NP, was ist das?

- Definition über Komplement von NP gegeben, das hat ihm nicht gereicht
- Definition über Validieren eines nein-Zeugen
Ein bisschen was erzählt darüber was ein Zeuge ist, und wie das bei NP und Co-NP funktioniert, mit einem Beispiel (SAT: ja-Zeuge = Variablenbelegung für die es erfüllt ist, nein-Zeuge = alle Variablenbelegungen und dass es für keine davon erfüllt ist => daran sieht man schön, dass SAT in NP liegt und nicht in Co-NP weil der nein-Zeuge nicht polynomiell groß ist)
Das hat dann alles in allem als Erklärung so gereicht.

Gibt es auch etwas, das in Co-NP und in NP liegt?

Wollte er einfach nur darauf hinaus, dass das für alles in P der Fall ist.

Was sind Berechenbarkeit und Entscheidbarkeit?

Definitionen gegeben

Wir hatten da bei der Entscheidbarkeit noch eine schwächere Version. Wie war das?

Semientscheidbarkeit, Definition gegeben

Kennen Sie so etwas schweres? (Also unberechenbare Funktionen und unentscheidbare Probleme?)

Die Beispiele aus der Vorlesung genannt

Nehmen wir mal die Kolmogorov-Komplexität. Was ist das?

Erklärt was es ist, und warum sie nicht berechenbar ist.

Und wofür wäre es gut, wenn man die berechnen könnte? Also, das geht zwar nicht, aber wenn man zumindest eine Annäherung hätte?

ich: *denk**denk* keine Ahnung?
Chimani: zur Kompression
ich: ah ja, macht Sinn, denn die Kolmogorov-Komplexität sagt uns dann ja wie klein man etwas höchstens komprimieren kann, damit es noch rekonstruierbar ist

Was musste schriftlich gelöst werden?

Kim sollte aufzeichnen, wie man den Chef findet, und welcher dann der neue Chef ist.
Christina sollte beim Chinese Postman aufzeichnen, was dann die Clique ist.
Sonst war nach nichts konkret gefragt, aber man kann zum erklären natürlich gerne auch Stift und Zettel nutzen.

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

bei Kim:
Ging direkt los
Am Ende Chimani:"Wie viel Zeit ist noch?" Vornberger: "Noch ein bisschen, aber wir können auch aufhören, sie weiß ja alles."
Kurze Besprechung, Bewertung 1.3, Info D super, Info A teilweise etwas holpriger in den Erklärungen

bei Christina:
Einstieg: "Sie haben zusammen gelernt? Ok, dann stellen wir Ihnen die gleichen Fragen, dann haben wir einen Vergleich."
Bewertung 1.0, "Man merkt, dass Sie alles können und nicht nur auswendig widergeben"

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

Überhaupt nicht. Sie wussten beide genau, welche Antworten sie hören wollten, und die nächsten Fragen haben auch nicht darauf basiert, was man gesagt hat.

Zum Verhalten der Prüfer:

Beide super nett, haben sich auch mit uns gefreut, und sich hinterher noch erkundigt, was wir sonst so machen (Auslandssemester, Master), und ob ich nicht eine Bachelorarbeit in Theoretischer Informatik schreiben will :D