Computer Science, 2015-12-15

Module: 
Computer Science
Examiner: 
Prof. Dr. Oliver Vornberger
Assessor: 
Prof. Dr. Markus Chimani
Date: 
Tue, 2015-12-15

FORMALIA

Modulprüfung: 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: Vorlesungsaufzeichnungen, Skript
Info D: Alte Zusammenfassungen, Skript, Google
Nicht nur alleine Skript durchgehen und alles verstehen, man muss das auch rüber bringen können -> Mit Leuten lernen und sichabfragen kann da helfen.

PRÜFUNG

Prüfungsdatum: 15.12.15
Wiederholungsprüfung? nein Beisitzer: Chimani
Note: 1.0 Bereiche nach Zeit: 10/10

Fragensammlung: wie lauteten die Fragen im einzelnen?

INFO A
Was ist Rekursion?
Eine Methode kann in der Deklaration ihres Rumpfes den eigenen Namen verwenden. Es kommt zu einem rekursiven Aufruf. Typischerweise schrumpfen dabei die übergebenen Parameter und die Probleminstanz wird kleiner. Das geschieht so lange, bis ein einfacher Fall, der Rekursionsanker, erreicht wird.
Was für Beispiele hatten wir da?
Fakultät, Fibonacci, Türme von Hanoi.
Türme von Hanoi, wie hat man das da genutzt?
Man hat n Scheiben absteigender Größe auf Platz A. Sollen über B nach C gebracht werden, wobei nur eine Scheibe zur Zeit bewegt werden darf und nie eine größere auf einer kleineren liegen darf.
Wir haben uns überlegt, dass wir fast fertig sind, wenn wir n-1 Scheiben über C nach B gebracht haben, dann können wir die n-te Scheibe nach C legen und die übrigen n-1 dann mittels verlege von B über A nach C.
Laufzeit von Rekursion und Hanoi?
Laufzeit bei Rekursionen werden mittels einer Rekursionsgleichung ermittelt. Bei Hanoi: Haben wir nur eine Scheibe -> Konstante Laufzeit. Ansonsten f(n)= 2f(n-1)+1 (2 mal n-1 verlegen, 1 mal n verlegen) Laufzeit ist 0(2^n), also exponentiell.
Themenwechsel: Quicksort, was ist das, wie wird Rekursion genutzt?
Bsp für Algorithmus nach Divide & Conquer. Partioniere Folge in elementweise kleinere und elementweise größere, mit Hilfe eines Pivots. Teilhälften werden dann rekursiv sortiert.
Was ist die Laufzeit und wovon hängt sie ab?
Laufzeit hängt von der Wahl des Pivots ab. Im worst case ist es das größte oder kleinste Element, dann partioniert man die Folge in eine Teilfolge der Länge 1 und eine der Länge n-1. Greift man dann wieder in die Mitte und hat wieder das kleinste, hat man eine Laufzeit von O(n^2). Im best Case hat man den Median. Dann ist die Laufzeit O(n*log n). Wir können auch garantieren diesen immer zu finden.
Wie machen wir das genau und was ist davon die Laufzeit?
Wir teilen die Zahlen in 5er Gruppen, berechnen von diesen den Median und dann den Median der Mediane. Dadurch können wir garantieren, dass mindestens ein Viertel der Zahlen <= und ein Viertel >= der Median sind. Wir teilen die Zahlen also in 3 Gruppen (A: median) und suchen dan geziehlt in einer dieser Gruppen nach dem n. kleinsten Element. Die Laufzeit dafür ist linear, wir können versichern, dass es in 20*c*n geht. Also O(n).
Wo wird der Median genau genutzt?
Könnten das jedes mal beim Pivot suchen machen, wird in der Praxis aber nicht gemacht, weil der Worst Case so selten ist, dass der sichere Mehraufwand sich nicht lohnt.
Kommen wir zu Problemen auf ungerichteten Graphen, Minimaler Spannbaum, was ist denn das?
Gegeben ein ungerichteter, gewichteter Graph. Gesucht ist eine Teilmenge der Kanten, die alle Knoten möglichst günstig miteinander verbindet. Wir initialisieren einen Wald von n Knoten und einen Heap mit den Kantenkosten. Solange wir keinen MST haben nehmen wir die günstigste Kante aus dem Heap und schauen, ob wir damit 2 bisher unanhängige Teilbäume verbinden. Ist das der Fall, fügen wir sie dem MST hinzu, ansonsten wird sie verworfen und wir nehmen die nächste.
Wir schauen wir, ob wir eine Kante zwei unabhängige Kreise verbindet oder ob wir einen Kreis enthalten?
Wir merken uns für jeden Knoten, wer sein Chef ist. Anfangs ist jeder Knoten sein eigener Chef, fügen wir zwei Teilbäume zusammen, biegen wir jeweils einen teilbaum auf den anderen um. Weil wir dabei sehr lange Ketten kriegen können nutzen wir die Technik des Path Halving, das heißt wir biegen beim prüfen der Ketten die Verweise um (halbieren sie) Dadurch können wir fast konstante Laufzeit dafür garantieren.
Und was ist ein Heap?
Ein heap ist ein binärer Baum, der bis auf die letzte Ebene vollständig ist, diese ist von links bis zum sogenanntent "letzten Knoten" vollständig. Außerdem erfüllt jeder Knoten die Heap bedingung (Schlüssel eines Vaters ist kleiner als der Schlüssel seiner Söhne)
Und wie haben wir das implementiert?
Mit einem Array. Das geht, weil wir aus dem Index eines Knotens den Index seiner Söhne und damit deren Stellen im Array berechnen können. linker sohn:2i+1, rechter:2i+2

Info D
Was hat es denn mit P und NP auf sich?
Die Komplexitätsklasse P umfasst alle Entscheidungsprobleme, die sich von einer deterministischen TM in polynimieller Zeit lösen lassen. NP von einer Nicht-det. TM in polynomieller Zeit.
Und warum macht man diese Unterscheidung?
In der Praxis sind Probleme in P gut mit dem Computer zu lösen, wohingegen für alle Probleme in NP, wenn wir sie deterministisch lösen wollen, eine exponentielle Laufzeit haben. (Tatsächlich müssen sie das vllt nicht, wir kennen aber nur exp. Alg.) habe noch SAT alsBSP gebracht und über NP vollständigkeit geredet.
Und warum kann man da eine MIlion kriegen?
(jetzt verstehe ich erst, worauf er hinaus will) Es ist nicht sicher ob P=NP sein kann. Es kann sein, dass es für alle Probleme in NP auch det. polyn. Algorithmen gibt, wir sie nur nicht gefunden haben.
Sie sagten NPvollständig?
Ein Problem ist NPV, wenn es in NP liegt und wenn manjedes andere Problem in NP det. und in polynomieller Zeit auf es reduzieren kann. Es sind also die schwersten Probleme in NP.
Und was heißt Reduktion?
Eine Reduktion ist eine Methode aus der theoretischen Informatik, bei der man die Komplexität von zwei Problemen miteinander in Relation setzt. Reduzieren wir ein Problem A auf B, heißt dass, dass wenn wir einen Alg. haben,der B löst, er mit nur polynomiell Mehraufwand auch A lösen kann. B ist also mindestens so schwer wie A. (ein einfaches BSP ohne Gewähr mit demich mir dasgemerkt habe ist die Reduktion von multiplikation auf Addition. Jede Mult. ist nur eine n fache addition. Kann ein Algorithmus addieren, kann er mit nur polyn. (nfachem) Aufwand auch multiplizieren. Multiplikation ist also hächstens so schwer wir Addition.
Co-NP?
Probleme liegen in CoNP, wenn ihr Komplement in NP liegt bzw wenn das Problem, einen gegebenen Zeugen für eine Nein-Instanz auf Echtheit zu prüfen, in P liegt.
Stark NPV?
Vorüberlegung: Wir betrachten Komplexität stets relativ zur Länge der Eingabe. Eine Binärzahl der Länge n kann maximal den Wert 2^n haben, hat also exponentiellen Wert (ich glaube die Begrenztheit des Wertes ist hier das Zauberwort). Ein Problem ist Stark NPV, wenn das selbe Problem, eingeschränkt auf Instanzen, bei denen der Wert von n durch ein polynom von n beschränkt ist (also nicht exponentiell), NPV ist. Als Bsp für eine polynomielle beschränkung: wenn nur unär codierte Zahlen akzeptiert werden. Dann ist der Wert einer Zahöl der Länge n beschränkt durch den Wert n. und n ist ein Polynom von n.
Berechenbarkeit und entscheidbarkeit?
Berechenbarkeit ist eine Eigenschaft einer Funktion. Def gegeben (wenn eine endliche algorithmische beschreibung existiert...) unterschied total und partiell berechenbarkeit liegt in der einschränkung des definitionsbereichs. Eine Sprache ist entscheidbar, wenn ihre Charakteristische Funktion berechenbar ist. Def gegeben (1 wenn wort element sprache,null sonst) Semientscheidbar, wenn positive hälfte der char. funktion berechenbar.
Bsp unentscheidbares Problem
Halteproblem
Weiter?
Wang-Kachelung (wollte darauf hinaus)
Was ist denn die Wang Kachelung?
gegebeneine Endliche Menge möglicher nicht-rotierbarer Kacheltypen. Frage: ist damit die unendliche Ebene zu parkettieren, sodass sich berührende Kanten die gleiche Farbe haben?
Undwarum ist das nicht entscheidbar? (Hatbetont,er wolle keinen Beweis, nur die Idee)
Ist nicht entscheidbar, weil es Instanzen gibt, bei denen es nur aperiodische Lösungen gibt. (in anderen Prüfungen woltle er zT wissen, was aperiodisch heißt,also am besten googlen)
Dann wollte er nochwissen, wie eine solche Kachel aussieht, skizziert,fertig.

Was mußte schriftlich gelöst werden?
nichts

Welche Beispiele wurden wofür abgefragt?
Aussehen der Kacheltypen bei der Wang-Kachelung

Persönlicher Kommmentar, Was war toll? Was war doof? Was war auffällig?
Prüfer waren sehr entspannt und haben versucht zu helfen. War gut, dass es gleich losging.

Wie waren Einstieg, Ablauf, Ende, Bewertung und Begründung?
Ging gleich los und war sehr schnell zuende. Wenn ma gesagt hatte, was sie hören wollen, ging es schnell zum nächsten Thema. Es ging nie wirklich ins Detail oder auch nur in die Nähe einer Implementation.

Bewertung und Begründung:
Ich glaube, Modulprüfungnen werden, wenn sie sehen, dass man weiß, wovon man spricht und nicht zu verstehen gibt, dass man das Fach hasst, sehr wohlwollend beurteilt

Lässt sich der Prüfer von den Antworten leiten?
Eher nein, beide hatten schon eine konkrete Vorstellung von dem, was sie hören wollten.

Zum Verhalten des Prüfers:
Beide sehr entspannt, routiniert und nett.