FB18 - Das Forum für Informatik

fb18.de / Bachelorstudieng / PM Formale Informatik

FGI - 1. Klausur 22.07.2008 - Gedächtnisprotokoll

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 :)

RE: FGI - 1. Klausur 22.07.2008 - Gedächtnisprotokoll 2008-07-22 17:28
rothose86
Dein 4. bei Logik war die letzte Aufgabe des Teils.
Es war gegeben F=( \forall P(x) or \forall Q(x) ) und G= \forall (P(x) or Q(x))
Man sollte durch Angabe einer Struktur zeigen, dass die nicht äquivalent sind.
;)

RE: FGI - 1. Klausur 22.07.2008 - Gedächtnisprotokoll 2008-07-22 17:30
rothose86
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.

Stand das da sicher?
Meine mich zu errinnern dass Herr Jantzen mal in der Vorlesung meinte man braucht nur 45 % zum Bestehen. Aber da hat er auch von 150 Punkten gesprochen, wenn ich mich nicht irre.

RE: FGI - 1. Klausur 22.07.2008 - Gedächtnisprotokoll 2008-07-22 18:33
Anonymer User
So wurde es von dem Typen, der vorne stand, erzählt.
Und jeder Teil gab 50 Punkte - ganz vergessen.

RE: FGI - 1. Klausur 22.07.2008 - Gedächtnisprotokoll 2008-07-22 19:17
Julian F.
Irgendwo im 2. Teil gab's noch: "Wie lässt sich die Frage, ob ein gegebener Graph G = (V, E) einen Eulerschen Kreis besitzt, als formale Sprache ausdrücken?" (Sinngemäß… sofern ich den Sinn richtig verstanden habe)

Bei der Aufgabe wusste ich überhaupt keinen Anfang. Hat da jemand was geschafft?

RE: FGI - 1. Klausur 22.07.2008 - Gedächtnisprotokoll 2008-07-22 20:49
Anonymer User
Stand das da sicher?
Meine mich zu errinnern dass Herr Jantzen mal in der Vorlesung meinte man braucht nur 45 % zum Bestehen. Aber da hat er auch von 150 Punkten gesprochen, wenn ich mich nicht irre.

Ich glaube, das bezog sich damals auf die Uebungsaufgaben, da wuerden die 150 Punkte dann jedenfalls auch genau hinkommen.

RE: FGI - 1. Klausur 22.07.2008 - Gedächtnisprotokoll 2008-07-22 22:52
theorinix
Meine mich zu errinnern dass Herr Jantzen mal in der Vorlesung meinte man braucht nur 45 % zum Bestehen. Aber da hat er auch von 150 Punkten gesprochen, wenn ich mich nicht irre.

Jupp, das bezog sich auf den Übungsschein bzw. die Zulassungsanforderungen,
um die Klausur (im ersten Versuch) mitzuschreiben zu dürfen!

Bei Klausuren war das stets anders geregelt, 50% (manchmal auch 49%?) mit 15 Pkt. in jedem Teil.

RE: FGI - 1. Klausur 22.07.2008 - Gedächtnisprotokoll 2008-07-23 00:13
Anonymer User
boah also so hammer hammer schwer war die Klausur vielleicht nicht, aber obwohl ich die Vorlesungen, alle Übungen und das Paniktutorium besucht habe, hatte ich Schwierigkeiten. Naja jetzt kann man nur noch beten und hoffen, dass es eine 4.0000000 wird :(

RE: FGI - 1. Klausur 22.07.2008 - Gedächtnisprotokoll 2008-07-23 06:18
Anonymer User
So schwer war die Klausur dieses Jahr wohl nicht, wenn so wenige rumheulen. Ich denke, die Profs haben das endlich eingesehen.

RE: FGI - 1. Klausur 22.07.2008 - Gedächtnisprotokoll 2008-07-23 07:17
Anonymer User
Nein sie war wirklich machbar, aber eine Aufgabe weniger und die Zeit hätte auch gut gereicht.
Klar musste man sehr viel können, da auch sehr viel abgefragt wurde, aber die Chance immerhin zu bestehen dürfte weitaus größer gewesen sein als letztes Jahr. ;)

RE: FGI - 1. Klausur 22.07.2008 - Gedächtnisprotokoll 2008-07-23 10:17
Anonymer User
Ich fand die Klausur sehr leicht. Da durchzufallen muss schon sehr große Kunst sein..

RE: FGI - 1. Klausur 22.07.2008 - Gedächtnisprotokoll 2008-07-23 12:06
TieKei
Ich fand die Klausur sehr leicht. Da durchzufallen muss schon sehr große Kunst sein..

[img]http://www.look54.de/html/img/produkte/400070va.jpg[/img]

RE: FGI - 1. Klausur 22.07.2008 - Gedächtnisprotokoll 2008-07-23 21:12
Anonymer User
übertreibt mal nicht!!! So einfach war die Klausur nicht!

RE: FGI - 1. Klausur 22.07.2008 - Gedächtnisprotokoll 2008-07-23 21:54
Julian F.
Mein Standpunkt zum Schwierigkeitsgrad der Klausur: Sie war nicht zu leicht und nicht zu schwer. Bestehen sollte (mit etwas Vorbereitung) eigentlich drin sein - zumindest scheint mir das nicht schwerer zu erreichen als in anderen, vergleichbaren Fächern.

Über die Sinnhaftigkeit detailgenauer Wiedergabe von formalen Definitionen als Aufgabe einer Klausur mögen die Meinungen auseinander gehen, aber auch das hat sich ja in solchen Grenzen gehalten, dass ich mich darüber nicht beschweren möchte. Wer eine Bestnote will, muss(te) halt ein paar Definitionen auswendig gelernt haben.

RE: FGI - 1. Klausur 22.07.2008 - Gedächtnisprotokoll 2008-07-23 22:16
Fred
Wer eine Bestnote will, muss(te) halt ein paar Definitionen auswendig gelernt haben.
Ideal ist es, Definitionen nicht nur auswendig zu lernen, sondern ihren Sinn zu verstehen und wiedergeben zu können. Vor allem in mündlichen Prüfungen zahlt sich das aus.

RE: FGI - 1. Klausur 22.07.2008 - Gedächtnisprotokoll 2008-07-24 00:15
Julian F.
Ideal ist es, Definitionen nicht nur auswendig zu lernen, sondern ihren Sinn zu verstehen und wiedergeben zu können. Vor allem in mündlichen Prüfungen zahlt sich das aus.
Richtig. Vermutlich meinen wir sogar das selbe. Ich wollte nicht davon gesprochen haben, Definitionen nach Wortlaut auswendig zu lernen (was auch in der Klausur nicht gefordert war, evtl. aber an den entsprechenden Stellen Denkarbeit gespart hätte), sondern davon, Definitionen von Dingen wie Erfüllbarkeit, Entscheidbarkeit, BPF usw. vollständig und (formal) korrekt ([25]) wiedergeben zu können, was ja gerade im Bereich der Theoretischen Informatik einen gewissen Wert hat. Bei einigen der komplexeren Definitionen hat das allerdings schon einen Hauch des Auswendiglernens der Komponenten der Definition - zumindest ging es mir so.

RE: FGI - 1. Klausur 22.07.2008 - Gedächtnisprotokoll 2008-07-26 15:49
Anonymer User
Wisst ihr noch mehr über die Aufgaben?

RE: FGI - 1. Klausur 22.07.2008 - Gedächtnisprotokoll 2008-07-29 12:24
Julian F.
Die Ergebnisse stehen in STiNE… Schnitt ist 3,76, durchaus einige Noten auch im oberen Bewertungsbereich.

RE: FGI - 1. Klausur 22.07.2008 - Gedächtnisprotokoll 2008-07-29 13:29
Anonymer User
Könnte vielleicht mal jmd der diese Klausur zum ersten mal geschrieben hat die Statistik aus Stine hier posten? Ich kann nur die Statistik für die Leute aus dem Jahrgang 06 sehen!

RE: FGI - 1. Klausur 22.07.2008 - Gedächtnisprotokoll 2008-07-29 14:30
payne
Noten 1,0 1,3 1,7 2,0 2,3 2,7 3,0 3,3 3,7 4,0 5,0
Anzahl 3 3 7 5 2 2 4 8 7 9 37
Durchschnitt: 3,73
Vorliegende Ergebnisse: 87
Fehlend (ohne Grund): 22

RE: FGI - 1. Klausur 22.07.2008 - Gedächtnisprotokoll 2008-07-29 19:37
Anonymer User
Hi!

Weiß jemand, ob die Ergebnisse außer in Stine noch irgendwo online vorliegen.
Habe keine Lust ganz nach Stellingen zu gurken und bin Diplomer, also Stine-unabhängig.

RE: FGI - 1. Klausur 22.07.2008 - Gedächtnisprotokoll 2008-07-29 20:10
Anonymer User
yeah 1.0
logger vom hogger.. 37 durchgefallen lol .. peinlich

RE: FGI - 1. Klausur 22.07.2008 - Gedächtnisprotokoll 2008-07-29 21:07
Anonymer User
yeah 1.0
logger vom hogger.. 37 durchgefallen lol .. peinlich

oh man du sucker…..einfach mal die klappe halten…

weiß jemand ob es eine klausureinsicht geben wird, oder bei wem man sich da melden kann?

RE: FGI - 1. Klausur 22.07.2008 - Gedächtnisprotokoll 2008-07-29 21:23
GroßerSchöpfer
weiß jemand ob es eine klausureinsicht geben wird, oder bei wem man sich da melden kann?

auch hier gilt:

§22

Einsicht in die Prüfungsakten

Bis zu einem Jahr nach Abschluss der einzelnen Modulprüfungen wird vom Vorsitzenden des Prüfungsausschusses auf schriftlichen Antrag des Prüflings in angemessener Frist Einsicht in seine schriftlichen Prüfungsarbeiten, die darauf bezogenen Gutachten und die Prüfungsprotokolle gewährt, soweit diese nicht bereits ausgehändigt worden sind.

Und dazu zum Beispiel folgendes Formular verwenden: http://www.informatik.uni-hamburg.de/Fachschaft/2008/klausureinsicht.pdf

RE: FGI - 1. Klausur 22.07.2008 - Gedächtnisprotokoll 2008-10-03 23:25
TieKei
Dein 4. bei Logik war die letzte Aufgabe des Teils.
Es war gegeben F=( \forall P(x) or \forall Q(x) ) und G=  \forall (P(x) or Q(x))
Man sollte durch Angabe einer Struktur zeigen, dass die nicht äquivalent sind.
;)

So und genau das kann ich nicht zeigen, gibt mir jemand mal nen Tipp?
Ich finds rein logisch sofort einleuchtend, aber formell weiß ich nicht wie.

RE: FGI - 1. Klausur 22.07.2008 - Gedächtnisprotokoll 2008-10-03 23:32
UncleOwen
Nimm als Universum die natürlichen Zahlen, I(P) und I(Q) sind die geraden bzw. ungeraden natürlichen Zahlen