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

Prüfer:Prof. Weihrauch
Termin:05.10.2000, 12.30 Uhr
Dauer:ca. 25 Minuten
Note:1,0

Fragen zum Teil A:

Wann ist eine Zahlenfunktion f berechenbar?

Ist f = 7x berechenbar?
Wann ist eine Wortfunktion g berechenbar?
Wie kommt man von einer Turingmaschine zu einer Bandmaschine?
Was muss man machen, wenn man ein Zeichen vom ehemaligen Band 3 lesen will?
Wie ist der Zusammenhang zwischen Zahlen- und Wortfunktionen?
Ist die Menge Schnittmenge von A und B r. a., wenn A und B r. a. sind?
Und wie ist das bei der Vereinigung von A und B?
Wann ist eine Menge r. a.?
Wann ist eine Menge rekursiv?
Welche Definition gibt es dafür noch?
Ist die Menge der Zweierpotenzen rek.?
Welche Menge ist nicht rek., aber r. a.?
N/Kj ist nicht r. a..Gibt es eine Menge, die nicht r. a. ist und deren Komplement auch nicht r. a. ist?
Wie ist das Äquivalenzproblem definiert?
Wie ist die Standardnummerierung definiert?
Was ist dabei die Syntax?
Wir hatten Funktionen und Programme. Wie ist nun der Zusammenhang?
Welche Anforderungen an eine Programmiersprache hatten wir besprochen?
Wie ist das utm-Theorem definiert?
Eine Sprache kann in eine andere übersetzt werden. Welchen Satz hatten wir dazu erwähnt?
Wie lautet, denn der Äquivalenzsatz von Rogers?


Fragen zum Teil B:

Beispiele:        L1:= {w$wR}, L2:= {wwR}, L3:= {ww}
Was können Sie zu den Mengen bezüglich Kontextfreiheit sagen?
Wie kann man zeigen, dass L3 nicht kontextfrei ist?
Wie lautet der Satz von Savitch?
Was versteht man unter NP-vollständig?
Was versteht man unter NP-hart?
Wir hatten im Kurs die Kontrollturingmaschine eingeführt. Was versteht man unter x ist Element von L(M)?


Mein Eindruck:
Prof. Weihrauch ist sehr freundlich, ruhig, fair, lässt ausreichend Zeit zum Antworten.
Ich kann ihn als Prüfer nur empfehlen!

Viel Erfolg bei Deiner Prüfung!