FGI-I Klausur Gedächtnisprotokoll SS09 Erster Termin
2009-07-27 19:16
DaGeRe
Moin Leute,
Ich fand das Gedächtnisprotokoll vom letzten Jahr bei der Vorbereitung ganz hilfreich, deshalb finde ich, wir können ja mal aus Solidarität für den nächsten Jahrgang die Klausur zusammentragen.
Mir ist soviel noch eingefallen:
Aussagenlogischer Teil:
1. Erläutere folgende Zeichen (Zeichen für Implikation, Ableitung mittels Modus Ponens und Folgerbarkeit war gegeben).
Erläutere den Zusammenhang zwischen folgenden zeichen:
a) Folgerbarkeit - Implikation
b) Implikation - Modus Ponens
c) Modus Ponens - Folgerbarkeit
2. F und G seien aussagenlogische Formeln. Unter welchen der Folgenden Bedingungen kann F gültig, kontingent oder unerfüllbar sein?
Jetzt kamen ein paar Formeln, ich krieg sie allerdings nicht mehr zusammen.
F => G
F v G und G unerfüllbar
(glaub ich)
3. Definiere Hornklausel, Hornformel, Literal und Implikationsschreibweise.
4. Markierungsalgorithmus:
a) Beschreibe den Markierungsalgorithmus möglichst genau (mit Eingabe, Ausgabe und Vorgehen)
b) Irgendne Frage zum Markierungsalgorithmus
c) Wieso ist die Ausgabe unerfüllbar korrekt?
5. Resolution: eine Formelmenge und eine Formel gegeben, zeige die Folgerbarkeit mittels Aussagenlogischer Reduktion.
6. 3 Prädikatenlogische Formelmengen, sind diese unifizierbar? Wenn ja, gib den Allgemeinen Unifikator an, wenn nein, gib den Grund an, weshalb nicht
c) P ( h ( x, f(w) ), x), P( f(y), h(z), y)
Prädikatenlogischer Teil
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!
a) Alle Wörter, in denen kein a vor einem b steht
b) Alle Wörter, in denen ab oder ba, aber nicht beide enthalten sind
(Die Aufgabe war glaub ich umfangreicher..)
2. Kellerautomat gegeben - gib an, welche Sprache aktzeptiert wird.
3. Aussagen über formale Sprache, NPSpace, NSpace, Entscheidbarkeit
4.
a) Definiere Entscheidbarkeit
b) Wieder Aussagen und Fragen
5. Nichtdeterministischer Automat gegeben - erstelle Deterministischen (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..)
6.
a) Wie würdest du vorgehen, wenn du testen willst, ob ein Problem NP-vollständig ist?
b) Kreuze an:
Ist die Menge 2^M abzählbar, wenn
O M abzählbar ist
O M aufzählbar ist
O M entscheidbar ist
Mehr fällt mir leider nicht mehr ein, ist schon bisschen faszinierend, wie schnell man so was vergisst..
Wenn jemandem noch was einfällt, wär es nett, wenn ers dazu schreibt. Wir könnten das ganze ja auch mal texen, damit die nächsten ne richtige Beispielklausur haben ;)
/edit: paar Änderungen eingefügt..
Ich fand das Gedächtnisprotokoll vom letzten Jahr bei der Vorbereitung ganz hilfreich, deshalb finde ich, wir können ja mal aus Solidarität für den nächsten Jahrgang die Klausur zusammentragen.
Mir ist soviel noch eingefallen:
Aussagenlogischer Teil:
1. Erläutere folgende Zeichen (Zeichen für Implikation, Ableitung mittels Modus Ponens und Folgerbarkeit war gegeben).
Erläutere den Zusammenhang zwischen folgenden zeichen:
a) Folgerbarkeit - Implikation
b) Implikation - Modus Ponens
c) Modus Ponens - Folgerbarkeit
2. F und G seien aussagenlogische Formeln. Unter welchen der Folgenden Bedingungen kann F gültig, kontingent oder unerfüllbar sein?
Jetzt kamen ein paar Formeln, ich krieg sie allerdings nicht mehr zusammen.
F => G
F v G und G unerfüllbar
(glaub ich)
3. Definiere Hornklausel, Hornformel, Literal und Implikationsschreibweise.
4. Markierungsalgorithmus:
a) Beschreibe den Markierungsalgorithmus möglichst genau (mit Eingabe, Ausgabe und Vorgehen)
b) Irgendne Frage zum Markierungsalgorithmus
c) Wieso ist die Ausgabe unerfüllbar korrekt?
5. Resolution: eine Formelmenge und eine Formel gegeben, zeige die Folgerbarkeit mittels Aussagenlogischer Reduktion.
6. 3 Prädikatenlogische Formelmengen, sind diese unifizierbar? Wenn ja, gib den Allgemeinen Unifikator an, wenn nein, gib den Grund an, weshalb nicht
c) P ( h ( x, f(w) ), x), P( f(y), h(z), y)
Prädikatenlogischer Teil
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!
a) Alle Wörter, in denen kein a vor einem b steht
b) Alle Wörter, in denen ab oder ba, aber nicht beide enthalten sind
(Die Aufgabe war glaub ich umfangreicher..)
2. Kellerautomat gegeben - gib an, welche Sprache aktzeptiert wird.
3. Aussagen über formale Sprache, NPSpace, NSpace, Entscheidbarkeit
4.
a) Definiere Entscheidbarkeit
b) Wieder Aussagen und Fragen
5. Nichtdeterministischer Automat gegeben - erstelle Deterministischen (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..)
6.
a) Wie würdest du vorgehen, wenn du testen willst, ob ein Problem NP-vollständig ist?
b) Kreuze an:
Ist die Menge 2^M abzählbar, wenn
O M abzählbar ist
O M aufzählbar ist
O M entscheidbar ist
Mehr fällt mir leider nicht mehr ein, ist schon bisschen faszinierend, wie schnell man so was vergisst..
Wenn jemandem noch was einfällt, wär es nett, wenn ers dazu schreibt. Wir könnten das ganze ja auch mal texen, damit die nächsten ne richtige Beispielklausur haben ;)
/edit: paar Änderungen eingefügt..