FGI - 1. Klausur 22.07.2008 - Gedächtnisprotokoll
2008-07-22 17:10
Anonymer User
Die Reihenfolge stimmt nicht. Vollständig ist es sicher auch nicht.
Insgesamt gab es 100 Punkte. 50 Voraussetzung zum Bestehen inkl. 15 in jedem der beiden Teile.
I. Logik
1. Seien F und G beliebige Formeln, was ist F (gültig, unerfüllbar, kontingent - mehreres möglich)?
Verschiedene Formeln wie z.B. F v G gültig waren angegeben.
2. Gegeben war die rekursive Definition der Tiefe (siehe Skript). Dann sollte man Grad rekursiv definieren (wurde aber nicht als Grad bezeichnet, sondern nur umschrieben!). Anschließend war zu zeigen, dass Tiefe <= Grad per struktureller Induktion.
3. Resolution
i) Resolutionsableitung
ii) Irgendwas streichen sollte man und bei iii) Begründung dafür angeben, ansonsten Resolutionsableitung
iv) Erläutern, welche Resolutionsmethode man für ii) wählen würde, angegeben waren zur normalen noch P- und N-Resolution
v) Resolutionsbeweis zu ii) (?)
4.PL
Man zeige über die Struktur, dass zwei PL-Formeln F und G nicht äquivalent sind.
9 Punkte (!)
5. Prädikatenlogik
a) Was ist bereinigte Pränexform (BPF)?
b) Was ist Skolemisierung?
c) Bringe Formel F in BPF
d) Skolemisiere die Formel von c)
6. Inferenzregeln
a) Was ist die Definition von korrekt bei Inferenzregeln?
b) Zeige, dass die zwei Inferenzregeln korrekt sind.
7. Gabs glaub ich auch noch
—————————
II. Formale Sprachen, Berechenbarkeit, Automaten
1. rationale Ausdrücke
a)b) Man gebe rationale Ausdrücke zu einer bestimmten Sprache mit vorgegebenen Alphabet an. Ebenfalls ein Wort, welches nicht in dieser Sprache enthalten ist.
c) DFA (!) Komplette Definition + Zustandsdiagramm für Sprache {a,b}*{b}+
2. Potenzautomat aus vorgegebenem Automaten bilden
3. x <<< y (Ich glaub da steht was im Skript zu. Wurde jedenfalls in der Klausur definiert)
Im Endeffekt gings darum, eine Liste neu anzuordnen.
(4,2,3) (4,3,2) (2,9,2) (2,6,6) (4,6,2) (Die Zahlen stimmen nicht unbedingt)
Dabei war x <<< y, wenn x1+x2+x3 < y1+y2+y3 oder x1+x2+x3=y1+y2+y3 und weitere Bedingungen.
Per Anhang gabs dann nochmal die Erklärungen zu lexikographische und lexikalische Ordnung.
Auch hier sollte sortiert werden.
Dazwischen gabs noch eine kleine Aufgabe, wo man im Endeffekt nur a's, b's und c's von z.B. "abb" zählen musste und als Tupel (1,2,0) für (a,b,c) schreiben sollte.
11 Punkte insgesamt
4. Das Pumpinglemma war in Form einer aufgebröselten prädikatenlogischen Formel gegeben, diese sollte man für 3 Punkte richtig zusammensetzen.
5. Kontextfreie Grammatik
a^mb^(2n)c^(m+n) sollte erzeugt werden. Z.b. so: S -> aBc | aSc, B -> bbBc | bbc
vielleicht musste man auch noch S -> epsilon reinbringen, aber keine Ahnung
6. 9 Fragen
Dies waren nicht unbedingt leichte Verständnisfragen, zu Mengen, Entscheidbarkeit, Abgeschlossenheit der Mengen usw. (Ja/Nein Antworten) 1 Punkt pro Frage
7.
a) Entscheidbarkeit von Formalen Sprachen oder so sollte man erklären. 2 Punkte
b) Man beschreibe eine formale Sprache, die den Eulerschen Kreis (siehe DM - ungerichteter Graph, jede Kante wird genau einmal gegangen) erklärt. 2 Punkte
c) NP-schwer. Was muss man tun, um NP-vollständig zu erhalten?
So, mehr fällt mir gerade nicht ein, aber hab bestimmt was vergessen :)
Insgesamt gab es 100 Punkte. 50 Voraussetzung zum Bestehen inkl. 15 in jedem der beiden Teile.
I. Logik
1. Seien F und G beliebige Formeln, was ist F (gültig, unerfüllbar, kontingent - mehreres möglich)?
Verschiedene Formeln wie z.B. F v G gültig waren angegeben.
2. Gegeben war die rekursive Definition der Tiefe (siehe Skript). Dann sollte man Grad rekursiv definieren (wurde aber nicht als Grad bezeichnet, sondern nur umschrieben!). Anschließend war zu zeigen, dass Tiefe <= Grad per struktureller Induktion.
3. Resolution
i) Resolutionsableitung
ii) Irgendwas streichen sollte man und bei iii) Begründung dafür angeben, ansonsten Resolutionsableitung
iv) Erläutern, welche Resolutionsmethode man für ii) wählen würde, angegeben waren zur normalen noch P- und N-Resolution
v) Resolutionsbeweis zu ii) (?)
4.PL
Man zeige über die Struktur, dass zwei PL-Formeln F und G nicht äquivalent sind.
9 Punkte (!)
5. Prädikatenlogik
a) Was ist bereinigte Pränexform (BPF)?
b) Was ist Skolemisierung?
c) Bringe Formel F in BPF
d) Skolemisiere die Formel von c)
6. Inferenzregeln
a) Was ist die Definition von korrekt bei Inferenzregeln?
b) Zeige, dass die zwei Inferenzregeln korrekt sind.
7. Gabs glaub ich auch noch
—————————
II. Formale Sprachen, Berechenbarkeit, Automaten
1. rationale Ausdrücke
a)b) Man gebe rationale Ausdrücke zu einer bestimmten Sprache mit vorgegebenen Alphabet an. Ebenfalls ein Wort, welches nicht in dieser Sprache enthalten ist.
c) DFA (!) Komplette Definition + Zustandsdiagramm für Sprache {a,b}*{b}+
2. Potenzautomat aus vorgegebenem Automaten bilden
3. x <<< y (Ich glaub da steht was im Skript zu. Wurde jedenfalls in der Klausur definiert)
Im Endeffekt gings darum, eine Liste neu anzuordnen.
(4,2,3) (4,3,2) (2,9,2) (2,6,6) (4,6,2) (Die Zahlen stimmen nicht unbedingt)
Dabei war x <<< y, wenn x1+x2+x3 < y1+y2+y3 oder x1+x2+x3=y1+y2+y3 und weitere Bedingungen.
Per Anhang gabs dann nochmal die Erklärungen zu lexikographische und lexikalische Ordnung.
Auch hier sollte sortiert werden.
Dazwischen gabs noch eine kleine Aufgabe, wo man im Endeffekt nur a's, b's und c's von z.B. "abb" zählen musste und als Tupel (1,2,0) für (a,b,c) schreiben sollte.
11 Punkte insgesamt
4. Das Pumpinglemma war in Form einer aufgebröselten prädikatenlogischen Formel gegeben, diese sollte man für 3 Punkte richtig zusammensetzen.
5. Kontextfreie Grammatik
a^mb^(2n)c^(m+n) sollte erzeugt werden. Z.b. so: S -> aBc | aSc, B -> bbBc | bbc
vielleicht musste man auch noch S -> epsilon reinbringen, aber keine Ahnung
6. 9 Fragen
Dies waren nicht unbedingt leichte Verständnisfragen, zu Mengen, Entscheidbarkeit, Abgeschlossenheit der Mengen usw. (Ja/Nein Antworten) 1 Punkt pro Frage
7.
a) Entscheidbarkeit von Formalen Sprachen oder so sollte man erklären. 2 Punkte
b) Man beschreibe eine formale Sprache, die den Eulerschen Kreis (siehe DM - ungerichteter Graph, jede Kante wird genau einmal gegangen) erklärt. 2 Punkte
c) NP-schwer. Was muss man tun, um NP-vollständig zu erhalten?
So, mehr fällt mir gerade nicht ein, aber hab bestimmt was vergessen :)