Bearbeiten von „Gedächtnisprotokoll FGI109-1“
Zur Navigation springen
Zur Suche springen
Warnung: Du bist nicht angemeldet. Deine IP-Adresse wird bei Bearbeitungen öffentlich sichtbar. Melde dich an oder erstelle ein Benutzerkonto, damit Bearbeitungen deinem Benutzernamen zugeordnet werden.
Die Bearbeitung kann rückgängig gemacht werden. Bitte prüfe den Vergleich unten, um sicherzustellen, dass du dies tun möchtest, und veröffentliche dann unten deine Änderungen, um die Bearbeitung rückgängig zu machen.
Aktuelle Version | Dein Text | ||
Zeile 2: | Zeile 2: | ||
== Aufgabe1 == | == Aufgabe1 == | ||
1. Erläutere folgende Zeichen (Zeichen für Implikation, Ableitung mittels Modus Ponens und Folgerbarkeit war gegeben). | 1. Erläutere folgende Zeichen (Zeichen für Implikation, Ableitung mittels Modus Ponens und Folgerbarkeit war gegeben). | ||
Erläutere den Zusammenhang zwischen folgenden zeichen: | Erläutere den Zusammenhang zwischen folgenden zeichen: | ||
a) Folgerbarkeit - Implikation | a) Folgerbarkeit - Implikation | ||
b) Implikation - Modus Ponens | b) Implikation - Modus Ponens | ||
c) Modus Ponens - Folgerbarkeit | c) Modus Ponens - Folgerbarkeit | ||
Zeile 25: | Zeile 22: | ||
== Aufgabe 4 == | == Aufgabe 4 == | ||
Noch eine aus dem ersten Teil zum Markierungsalgorithmus: | Noch eine aus dem ersten Teil zum Markierungsalgorithmus: | ||
a) Welche Eingabe nimmt der Algorithmus, welches Resultat liefert er? | a) Welche Eingabe nimmt der Algorithmus, welches Resultat liefert er? | ||
Gib Eingabe und Ausgabe an und beschreibe den Algorithmus möglichst genau! | Gib Eingabe und Ausgabe an und beschreibe den Algorithmus möglichst genau! | ||
b) Begründen Sie, warum der Algorithmus immer terminiert. | b) Begründen Sie, warum der Algorithmus immer terminiert. | ||
c) Begründen Sie, dass der Algorithmus "unerfüllbar" nur für unerfüllbare Formeln liefert. | c) Begründen Sie, dass der Algorithmus "unerfüllbar" nur für unerfüllbare Formeln liefert. | ||
== Aufgabe 5: Resolution == | == Aufgabe 5: Resolution == | ||
Folgerbarkeit einer Formel F von einer Formelmenge M zeigen (stand afaik zeigen da, d.h. es war klar, dass sie Folgerbar war..) | Folgerbarkeit einer Formel F von einer Formelmenge M zeigen (stand afaik zeigen da, d.h. es war klar, dass sie Folgerbar war..) | ||
== Aufgabe 6: Unifikation == | == Aufgabe 6: Unifikation == | ||
3 Prädikatenlogische Formelmengen waren gegeben und man sollte begründen/wiederlegen warum man sie (nicht) unifizieren kann | 3 Prädikatenlogische Formelmengen waren gegeben und man sollte begründen/wiederlegen warum man sie (nicht) unifizieren kann | ||
u, v, w, x, y, z - Variablen | u, v, w, x, y, z - Variablen | ||
P - Aussagensymbol | P - Aussagensymbol | ||
a) P( irgendwas ) P ( irgendas ) P (Irgendwas) | |||
a) P( irgendwas ) P ( irgendas ) P (Irgendwas) | |||
b) Blub | b) Blub | ||
c) P ( h ( x, f(w) ), x), P( f(y), h(z), y) | c) P ( h ( x, f(w) ), x), P( f(y), h(z), y) | ||
(So etwa) | (So etwa) | ||
== Aufgabe 7(?) | == Aufgabe 7(?) == | ||
Ist die Menge 2^ | Ist die Menge 2^M abzählbar, wenn | ||
O M abzählbar ist | O M abzählbar ist | ||
O M aufzählbar ist | O M aufzählbar ist | ||
O M entscheidbar ist | |||
O M | |||
waren insgesamt 7 aufgaben im ersten teil, die andere weiß ich grad nicht.. | waren insgesamt 7 aufgaben im ersten teil, die andere weiß ich grad nicht.. | ||
Zeile 67: | Zeile 50: | ||
== 1. == | == 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! | 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 | a) Alle Wörter, in denen kein a vor einem b steht | ||
Zeile 77: | Zeile 59: | ||
== 2. == | == 2. == | ||
Kellerautomat gegeben | Kellerautomat gegeben | ||
a) Gib alle Wörter bis zur Länge 4 an, die mit Endzustand akzeptiert werden. | a) Gib alle Wörter bis zur Länge 4 an, die mit Endzustand akzeptiert werden. | ||
Zeile 88: | Zeile 69: | ||
== 3. Aussagen über formale Sprache, PSpace, NSpace, Entscheidbarkeit == | == 3. Aussagen über formale Sprache, PSpace, NSpace, Entscheidbarkeit == | ||
b) PSpace ist Teilmenge von Cs ist Teilmenge von NSpace. Ja oder nein? | |||
== 4. == | == 4. == | ||
a) Definiere Entscheidbarkeit | a) Definiere Entscheidbarkeit | ||
b) Wieder Aussagen und Fragen | b) Wieder Aussagen und Fragen | ||
== 5. == | == 5. == | ||
Deterministischer Automat gegeben - erstelle Potenzautomat | Deterministischer Automat gegeben - erstelle Potenzautomat | ||
(Zustände q0 und q1, q1 Endzustand, q0 Anfangszustand, | (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..) | a-Pfeil von q0 nach q1 und von q0 nach q0, b-Pfeil von q1 nach q0, das wars glaub ich..) | ||
== 6. == | == 6. == | ||
Wie würdest du vorgehen, wenn du testen willst, ob ein Problem NP-vollständig ist? | Wie würdest du vorgehen, wenn du testen willst, ob ein Problem NP-vollständig ist? | ||
[[Kategorie:Gedaechtnisprotokoll|FGI1]] | [[Kategorie:Gedaechtnisprotokoll|FGI1]] |