Computer Science, 2017-04-05

Module: 
Computer Science
Examiner: 
Prof. Vornberger
Assessor: 
Prof. Chimani
Date: 
Wed, 2017-04-05

VORBEREITUNG

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

InfoA: Skript und (wo nötig) Vorlesungsaufzeichnungen
InfoD: Slides
Sehr hilfreich waren auch die alten Prüfungsprotokolle; einerseits als Kontrolle, wie sicher man den Stoff beherrscht und andererseits, um besser einschätzen zu können, welche (Art von) Fragen wohl dran kommen könnten.

PRÜFUNG

Prüfungsdatum: 05.04.2017
Wiederholungsprüfung? nein
Note: 1.0
Bereiche nach Zeit: halb-halb

Fragensammlung: wie lauteten die Fragen im einzelnen?

InfoA
- Rekursion am Beispiel der Türme von Hanoi?
- Rekursion am Beispiel der Fibonacci-Zahlen?
- Rekursionsgleichung + Laufzeit beider Algorithmen?
- Wo wird Rekursion sonst verwendet?
- Erkläre Quicksort
- Laufzeit(en) von Quicksort?
- Ist diese Laufzeit (O(n*log n) gut oder schlecht?
- Warum ist n * log n eine untere Schranke für einen vergleichenden Sortieralgorithmus?
InfoD
- Definiere P und NP
- Was ist ein Zeuge?
- Welche Komplexitäten gibt es außerdem?
(Wollte auf NP-vollständig hinaus.)
- Definiere NP-vollständig
- Definiere Reduktion
- Definiere Co-NP*
- Was ist die Ackermannfunktion? Weshalb haben wir uns damit beschäftigt?
- Was ist die Kolmogorov-Komplexität?
- Weshalb ist sie unberechenbar?

*Ich bin mir nicht sicher, ob diese Frage wirklich gestellt wurde oder ich mir diese Frage vorher gestellt hatte. Schadet aber nichts, sie beantworten zu können. :D

Was mußte schriftlich gelöst werden?

Die Rekursionsgleichungen für die Türme von Hanoi und Fibonacci sollte ich aufschreiben. Außerdem habe ich Zettel und Stift auch bei ein paar anderen Aufgaben für Notizen/Kritzeleien benutzt.

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

Eher nein. Ich denke, dass beide vorher ziemlich genau wussten, was sie fragen wollen.