TheGI 1 (StuPO90)/Gedächtnisprotokolle der mündlichen Prüfung

1. Bericht vom 14.02.05:

Als Aufgabe gab es eine Kellermaschine, die '01'-er-Gruppen liest und je eine 1 in den Keller schreibt, danach wieder '01'-er-Gruppen liest und je eine 1 aus dem Keller löscht. L = { (01) hoch 2n | n element N plus } = gerade Zahlen von 01er-Gruppen, leeres Wort nicht enthalten. Aufwaende: t_M(w) = |w|+2 (linear) s_M(w) = 5/4 * |w| (auch linear) also L element NTIME(n) und L element NSPACE(n) weil ja die Maschine nichtdeterministisch war. Achtung: Die Sprache ist regulaer, man kann auch einen Automaten dafür basteln. T_M(n) = n+2 fuer n=4k und k element N plus, fuer alle andern n ist T_M(n)=0 ! das liegt an der Definition vom Zeitaufwand nichtdeterministischer Maschinen!

Die Fragen die dann kamen waren Querfeldein:

Was ist P/NP? Verhaeltnis? Entscheider/Akzeptoren? Was für Operationen gehen auf akzeptierbaren und entscheidbaren Sprachen (Vereinigung, Komplement usw.)... Beispiel fuer ein NP-Problem.

Es dürfte in jedem Fall hilfreich sein, in den Definitionen dieser Zeit/Platzschranken firm zu sein.

-- Ellen 20:13, 14. Feb 2005 (CET)

2. Bericht vom 14.02.05:

Es ging um einen nichtdeterministischen Automaten, der bei Eingabe von einer 0 oder einer eins und dann beliebig vielen nullen, oder beliebig vielen nullen und anschließend einer eins in einem Endzustand ankam. Dieser musste deterministisch gemacht werden. Sonst kamen alle möglichen Fragen.

Auch wenn das Gespräch teilweise nicht besonders flüssig voran ging (teilweise bestimmt 15 Sekunden Pause) und sie auch manchmal minimal daneben lagen, bzw. etwas gebraucht haben um auf die Lösung zu kommen, haben alle drei besser als 2,0 bekommen.

-- Ellen 20:13, 14. Feb 2005 (CET)

3. Bericht vom 15.02.05:

Gegeben war die Sprache L= a^n b^m c^n | n,m> 0} Aufgabe: Grammatik dazu entwerfen, Ist die Sprache regulär? kontextfrei? Turingmaschine dazu entwerfen, ist diese TM in P oder NP und Komplexität.