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.

4. Bericht vom 14.02.05:

Aufgabenblatt:

Ein Nichtdeterministischer Automat war gegeben der die Sprache L={ 0^n | n>=2 } U {1^n | n>=1} akzeptiert.

Fragen zum Automaten:

• Welche Sprache erkennt der Automat?
• Ist der Automat Det. oder Nichtdet.?
• Ist die Sprache kontextfrei? Ist sie regulär?
• Ist der Aufwand linear? Ist er polynomiell?
• Ist die Sprache in P?
• Wandeln sie den Nichtdet. A. in einen Det. A. um.

Die Rücksprache selbst:

• Beweisidee Klasse der reg. Spr. ist über dem Komplement abgeschlossen
• Was ist ein Entscheider?
• Beweis/Veranschaulichung regulär ist in kontextfrei

Da wir glücklicherweise die Letzten waren und es schon recht spät war, fiel die Rücksprache relativ kurz aus: ca. 20 min.

--Ghandi 20:37, 15. Feb 2005 (CET)