Computer Science, 2016-08-31

Module: 
Computer Science
Examiner: 
Oliver Vornberger
Assessor: 
Markus Chimani
Date: 
Wed, 2016-08-31

Formalia

Modulprüfung: Info A, Info D
Fachsemester: 7
Wiederholungsprüfung? nein
Note: 1.3
Bereich nach Zeit: jeweils ca. 10-15 Minuten
Vorbereitung: Info A: Skript, Vorlesungsaufzeichnungen
Info D: Skript

Wie lauteten die Fragen?

Info A

Wie wird Rekursion bei den Fibonacci-Zahlen genutzt?

Hier habe ich den rekursiven Algorithmus zur Berechnung der Fibonaccizahlen aufgeschrieben und erklärt.

Und was bedeutet dies für die Laufzeit des Algorithmus?

Da im Rumpf die Methode 2 mal erneut aufgerufen wird hat man 2*f(n-1). Dies ergibt eine Laufzeit von 2^n, welche sehr ungünstig ist, da sie extrem schnell ansteigt.

Und wie würde man das in einem Algorithmus ohne Rekursion aufschreiben?

Ich stand zunächst auf dem Schlauch. In einer for-Schleife könnte man in jedem Schritt n=(n-1)+(n-2) berechnen.

Kommen wir mal zu Suchbäumen. Wozu benutzt man diese?

Um Elemente sortiert abzuspeichern, zu suchen und abzurufen. Methoden: insert, delete, lookup. Elemente im linken Teilbaum sind kleiner als jenes im Knoten, im rechten Teilbaum größer als jenes im Knoten. Die Laufzeit für Operationen ist im best und average case log n, im worst case (sortierte Eingabe) n. Ich hab einfach alles erzählt, was ich zu Suchbäumen wusste, um ein wenig Zeit zu schinden.

Wie löscht man denn ein Element aus dem Suchbaum?

Ich hatte keine Ahnung. Scheinbar steht der Algorithmus im Skript, angeschaut hatte ich mir diesen aber nicht.

Info D

Sie kennen P und NP. Was sind diese denn und wozu sind sie gut?

Komplexitätsklassen für Entscheidungsprobleme. Ich habe einfach die Definitionen gegeben.

Und warum macht man diese Entscheidung in P und NP? Ist das nicht das gleiche?

Es ist noch unklar, ob P=NP oder nicht. Es wird aber vermutet, dass dies nicht der Fall ist, da für viele Probleme in NP noch kein det. polynomieller Algorithmus gefunden wurde.

Und was ist daran so schlimm? Dann nutzt man eben einen nichtdeterministischen Algorithmus, oder?

Keine Ahnung worauf er hinauswollte. Ich habe ein wenig von potentiell exponentiellen Laufzeiten geredet und dass nichtdeterministische Algorithmen in der Praxis schlecht anwendbar wären.

Ja, und was ist den NP-Vollständigkeit?

Entscheidungsproblem liegt in NP und jedes andere Problem in NP lässt sich auf dieses Problem reduzieren.

Reduzieren? Was ist damit gemeint?

Man kann ein Problem Y als Instanz des Problems X darstellen, sodass dieses ja liefert, wenn Y ja liefern würde und umgekehrt.

Ja, und was gilt dabei außerdem?

Die Reduktion muss deterministisch und in polynomieller Zeit machbar sein.

Innherhalb der NP-Vollständigkeit haben wir noch einmal Unterscheidungen gemachtet. Welche?

Starke und schwache NP-Vollständigkeit.
Gegeben X und Xp, was das gleiche Problem ist bei dem Zahlenwerte allerdings durch ein Polynom von n beschränkt sind. Ist Xp Np-vollständig ist X stark NP vollständig, sonst nicht.

Was bedeutet dies: auf ein Polynom von n beschränkt? Was ist denn n?

Ich grüble und grüble ohne eine Antwort zu finden. Die Zahlenwerte? Die Eingabe? Die beiden bohren weiter. Nach gefühlt 5 Minuten komme ich auf die Antwort: der Speicherplatz natürlich!

Ok, kommen wir zu Berechenbarkeit und Entscheidbarkeit. Was ist der Unterschied?

Berechenbarkeit ist für Funktionen definiert. Ich gab hier die Definition für totale und partielle Funktionen. Entscheidbarkeit ist für Probleme definiert. Wir können Entscheidungsprobleme als Wortprobleme über Sprachen definieren. Dann ist eine Sprache entscheidbar, wenn berechenbar ist, ob ein Wort in der Sprache ist oder nicht. (charakteristische Funtktion)

Kennen Sie auch noch anderere Bezeichnungen in diesem Gebiet?

Ja, die positive und negative Hälfte. Bei der pos. Hälfte ist nur berechenbar, ob ein Wort in der Sprache enthalten ist, sonst ist der Wert 0 oder undef. Bei der neg. Hälfte umgekehrt.

Was bedeutet dies: es ist undefiniert?

Der Algorithmus hält dann nicht.

Wir haben das PCP kennengelernt. Was gilt hierbei dür die Entscheidbarkeit?

Das PCP ist semi-entscheidbar, aber unentscheidbar. Semi-entscheidbar, da man für immer größer werdende n alle Reihenfolgen durchgehen kann. Unentscheidbar, weil das Halteproblem als Spezialfall des PCP unentscheidbar ist.

Wir sind dabei nicht direkt vom Halteproblem zum PCP gegangen, dies wäre zu komplex. Welches Spezialproblem haben wir hierfür genutzt?

Das MPCPC. Hierbei steht der Anfangsstein fest und man sucht danach wieder nach einer Reihenfolge, sodass x1 bis xn = y1 bis yn

Was musste schriftlich gelöst werden?

Ich habe den Fibonacci-Algorithmus aufgeschrieben. Außerdem sollte ich aufzeichnen, was beim Löschen eines Knoten im Suchbaum passiert.

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

Vor mir war noch eine weitere Prüfung, daher musste ich etwas warten. Als ich reinkam, ging es dann aber auch sofort los.
Die beiden haben sich nach der Prüfung kaum mehr als 30 Sekunden beraten. Die Begründung für die 1,3 lag darin, dass ich beim Suchbaum nicht wusste, wie das Löschen eines Knoten verläuft.

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

Nicht wirklich. Wenn man viel zum Thema zu reden hat, warten sie meist bis man alles erzählt hat, was man erzählen wollte. Sie wissen aber genau welche Antwort sie hören wollen und fragen auch so lange weiter bis man entweder doch noch darauf kommt oder klar ist, dass man es einfach nicht weiß.

Zum Verhalten der Prüfer:

Beide super nett und großzügig in der Bewertung. Ich hatte den Eindruck, dass ich an sehr vielen Stellen gestockt habe und sie mich mehrmals fragen mussten, um die richtige Antwort zu erhalten. Doch solange dann irgendwann das richtige kam, haben sie sich auch damit zufrieden gegeben ohne Punkte abzuziehen.