Gedächtnisprotokoll FGI109-1 - Versionsgeschichte

1steenfa: Bot: Kosmetische Änderungen

2012-06-08T16:05:43Z

Bot: Kosmetische Änderungen

← Nächstältere Version		Version vom 8. Juni 2012, 16:05 Uhr
Zeile 2:		Zeile 2:


	== Aufgabe1 ==		== Aufgabe1 ==

	1. Erläutere folgende Zeichen (Zeichen für Implikation, Ableitung mittels Modus Ponens und Folgerbarkeit war gegeben).		1. Erläutere folgende Zeichen (Zeichen für Implikation, Ableitung mittels Modus Ponens und Folgerbarkeit war gegeben).
Zeile 34:		Zeile 34:
	c) Begründen Sie, dass der Algorithmus "unerfüllbar" nur für unerfüllbare Formeln liefert.		c) Begründen Sie, dass der Algorithmus "unerfüllbar" nur für unerfüllbare Formeln liefert.

	== Aufgabe 5: Resolution ==		== Aufgabe 5: Resolution ==
	Folgerbarkeit einer Formel F von einer Formelmenge M zeigen (stand afaik zeigen da, d.h. es war klar, dass sie Folgerbar war..)		Folgerbarkeit einer Formel F von einer Formelmenge M zeigen (stand afaik zeigen da, d.h. es war klar, dass sie Folgerbar war..)

Zeile 108:		Zeile 108:
	a-Pfeil von q0 nach q1 und von q0 nach q0, b-Pfeil von q1 nach q0, das wars glaub ich..)		a-Pfeil von q0 nach q1 und von q0 nach q0, b-Pfeil von q1 nach q0, das wars glaub ich..)

	== 6. ==		== 6. ==
	Wie würdest du vorgehen, wenn du testen willst, ob ein Problem NP-vollständig ist?		Wie würdest du vorgehen, wenn du testen willst, ob ein Problem NP-vollständig ist?


	[[Kategorie:Gedaechtnisprotokoll\|FGI1]]		[[Kategorie:Gedaechtnisprotokoll\|FGI1]]

Phil: hat ?Gedächtnisprotokoll FGI1-2009-1? nach ?Gedächtnisprotokoll FGI109-1? verschoben: schaut besser aus ;)

2009-09-01T13:39:40Z

hat ?Gedächtnisprotokoll FGI1-2009-1? nach ?Gedächtnisprotokoll FGI109-1? verschoben: schaut besser aus ;)

← Nächstältere Version	Version vom 1. September 2009, 13:39 Uhr
(kein Unterschied)

92.224.124.141: /* 3. Aussagen über formale Sprache, PSpace, NSpace, Entscheidbarkeit */

2009-07-28T22:39:24Z

3. Aussagen über formale Sprache, PSpace, NSpace, Entscheidbarkeit

← Nächstältere Version		Version vom 28. Juli 2009, 22:39 Uhr
Zeile 93:		Zeile 93:
	a) Das Komplement jeder entscheidbaren Menge ist aufzählbar.		a) Das Komplement jeder entscheidbaren Menge ist aufzählbar.

	b) ~~PSpace~~ ist Teilmenge von Cs ist Teilmenge von NSpace.		b) DSpace ist Teilmenge von Cs ist Teilmenge von NSpace.

	d) Jedes Problem in NP ist entscheidbar.		d) Jedes Problem in NP ist entscheidbar.

84.144.86.100: Formatierung angepasst

2009-07-28T10:01:03Z

Formatierung angepasst

← Nächstältere Version		Version vom 28. Juli 2009, 10:01 Uhr
Zeile 6:		Zeile 6:
	1. Erläutere folgende Zeichen (Zeichen für Implikation, Ableitung mittels Modus Ponens und Folgerbarkeit war gegeben).		1. Erläutere folgende Zeichen (Zeichen für Implikation, Ableitung mittels Modus Ponens und Folgerbarkeit war gegeben).
	Erläutere den Zusammenhang zwischen folgenden zeichen:		Erläutere den Zusammenhang zwischen folgenden zeichen:


	a) Folgerbarkeit - Implikation		a) Folgerbarkeit - Implikation

	b) Implikation - Modus Ponens		b) Implikation - Modus Ponens

	c) Modus Ponens - Folgerbarkeit		c) Modus Ponens - Folgerbarkeit

Zeile 22:		Zeile 25:
	== Aufgabe 4 ==		== Aufgabe 4 ==
	Noch eine aus dem ersten Teil zum Markierungsalgorithmus:		Noch eine aus dem ersten Teil zum Markierungsalgorithmus:


	a) Welche Eingabe nimmt der Algorithmus, welches Resultat liefert er?		a) Welche Eingabe nimmt der Algorithmus, welches Resultat liefert er?
	Gib Eingabe und Ausgabe an und beschreibe den Algorithmus möglichst genau!		Gib Eingabe und Ausgabe an und beschreibe den Algorithmus möglichst genau!

	b) Begründen Sie, warum der Algorithmus immer terminiert.		b) Begründen Sie, warum der Algorithmus immer terminiert.

	c) Begründen Sie, dass der Algorithmus "unerfüllbar" nur für unerfüllbare Formeln liefert.		c) Begründen Sie, dass der Algorithmus "unerfüllbar" nur für unerfüllbare Formeln liefert.

Zeile 32:		Zeile 39:
	== Aufgabe 6: Unifikation ==		== Aufgabe 6: Unifikation ==
	3 Prädikatenlogische Formelmengen waren gegeben und man sollte begründen/wiederlegen warum man sie (nicht) unifizieren kann		3 Prädikatenlogische Formelmengen waren gegeben und man sollte begründen/wiederlegen warum man sie (nicht) unifizieren kann

	u, v, w, x, y, z - Variablen		u, v, w, x, y, z - Variablen

	P - Aussagensymbol		P - Aussagensymbol
	a) P( irgendwas ) P ( irgendas ) P (Irgendwas)

			a) P( irgendwas ) P ( irgendas ) P (Irgendwas)

	b) Blub		b) Blub

	c) P ( h ( x, f(w) ), x), P( f(y), h(z), y)		c) P ( h ( x, f(w) ), x), P( f(y), h(z), y)

	(So etwa)		(So etwa)

	== Aufgabe 7(?) - ne, das muss auch irgendwo im 2. Teil gewesen sein. Jeder Teil hatte 6 Aufgaben. ==		== Aufgabe 7(?) - ne, das muss auch irgendwo im 2. Teil gewesen sein. Jeder Teil hatte 6 Aufgaben. ==
	Ist die Menge 2^M immer abzählbar, wenn		Ist die Menge 2^M immer abzählbar, wenn

	O M abzählbar ist		O M abzählbar ist

	O M aufzählbar ist		O M aufzählbar ist

	O M endlich ist		O M endlich ist

Zeile 50:		Zeile 67:
	== 1. ==		== 1. ==
	Alphabet gegeben (a, b). Gib jeweils geforderte Sprache sowie alle Wörter der Länge 3 über Alphabet-Stern an, die nicht enthalten sind!		Alphabet gegeben (a, b). Gib jeweils geforderte Sprache sowie alle Wörter der Länge 3 über Alphabet-Stern an, die nicht enthalten sind!


	a) Alle Wörter, in denen kein a vor einem b steht		a) Alle Wörter, in denen kein a vor einem b steht
Zeile 59:		Zeile 77:
	== 2. ==		== 2. ==
	Kellerautomat gegeben		Kellerautomat gegeben


	a) Gib alle Wörter bis zur Länge 4 an, die mit Endzustand akzeptiert werden.		a) Gib alle Wörter bis zur Länge 4 an, die mit Endzustand akzeptiert werden.
Zeile 70:		Zeile 89:
	== 3. Aussagen über formale Sprache, PSpace, NSpace, Entscheidbarkeit ==		== 3. Aussagen über formale Sprache, PSpace, NSpace, Entscheidbarkeit ==
	Man konnte jeweils "Ja" oder "Nein" ankreuzen		Man konnte jeweils "Ja" oder "Nein" ankreuzen


	a) Das Komplement jeder entscheidbaren Menge ist aufzählbar.		a) Das Komplement jeder entscheidbaren Menge ist aufzählbar.

	b) PSpace ist Teilmenge von Cs ist Teilmenge von NSpace.		b) PSpace ist Teilmenge von Cs ist Teilmenge von NSpace.

	d) Jedes Problem in NP ist entscheidbar.		d) Jedes Problem in NP ist entscheidbar.

	== 4. ==		== 4. ==
	a) Definiere Entscheidbarkeit		a) Definiere Entscheidbarkeit

	b) Wieder Aussagen und Fragen		b) Wieder Aussagen und Fragen

	== 5. ==		== 5. ==
	Deterministischer Automat gegeben - erstelle Potenzautomat		Deterministischer Automat gegeben - erstelle Potenzautomat

	(Zustände q0 und q1, q1 Endzustand, q0 Anfangszustand,		(Zustände q0 und q1, q1 Endzustand, q0 Anfangszustand,
	a-Pfeil von q0 nach q1 und von q0 nach q0, b-Pfeil von q1 nach q0, das wars glaub ich..)		a-Pfeil von q0 nach q1 und von q0 nach q0, b-Pfeil von q1 nach q0, das wars glaub ich..)

84.144.86.100: Ja/Nein-Fragen hinzugefügt bzw. editiert

2009-07-28T09:55:13Z

Ja/Nein-Fragen hinzugefügt bzw. editiert

← Nächstältere Version		Version vom 28. Juli 2009, 09:55 Uhr
Zeile 40:		Zeile 40:

	== Aufgabe 7(?) - ne, das muss auch irgendwo im 2. Teil gewesen sein. Jeder Teil hatte 6 Aufgaben. ==		== Aufgabe 7(?) - ne, das muss auch irgendwo im 2. Teil gewesen sein. Jeder Teil hatte 6 Aufgaben. ==
	Ist die Menge 2^M abzählbar, wenn		Ist die Menge 2^M immer abzählbar, wenn
	O M abzählbar ist		O M abzählbar ist
	O M aufzählbar ist		O M aufzählbar ist
	O M ~~entscheidbar~~ ist		O M endlich ist

	waren insgesamt 7 aufgaben im ersten teil, die andere weiß ich grad nicht..		waren insgesamt 7 aufgaben im ersten teil, die andere weiß ich grad nicht..
Zeile 69:		Zeile 69:

	== 3. Aussagen über formale Sprache, PSpace, NSpace, Entscheidbarkeit ==		== 3. Aussagen über formale Sprache, PSpace, NSpace, Entscheidbarkeit ==
			Man konnte jeweils "Ja" oder "Nein" ankreuzen

	b) PSpace ist Teilmenge von Cs ist Teilmenge von NSpace. ~~Ja oder nein?~~		a) Das Komplement jeder entscheidbaren Menge ist aufzählbar.
			b) PSpace ist Teilmenge von Cs ist Teilmenge von NSpace.
			d) Jedes Problem in NP ist entscheidbar.

	== 4. ==		== 4. ==

80.171.195.118: /* Aufgabe 7(?) */

2009-07-27T23:05:51Z

Aufgabe 7(?)

← Nächstältere Version		Version vom 27. Juli 2009, 23:05 Uhr
Zeile 39:		Zeile 39:
	(So etwa)		(So etwa)

	== Aufgabe 7(?) ==		== Aufgabe 7(?) - ne, das muss auch irgendwo im 2. Teil gewesen sein. Jeder Teil hatte 6 Aufgaben. ==
	Ist die Menge 2^M abzählbar, wenn		Ist die Menge 2^M abzählbar, wenn
	O M abzählbar ist		O M abzählbar ist

85.176.95.40: /* 5. */

2009-07-27T18:46:49Z

← Nächstältere Version		Version vom 27. Juli 2009, 18:46 Uhr
Zeile 77:		Zeile 77:

	== 5. ==		== 5. ==
	Deterministischer Automat gegeben - erstelle ~~nichtdeterministischen~~ (Zustände q0 und q1, q1 Endzustand, q0		Deterministischer Automat gegeben - erstelle Potenzautomat
			(Zustände q0 und q1, q1 Endzustand, q0 Anfangszustand,
	Anfangszustand, a-Pfeil von q0 nach q1 und von q0 nach q0, b-Pfeil von q1 nach q0, das wars glaub ich..)		a-Pfeil von q0 nach q1 und von q0 nach q0, b-Pfeil von q1 nach q0, das wars glaub ich..)

	== 6. ==		== 6. ==

85.176.95.40: /* 2. */

2009-07-27T18:46:02Z

← Nächstältere Version		Version vom 27. Juli 2009, 18:46 Uhr
Zeile 68:		Zeile 68:
	d) Gib ein Wort w aus L mit \|w\| >= 2 inkl. der Konfiguration an, das mit Endzustand akzeptiert wird		d) Gib ein Wort w aus L mit \|w\| >= 2 inkl. der Konfiguration an, das mit Endzustand akzeptiert wird

	== 3. == Aussagen über formale Sprache, ~~NPSpace~~, NSpace, Entscheidbarkeit		== 3. Aussagen über formale Sprache, PSpace, NSpace, Entscheidbarkeit ==

			b) PSpace ist Teilmenge von Cs ist Teilmenge von NSpace. Ja oder nein?

	== 4. ==		== 4. ==

85.176.95.40: /* 2. */

2009-07-27T18:44:07Z

← Nächstältere Version		Version vom 27. Juli 2009, 18:44 Uhr
Zeile 58:		Zeile 58:

	== 2. ==		== 2. ==
	Kellerautomat gegeben ~~- gib~~ an, ~~welche Sprache aktzeptiert~~ wird.		Kellerautomat gegeben

			a) Gib alle Wörter bis zur Länge 4 an, die mit Endzustand akzeptiert werden.

			b) Gib alle Wörter bis zur Länge 4 an, die mit leerem Keller akzeptiert werden.

			c) Gib ein Wort w aus L mit \|w\| >= 2 inkl. der Konfiguration an, das mit leerem Keller akzeptiert wird.

			d) Gib ein Wort w aus L mit \|w\| >= 2 inkl. der Konfiguration an, das mit Endzustand akzeptiert wird

	== 3. == Aussagen über formale Sprache, NPSpace, NSpace, Entscheidbarkeit		== 3. == Aussagen über formale Sprache, NPSpace, NSpace, Entscheidbarkeit

85.176.95.40: /* 1. */

2009-07-27T18:40:57Z

← Nächstältere Version		Version vom 27. Juli 2009, 18:40 Uhr
Zeile 55:		Zeile 55:
	b) Alle Wörter, in denen ab oder ba, aber nicht beide enthalten sind		b) Alle Wörter, in denen ab oder ba, aber nicht beide enthalten sind

	(~~Die Aufgabe war glaub ich umfangreicher..~~)		c) Konstruiere einen DFA (mit allen Angaben) zur Sprache L = {w aus {a,b}* \| Es gibt eine natürliche Zahl n für die gilt: \|w\|a = 2n}

	== 2. ==		== 2. ==