Computer Science, 2017-08-09

Module: 
Computer Science
Examiner: 
Oliver Vornberger
Assessor: 
Chimani
Date: 
Wed, 2017-08-09

FORMALIA

Modulprüfung: Info A + Info D Fachsemester: 6
Prüfer/2.Prüfer: Vornberger/Chimani

VORBEREITUNG

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

Info A:
Skript und Aufzeichnungen.
Skript hätte eigentlich gereicht. Es gibt zwar kleinigkeiten die nicht im Skript stehen: z.B. definition von 'Netzwerk' (=der graph vom Maximalen Fluss) allerdings keine davon gefragt. Aufzeichnungen sind hilfreich wenn man Stellen des z.T. knappen Skripts nicht versteht.

Info D:
Slides
Eigentlich könnte man glaube ich alles bis Turingmaschinen ignorieren.

Dann hab ich mir für die sachen die man auswendig können muss Karteikarten gemacht. z.B.:
- info d definitionen
- die verschiedenen NPC probleme mit beweisen

PRÜFUNG

<> Prüfungsdatum: 09.08.17
Wiederholungsprüfung? nein
Note: 1.0 Bereiche nach Zeit: 10:10

Fragensammlung: wie lauteten die Fragen im einzelnen?

Info A:

Was ist Chinese Postman?
- Ungerichteter Graph mit gewichteten Kanten. Rundreise, jede Kante mind einmal, minimale Gesamtkosten

Wie löst man das?
- Eulergraph (alle Knoten geraden grad)
- Beliebig immer ne unbesuchte kante langlaufen, da gerader grad kommt man aus nem knoten raus in den man rein kommt
- (auf nachfrage:) evtl gibts mehrere Kreise. dann mergen

Und wenn es kein Eulergraph ist?
- zu eulergraph machen durch Verdopplung von Kanten
- aufgemalt, dass man den Grad nur gerade machen kann indem man zwei ungerade Grad knoten verbindet.
- mit floyd all pairs shortest paths die kürzesten Wege bestimmen
- Clique betrachten,
- minimum cost matching darauf

Was ist den dann floyd?
- all pairs shortest paths
- man braucht Adjazenzmatrix
- man erlaubt immer nach und nach einen Knoten k mehr und guckt ob man dadurch kürzer wird
- dieses dreieck aufgemalt
- formel für neuen eintrag ( top index k nicht vergessen): $$D^k_{ij}=min\{D^{k-1}_{ij}, D^{k-1}_{ik} + D^{k-1}_{kj}\}$$

Und wenn man da jetzt den weg wissen will?
- Matrix P mit vorgängern
- P_ij ist vorletzter Knoten aufm weg von i nach j
- (auf nachfrage:) Oben im Bild mit den drei knoten gezeigt wo das umgebogen wird

Und wie gibt man diesen weg (i->j) jetzt aus?
- rekursiv (steht im skript)
- zuerst rekursiv drucke(i -> P_ij), (drucke pfad von i nach 'das was in P_ij steht)
- dann den letzten drucken also j

Was gibts noch für graph probleme?
- aufgezählt, er wollte dann maximalen Fluss

Was ist das?
- Problem beschrieben
- Bedingungen: Pro Knoten gleich viel rein wie raus, fluss kleiner als kapazität sein

Lösungsidee?
- suche erweiternde wege
- erhöhe entlang dieser
- Gibt satz: keine erw. wege <=> fluss maximal
(Recht oberflächlich. Keine begründung davon, kein cut, kein genauer breitensuche algorithmus)

Ok dann jetzt Sprung: Wie ist das den mit Rekursion bei quicksort?
- bei Quicksort spaltet man das Array in zwei teil arrays wobei im linken alle elemente <= Pivot element sind und im rechten alle >= Pivot
- auf jedes dann wieder rekursiv quicksort

Wie ist die laufzeit davon? (Irgendwie hat er es so formuliert das klar war er wollte die Rekursionsgleichung)
- das in zwei hälften aufteilen dauert c*n (mit finger rumgefuchtelt, dass man mit zwei zeigern jedes element nur einmal anguckt, da man ja fertig ist sobald die Zeiger übereinander laufen)
- dann rekursiver aufruf mit hälften
(zwischenruf von Vorni: Nimm an hälften wären gleich)
- ok dann 2*f(n/2)

Was ist dann die Laufzeit?
-n*log(n)

Und im worst case?
- n^2 wenn hälften n-1 und 1 lang sind

Ist das gut oder schlecht?
- Durch theoretische überlegung beweisbar das n*log(n) das bestmögliche ist

Wie zeigt man das?
- ok für ein array von länge n gibt es n! verschiedene reihenfolgen
- wir müssen irgendwie so entscheidungen treffen das wir bei einer eindeutigen davon landen
- pro entscheidung unterscheiden wir zwischen 'zwei realitäten'
- so viele unterscheidungen bis n! eindeutige end realitäten möglich sind
- also binärbaum mit n! blättern
- dieser hat höhe log(n!) >= n/4 * log(n)

Info D:

P und NP?
-Definition der slides

Wieso interessiert uns das?
-Weil wir nicht wissen ob die gleich sind

(hier weiß ich den genauen Dialog nicht mehr aber so ungefähr)
Chimani: Na und? ist doch beides polynomisch?
Ich: joa, naja, aber computer sind nunmal deterministisch und wir können den Nichtdeterminismus nur durch exponentielles raten simulieren?
Chimani: Ja aber man könnte doch irgendwie nen nichtdeterministischen Computer bauen?
Ich: Äh Äh, aber für NP muss er nicht nur zufällig irgendwas machen, sondern zufällig immer genau das richtige raten und das geht nicht. (darauf wollte er glaub ich raus, das NP heißt nicht deterministisch immer richtig raten)

Dann gibts ja noch NP Vollständig?
- Definition (mit reduktion)

Was ist denn Reduktion?
- Definition davon

Ok dann gabs noch teilmenge von NP vollständig?
- Ja stark und schwach NP vollständig
- Definition
- Schwach NPC erlaubt Pseudopolynomielen algorithmus

Wasn das?
- O(n^c * a^d) a ist zahlenwert der größten vorkommenden zahl

Beispiele für stark/schach NPC?
- stark: alles ohne zahlen: Sat, Hammiltonkreis
- schwach: subsetsum

wann ham sie nochmal Info D gehört?
- dieses jahr

Was ist den FPT?
- Fixed Parameter tractable
- parameter k fest
- laufzeit O(f(k) * n^c)

(die genaue formulierungen weiß ich nicht mehr aber er wollte hierauf hinaus:)
Ist den alles mit Polynomischer Laufzeit mit einem festen Parameter k auch FPT in bezug auf k?
- äh äh
- nein, n^k ist zum beispiel nicht FPT da es sich nicht in die form f(k) * n^c trennen lässt

Beispiel für FPT problem?
- Vertex Cover

Wie zeigt man das denn?
- zwei möglichkeiten
- Kernelization und Tiefenbeschränkter suchbaum

Such dir eins aus!
- Suchbaum ist leichter
- Chimani: Stimmt, gute wahl

-Ok bei vertex Cover muss für jede Kante immer mind einer der beiden Knoten in W
- wir wählen immer einen der beiden für höchstens k kanten

Zwischenfrage: Was ist den k?
- achso: |W| <= k
- also höchstens k knoten im vertex cover erlaubt

Ok weiter?
- also suchbaum
- wir nehmen beliebige kante
- starte suchbaum neue mit einmal dem einen Knoten in W und einmal den anderen Knoten in W

(hier war meine erklärung bischen verschwurbelt deswegen mussten sie nachfragen)

- also man löscht in jedem suchbaum-knoten erstmal alle graph-knoten die man sich bis hierhin in W gewählt hat
- und nimmt dann daraus ne Kannte
- und macht dann zwei suchbaum-kinder je mit einmal dem einen Endknoten der Kante in W gewählt einmal dem anderen
- das heißt graph unterhalb von diesem Suchbaum-Knoten enthält dann alle bis dahin in W gewählten Knoten nicht mehr

Berechenbarkeit und Endscheidbarkeit?
- Berechenbarkeit: Definition
- Entscheidbarkeit: Definition mit charakterischen Funktion

Was gibts da noch?
- (co-)semi-entscheidbar, positive/negative hälfte

was ist den Untentscheidbar?
- Halteprolbem

Mehr?
- Wortproblem, PCP, Wang-Parket, Kolgomorov komplexität

Wirklich, Kolgomorov komplexität unentscheidbar?
- achso, ne dass ist nicht berechenbar

Aja zurück zum Halteproblem, wie kann man den einsehen das es semi-entscheidbar ist?
- Turingmaschiene M auf w laufen lassen
- wenns anhält return 1
- wenn nicht ists halt undef
- also semi-entscheidungs-algorithmus

Okay und wie sieht man jetzt ein das es nicht entscheidbar ist?
- war erst kurz verwirrt
- halteproblem und spezielles halteproblem nochmal definiert
- dann normalen Beweis

Was mußte schriftlich gelöst werden?
- Rekursionsgleichung von Quicksort
- ich hab generell relativ viel aufgemalt/geschrieben kann mir gut vorstellen, dass sie sonst halt explizit danach gefragt hätten.

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

-Ich habe relativ oft Wörter verdreht:
z.B. schwer/leicht NP-Vollständig anstatt stark/schwach
oder Nicht-Polynomisch anstatt Nicht-Deterministisch.
Dann hat mich Chimani einfach so lange komisch angeschaut bis ich mich korrigiert hab.

- generell ist es ratsam langsam zu reden. Hab ich nicht gemacht und hab mich gelegentlich verhaspelt. Auch waren meine erklärungen nicht immer großartig strukturiert.

- Details/Code wurde gar nicht gefragt

Bewertung und Begründung:

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

Hab ich nicht explizit versucht. Aber viel geht da glaub ich nicht.

Zum Verhalten des Prüfers:

Beides Goldstückchen.