Mündliche Diplomvorprüfung: Theoretische Informatik A + B

Teil A:

Wann ist eine Zahlenfunktion berechenbar?
Kennen Sie weitere Definitionen? -> WHILE Programme, m - Rekursion
Wie ist denn die m - Rekursion definiert? -> grobe Beschreibung reichte
Wieso sagt man heißt berechenbar? -> Churchsche These
Wann ist eine Wortfunktion berechenbar?
Gibt es einen Zusammenhang zwischen der Berechenbarkeit von Zahlen- und Wortfunktionen?

Überleitung von Prof. Weihrauch zu j -> Definition
Was sind denn hierbei die Programme? -> die natürlichen Zahlen
Die 2 grundlegenden Eigenschaften an dieser Stelle? -> utm und smn
Was ist denn das utm-Theorem? -> Definition und Beschreibung

Wie sieht es denn mit der Berechenbarkeit auf anderen Mengen aus? -> abzählbare Mengen, die reellen Zahlen als Beispiel für eine nicht abzählbare Menge, Darstellung der reellen Zahlen, Problem der nicht berechenbaren Multiplikation bei der Dezimaldarstellung, Cauchy Darstellung
Können Sie beweisen, dass die Multiplikation nicht berechenbar ist?
Kennen Sie den letzten Satz aus der KE 7 (fundamentale Eigenschaft der Algebra) -> war irgendwas mit Stetigkeit, ich wusste aber überhaupt nicht was er wollte

Teil B:

Welche Regeln gelten denn bei den rechtslinearen Grammatiken?
Die Regeln in der Normalform?
Wie kann man denn eine rechtslineare Grammatik in ihre Normalform überführen?
PASCAL ist ja durch eine kontextfreie Grammatik beschreibar (Backus Naur Form). Warum ist es dennoch nicht kontextfrei? -> Wegen Variablendeklaration, Beweis durch PumpingLemma

Überleitung zur Komplexitätstheorie:
Nehmen wie mal die Bandkomplexität. Kennen Sie GAP? -> naja, so ungefähr
Was ist denn das besondere an GAP? -> das man so wenig Band braucht (wusste ich aber nicht)
Wie sind denn P und NP definiert?
Was ist denn das N-NP Problem?
Definition von NP-vollständig?
Was bedeutet A aus NZEIT(n^3) genau? -> alle möglichen Pfade müssen in Zeit n^3 durchlaufen sein (hier wusste ich überhaupt nicht was er hören wollte)

Mein Eindruck von der Prüfung:
Prof. Weihrauch fängt die Prüfung immer gleich an. Das ist schon mal sehr nett. Und dann läßt er sich für die nächste Frage sehr viel Zeit, man merkt wie er überlegt, was er denn mal als nächstes fragen könnte. Ich denke man kann den Prüfungsverlauf sehr gut steuern, da er keinen festen Plan hat.
Und die Benotung ist sehr, sehr wohlwollend. Ich war von meiner guten Note doch echt überrascht.