Vordiplom Theoretische Informatik
Kurs 1653/1654 Version 98

A Berechenbarkeit

Wann ist eine Zahlenfunktion berechenbar?

Wenn es eine Registermaschine gibt, die diese Funktion berechnet. My Rekursion habe ich nicht erwähnt, wurde auch nicht nachgefragt.

Ist die Funktion y = x² berechenbar?

Ja (zu genauerer Erklärung brauchte ich nicht mehr anzusetzen)

Überleitung zu Turing- und Bandmaschinen / Konfigurationen bei Bandmaschinen Wie ist die Datenmenge einer Bandmaschine definiert?

D = ( Gamma* x Gamma x Gamma*) und genaue Erläuterung der tatsächlichen Bedeutung dieser Definition: Tripel (u,a,v) mit u,a,v als Worte links, unter, rechts vom Schreib/Lesekopf.

Befehlssatz einer Bandmaschine

L, R, t(a), f(a)

Gibt es einen Zusammenhang zwischen Wort- und Zahlenfunktionen? Zusammenhang zwischen ihrer Berechenbarkeit?

Zusammenhang ueber Standardnumerierung Ny. Erklärung mit Diagramm: Wortfunktion g berechenbar, gdw. ihre zugehörige Zahlenfunktion ny-1 g ny berechenbar.

Was ist klein-phi?

Abbildung von N in P1, Zusammensetzung der Funktion, Bedeutung (mehr generelle Erläuterung, zur genauen Definition kam ich nicht mehr)

UTM und SMN Theorem als Anforderung an Programmiersprache klein-phi: Was ist das Besondere an klein-phi?

-hier verlor ich zum ersten Mal den Faden - wesentlich ist aber, daß es unendlich viele Numerierungen gibt, die das utm Theorem nicht erfüllen. Daraufhin habe ich von mir aus den Äquivalenzsatz erwaehnt/erklärt, was anscheinend o.k. war.

Wann ist eine Menge rekursiv bzw. rekursiv-aufzählbar? Welcher Zusammenhang besteht zwischen rekursiven und r.a. Mengen?

sämtliche Definition und Sätze dazu.

Kennen Sie eine Menge die r.a. ist, aber nicht rekursiv?

Kphi - mit genauer Definition von Kphi und Beweis, wobei beim Beweis für r.a. die Erwähnung des utm Theorems schon genügte, der Beweis für die Nichtrekusivität (über N \ Kphi nicht r.a.) mußte dagegen genau sein.

Wie ist die Berechnung in Q definiert?

Definition und Erläuterung der Nyrat-Darstellung von Q

Was ist das Problem der Berechnung bei reellen Zahlen? Welcher MaschinenTyp wird benutzt?

Reelle Zahlen überabzählbar, d.h. es existiert keine Numerierung auf R, statt dessen wird mit Cauchy Dastellung ein x aus R durch unendliche Zahlenreihe "angenähert" ; Typ-2 Maschine erläutert

B Sprachen

Ist L={ w aus {0,1}* | 010 Teilwort von w } regulär?

Ja. Als regulärer Ausdruck {0 u 1}* . {010} . {0 u 1}* darstellbar.

Ist L={ wwR | w aus Sigma* } regulär?

Nein. Nicht regulär, aber nichtdeterministisch kontextfrei. Erklärung, daß kein Endlicher Automat konstruierbar ist, der wwR erzeugen kann, aber das Erkennen durch Kellerautomat möglich ist. Unterschied det./nicht det. Kellerautomat und L={ w$wR } als Beispiel für det. ktf. Sprache. Pumping Lemmata wurden nicht nachgefragt.

Regelmenge der kontextfreien Grammatiken in Chomsky Normalform?

C Komplexitaetstheorie

Welches ist der Zusammenhang zwischen Bandbedarf Sm(x) und Zeitbedarf Tm(x) -

Definitionen mit Beweisidee - beim Beweis der Abschätzung von Tm mußte ich passen

Wie ist NP Vollständigkeit erklärt?

Definition NP Vollständig mit Angabe Def. NP Hart, Pol-Reduzierbarkeit

Genereller Eindruck der Prüfung:

Insgesamt war die Atmosphäre während der Prüfung vollkommen ruhig und entspannt. Als Vorbereitung auf die Prüfung habe ich in der Hauptsache die Protokolle der letzten beiden Jahre gründlich durchgearbeitet.

W. wirft die Fragen nicht in den luftleeren Raum, sondern leitet sie immer mit einigen Worten ein. Trotzdem hatte ich bei 2 oder 3 Fragen Schwierigkeiten, sofort zu erkennen, worauf er abzielte, fand jedoch meistens nach entsprechenden Stichworten seinerseits recht schnell wieder den Faden. Ich hatte weder den Eindruck, hängen gelassen zu werden in einer solchen Situation, noch empfand ich, daß mir eben dieses "auf-dem-Schlauch-stehen" negativ angelastet wurde. Allerdings hatte ich schon das Gefühl, W. kann sehr genau sondieren, ob man sich denn tatsächlich mit dem Stoff auseinandergesetzt hat oder nicht - auf stupides Auswendiglernen allein sollte man sich nicht verlassen, sondern schon eine gewisse Liebe zum Detail entwickeln (beispielsweise bei Definitionen von smn Theorem und rek. / r.a. Mengen verstehen, wann eine partiell rekursive und wann eine total rekursive Funktion notwendig ist).

Sehr geholfen hat mir, mit anderen zusammen Prüfung zu "spielen", also wirklich über das Thema zu reden. Erst dabei habe ich wirklich gelernt, genau und somit korrekt, die Fragen zu beantworten.