FB18 - Das Forum für Informatik

fb18.de / Bachelorstudieng / PM Formale Informatik

FGI-I Klausur Gedächtnisprotokoll SS09 Erster Termin

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

RE: FGI-I Klausur Gedächtnisprotokoll SS09 Erster Termin 2009-07-27 19:20
Julian F.
Nebenan wurde damit schon begonnen, im Fachschaftswiki steht dafür auch schon ein bisschen was: GProt FGI1 2009-1

RE: FGI-I Klausur Gedächtnisprotokoll SS09 Erster Termin 2009-07-27 19:22
Anonymer User
Wir haben in nem anderen Thread auch schon damit begonnen und auch eine Wikiseite angelegt. Deins ist allerdings viel ausführlicher, füg es doch bitte mit ins Wiki ein: http://www.informatik.uni-hamburg.de/Fachschaft/wiki/index.php/Ged%C3%A4chtnisprotokoll_FGI1-2009-1
Da können alle mitarbeiten und wenn es fertig ist kann sich auch jemand darum kümmern das zu texen.

RE: FGI-I Klausur Gedächtnisprotokoll SS09 Erster Termin 2009-07-27 19:22
DaGeRe
Hups, hab ich irgendwie übersehen. Ich füg das mal zusammen…

edit: ist drin.

RE: FGI-I Klausur Gedächtnisprotokoll SS09 Erster Termin 2009-07-27 21:07
peace
Dankesehr! Gprots sind immer wichtig!

RE: FGI-I Klausur Gedächtnisprotokoll SS09 Erster Termin 2009-07-28 09:41
Anonymer User
Beim Logik Teil Aufgabe 2 meine ich mich noch an die hier erinnern zu können aber ohne gewähr:

G unerfüllbar, G => F gültig
F => G unerfüllbar

4b) War "Warum terminiert der Algorithmus auf jeden Fall?"

Am Anfang vom Aussagenlogischen Teil war noch ne Frage zur Gleichheit von regulären Mengen:

ja/nein - (leere Menge)^+ und (leere Menge)*
ja/nein - (a* b*)* und (a + b)*
ja/nein - ?
ja/nein - ?

Zum Nichtdeterministischen Automaten:
Der hatte noch eine b-Kante von q1 nach q1.

Bei 1 sollte man ganz am Ende noch einen DFA bauen, der Eine Sprache über dem Alphabet {a, b} akzeptiert, bei der die Zahl der a's ein Vielfaches von 2 ist, also |w|a = 2n, n aus nat. Zahlen.

Die Ankreuzfragen auf der vorletzten Seite:
ja/nein - DSpace(n) teilmenge von Cs teilmenge von Nspace(n)
ja/nein - Das Komplement jeder entscheidbaren Menge ist aufzählbar
ja/nein - ?
ja/nein - ?

Ausserdem gab es noch eine Aufgabe, bei der eine kontextfreie Grammatik gegeben war und man eine Menge Na bestimmen sollte. Hierbei handelte es sich um die Umkehrung der Aufgabe 11.1.ii, sodass die Allgemeine Regel in logischer Notation gegeben war, und man sie auf die Grammatik anwenden sollte. M0 war nicht vorgegeben, das sollte man sich sinnvoll wählen.

btw: Änder mal die Überschrift bei Teil 2. Das war der Automaten/Sprachtheorie Teil und nicht der Prädikatenlogische Teil ;)


mehr fällt mir grad nicht ein
Gruß