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) (ohne Gewähr ;))