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

Buchholz: TheGI 1 Gedächtnisprotokolle der mündlichen Prüfung wurde nach TheGI 1 (StuPO90)/Gedächtnisprotokolle der mündlichen Prüfung verschoben

2006-08-17T18:02:23Z

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

Buchholz: Gedächtnisprotokolle der mündlichen Prüfung wurde nach TheGI 1 Gedächtnisprotokolle der mündlichen Prüfung verschoben

2006-02-27T21:44:43Z

Gedächtnisprotokolle der mündlichen Prüfung wurde nach TheGI 1 Gedächtnisprotokolle der mündlichen Prüfung verschoben

Ghandi: Weiteres Protokoll

2005-02-15T19:37:19Z

Weiteres Protokoll

84.191.61.194 am 15. Februar 2005 um 15:04 Uhr

2005-02-15T15:04:40Z

Ellen: /* 2. Bericht vom 14.02.05: */

2005-02-14T19:34:55Z

‎2. Bericht vom 14.02.05:

Ellen: 1. Protokoll

2005-02-14T19:13:06Z

1. Protokoll

Neue Seite

====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.

-- [[Benutzer:Ellen|Ellen]] 20:13, 14. Feb 2005 (CET) (ohne Gewähr ;))

← Nächstältere Version		Version vom 15. Februar 2005, 19:37 Uhr
Zeile 34:		Zeile 34:
	Gegeben war die Sprache L= a^n b^m c^n \| n,m> 0}		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.		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.
		+
		+	--[[Benutzer:Ghandi\|Ghandi]] 20:37, 15. Feb 2005 (CET)

← Nächstältere Version		Version vom 15. Februar 2005, 15:04 Uhr
Zeile 30:		Zeile 30:

	-- [[Benutzer:Ellen\|Ellen]] 20:13, 14. Feb 2005 (CET)		-- [[Benutzer:Ellen\|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.

← Nächstältere Version		Version vom 14. Februar 2005, 19:34 Uhr
Zeile 17:		Zeile 17:
	Es dürfte in jedem Fall hilfreich sein, in den Definitionen dieser Zeit/Platzschranken firm zu sein.		Es dürfte in jedem Fall hilfreich sein, in den Definitionen dieser Zeit/Platzschranken firm zu sein.

−	-- [[Benutzer:Ellen\|Ellen]] 20:13, 14. Feb 2005 (CET) (~~ohne Gewähr ;~~))	+
		+	-- [[Benutzer:Ellen\|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.
		+
		+
		+	-- [[Benutzer:Ellen\|Ellen]] 20:13, 14. Feb 2005 (CET)

← Nächstältere Version	Version vom 17. August 2006, 18:02 Uhr
(kein Unterschied)

← Nächstältere Version	Version vom 27. Februar 2006, 21:44 Uhr
(kein Unterschied)