FB18 - Das Forum für Informatik

fb18.de / Bachelorstudieng / PM Formale Informatik

FGI-1 KLausur Gedächtnisprotokoll 2 2009

FGI-1 KLausur Gedächtnisprotokoll 2 2009 2009-08-28 12:14
Anonymer User
Hey,
also leicht war die nicht, aber die Themen lagen mir, wie gings euch so? ;)

zum inhalt:

1) Ein paar Aufgaben zum Ankreuzen der Art: Welche Eigenschaften kann F haben wenn…
a) F kontingent und G unerfüllbar F ^ G oder so ;) you know… standard zeuch halt…

2) a)STrukturelle Rekursion von:
Anzahl der Junktoren (j)
Anzahl der Teilformeln in einer Formel (tf)
Anzahl der Aussagenlogischen symbole (as)

b) Strukturelle Induktion:
tf(F) = as(F)+j(F)

3) Markierungsalgorithmus bei 2 Formeln
4) Ein paar Fragen zu Eigenschaften der Resolution in dem Stil:
Wenn bei 3 Klauseln in einer Klauselmenge ein Literal A nur einmal vorkommt und nur positiv, kann man es dann ignorieren? Ja/Nein Mit Begründung (Begründung 1 Punkt, X ein Punkt!)
Mit bisschen nachdenken, glaub cih gut machbar!
5) Resolution bei 2 Aussagenlogischen Formeln und 2 Prädikatenlogsichen Formeln
6)

Automaten:
Das war ziemlich schwer fand ich…
1) einen DFA zeichnen der genausoviele a, wie b akzeptiert, aber es darf kein leere wort entstehen! Sehr gut machbar dnek ich ^^
3) Eine rechtslineare, kontextfreie Grammatik die binäre zahlen darstellt mit nachkommastellen.
Man musste druaf achten, das sowas wie 0100,0 nicht akzeptiert wird (vorne die 0(!)) oder halt 0,0000 nicht…
Also eine fiese Frage:
Glaube 4 b) Man hat einen NFA gegeben mit den Start und Endzuständen und soll daraus schließen, was ein Potenzautomat für STart und Endzustände hat
auch fies: 5) Ein e-FA gegebn, ein endlicher Automat ohne e übergänge soll erstellt werden und die Übergänge als Relation angegeben werden. RElationen find ich gemein :D
naja gegen ende dann einfachere sachen:
6 oder 7 a) Definition von Aufzählbarkeit (4 Punkte, die wenn man das auswendig konnte leicht bekommen konnte)
b) eine DTM wozu man die Sprache als Menge aufschreiben sollte

So, ist ja schon bald vollständig :)

RE: FGI-1 KLausur Gedächtnisprotokoll 2 2009 2009-08-28 22:38
theorinix
[…]
Automaten:
Das war ziemlich schwer fand ich…
1) einen DFA zeichnen der genausoviele a, wie b akzeptiert, aber es darf kein leere wort entstehen! Sehr gut machbar dnek ich ^^
[…]
Also eine fiese Frage:
Glaube 4 b) Man hat einen NFA gegeben mit den Start und Endzuständen und soll daraus schließen, was ein Potenzautomat für STart und Endzustände hat
[…]

zu 1)
Ich glaub' einen DFA für [latex]$\{w\in \{a,b\}^+\mid |w|_a = |w|_b \} $[/latex] gibt es nicht, da diese Menge nicht regulär ist.
War das nicht so, dass kein Wort in der Menge sein sollte, dass ausschließlich aus b's gebildet wurde?
Also so etwas wie die Menge (a+b)^*a(a+b)^*, in der immer mindestens ein a vorkommt…?

zu 4 b):
Die Menge der Anfangszustände des NFA sind der Anfangszustand des Potenzautomaten
und
jede Teilmenge von Q, in der ein Endzustand des NFA enthalten ist, wird ein Endzustand des Potenzautomaten sein.
Inwiefern ist es fies eine solche Definition abzufragen??

RE: FGI-1 KLausur Gedächtnisprotokoll 2 2009 2009-08-28 22:44
Anonymer User
Es war explizit nach einem Startzustand gefragt.
Und naja, man hat ja keine Überführungsfunktion, also weiß man nicht in welchem die 2 Endzustände vorhanden sein werden oder? Also man kann halt einfach die Möglichkeiten hinschreiben. Wenns so gedacht war, wars ja echt nicht grade schwer. Das hatte ich sogar im Kopf *murks*

zu 1) Dann hab ich die Aufgabe falsch verstanden, wenn du recht hast. *nochmalMurks*

RE: FGI-1 KLausur Gedächtnisprotokoll 2 2009 2009-08-29 16:48
Anonymer User
Logikteil war ja nicht so schwer,aber Herr Jantzen hat sehr schwere Fragen gestellt, wenn ich durchfalle ist wegen ihm[26]

RE: FGI-1 KLausur Gedächtnisprotokoll 2 2009 2009-08-29 17:49
Anonymer User
Wieviele brauch man denn im automatenteil?

RE: FGI-1 KLausur Gedächtnisprotokoll 2 2009 2009-08-29 18:48
Anonymer User
  ich fand beide teile schwer, sie war gar nicht ähnlich zur ersten Klausur….sehr schade

RE: FGI-1 KLausur Gedächtnisprotokoll 2 2009 2009-08-29 18:51
Anonymer User
  ich auch…Hoffentlich zieht Herr Jantzen die Bestehensquato nach unten.

RE: FGI-1 KLausur Gedächtnisprotokoll 2 2009 2009-08-29 19:29
Anonymer User
moin, ich fand beide Teile lösbar und nicht zu schwierig.

hier noch ein paar Dinge, die mir noch einfallen, aber keine Garantie auf Vollständigkeit oder Richtigkeit^^.

Logik:
zu 1)
  • [latex]$\neg F$[/latex] kontingent
  • G gültig [latex]$F \models G$[/latex]
  • G kontingent [latex]$F \Rightarrow G$[/latex] gültig
  • und noch weitere…

zu 2)
a) Rekursive Definition für die drei Funktionen j(F),as(F) und tf(F) angeben.
b) Wichtig war, dass man die Bezeichnungen der Schritte richtig hingeschreiben hat.

zu 3) die Formeln waren in KNF angegeben.

Automaten
zu 1)
Man sollte einen endlichen Automaten (also nicht beschränkt auf DFA) zeichnen, der die Sprache [latex]$\{w\in \{a,b\}^+\mid |w|_b \neq 0 \Rightarrow |w|_a \neq 0\} $[/latex] akzeptiert.

zu 2) ich bin mir nicht sicher, ob 0,0000 wirklich ausgeschlossen wurde.

es gab auch noch eine Aufgabe, bei der man die Sprachen [latex]$L_1=\{a,b,c\}$[/latex] und [latex]$L_2=\{c,d,e\}$[/latex] hatte und [latex]$L_1 \circ L_2$[/latex], [latex]$L_1 \times L_2$[/latex] und [latex]$L_1\setminus L_2$[/latex] angeben sollte.
Im zweiten Teil sollte man die Sprache [latex]$\{a,b\}^*\setminus\{a\}^*$[/latex] in Mengenschreibweise angeben.

RE: FGI-1 KLausur Gedächtnisprotokoll 2 2009 2009-08-30 12:55
theorinix
[…]
Automaten
zu 1)
Man sollte einen endlichen Automaten (also nicht beschränkt auf DFA) zeichnen, der die Sprache [latex]$\{w\in \{a,b\}^+\mid |w|_b \neq 0 \Rightarrow |w|_a \neq 0\} $[/latex] akzeptiert.

zu 2) ich bin mir nicht sicher, ob 0,0000 wirklich ausgeschlossen wurde.

es gab auch noch eine Aufgabe, bei der man die Sprachen [latex]$L_1=\{a,b,c\}$[/latex] und [latex]$L_2=\{c,d,e\}$[/latex] hatte und [latex]$L_1 \circ L_2$[/latex], [latex]$L_1 \times L_2$[/latex] und [latex]$L_1\setminus L_2$[/latex] angeben sollte.
Im zweiten Teil sollte man die Sprache [latex]$\{a,b\}^*\setminus\{a\}^*$[/latex] in Mengenschreibweise angeben.

Wenn man 1) ansieht, kommt obige, letzte Sprache mit a und b vertauscht heraus, also [latex]$\{a,b\}^*\setminus\{b\}^*$[/latex] !

RE: FGI-1 KLausur Gedächtnisprotokoll 2 2009 2009-08-31 17:05
Anonymer User
ergebnisse sind da :)
3,3



sauuu schnellll!!!! :)

RE: FGI-1 KLausur Gedächtnisprotokoll 2 2009 2009-09-07 18:13
Anonymer User
die Zahl der 1,0en hat sich ver-1,5-facht ^^

Was mich mal interessieren würde ist, ob die Zahlen beim Durchschnitt zusammengefasst beide Klausuren jetzt beinhalten, oder ob das nur die Ergebnisse vom 2. mal sind…
(Ich habe meine Note vom 1. Versuch behalten)

RE: FGI-1 KLausur Gedächtnisprotokoll 2 2009 2009-09-09 10:40
M. Jantzen
die Zahl der 1,0en hat sich ver-1,5-facht ^^

Was mich mal interessieren würde ist, ob die Zahlen beim Durchschnitt zusammengefasst beide Klausuren jetzt beinhalten, oder ob das nur die Ergebnisse vom 2. mal sind…
(Ich habe meine Note vom 1. Versuch behalten)

eigentlich gewünscht war, dass die verpatzte Klausur vom 27.07 und die Ersatzklausur vom 28.08. nur ein Ergebnis erzielen sollten, welches der "ersten Klausur" zugerechnet wird.
Wie STiNE zur Zeit damit umgeht, weiß ich nicht, am Ende jedenfalls sollte die Noten beider Klausuren (27.07. und 28.08.) zur Durchschnittsbildung herangezogen werden. Mir ist das Rechnungsverfahren wegen seiner Kompliziertheit (nicht Komplexität!) nicht auswndig geläufig. Dazu gab es ab und an Mails und Infos vom STiNE-Beauftragten Michael König.
Die zweite Klausur ist die kommende vom 01.10. und die wird (glaub ich zumindest) offiziell als Wiederholungsklausur tituliert. Die hat sicher ihre eigene Durchschnittsberechnung (zumindest denke ich das).

Matthias Jantzen