Fachschaft Informatik - Benutzerbeiträge [de]

Gedächtnisprotokoll FGI109-1

2009-07-27T18:46:49Z

85.176.95.40: /* 5. */

== Teil 1: Logik ==

== Aufgabe1 ==

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

== Aufgabe2 ==
Es waren verschiedene Formel gegeben und man sollte ein kreuz bei zutreffenden Antworten machen. (Kontingent, (allgemein)gültig, unerfüllbar)
In der Art: Seien F und G Formeln.
G ist Tautologie und F=>G gültig. Was kann F dann sein: gültig, kontingent, unerfüllbar?
und das für mehrere verschiedene formeln/Bedingungen! Waren 6 Formeln

== Aufgabe 3 ==
Definiere Hornklausel, Hornformel, Literal und Implikationsschreibweise.

== Aufgabe 4 ==
Noch eine aus dem ersten Teil zum Markierungsalgorithmus:
a) Welche Eingabe nimmt der Algorithmus, welches Resultat liefert er?
Gib Eingabe und Ausgabe an und beschreibe den Algorithmus möglichst genau!
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.

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

== Aufgabe 6: Unifikation ==
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
P - Aussagensymbol
a) P( irgendwas ) P ( irgendas ) P (Irgendwas)
b) Blub
c) P ( h ( x, f(w) ), x), P( f(y), h(z), y)
(So etwa)

== Aufgabe 7(?) ==
Ist die Menge 2^M abzählbar, wenn
  O M abzählbar ist
  O M aufzählbar ist
  O M entscheidbar ist

waren insgesamt 7 aufgaben im ersten teil, die andere weiß ich grad nicht..

== Teil 2: Formale Sprachen, Automaten und Komplexität ==
== 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

c) Konstruiere einen DFA (mit allen Angaben) zur Sprache L = {w aus {a,b}* | Es gibt eine natürliche Zahl n für die gilt: |w|a = 2n}

== 2. ==
Kellerautomat gegeben

a) Gib alle Wörter bis zur Länge 4 an, die mit Endzustand akzeptiert werden.

b) Gib alle Wörter bis zur Länge 4 an, die mit leerem Keller akzeptiert werden.

c) Gib ein Wort w aus L mit |w| >= 2 inkl. der Konfiguration an, das mit leerem Keller akzeptiert wird.

d) Gib ein Wort w aus L mit |w| >= 2 inkl. der Konfiguration an, das mit Endzustand akzeptiert wird

== 3. Aussagen über formale Sprache, PSpace, NSpace, Entscheidbarkeit ==

b) PSpace ist Teilmenge von Cs ist Teilmenge von NSpace. Ja oder nein?

== 4. ==
a) Definiere Entscheidbarkeit
b) Wieder Aussagen und Fragen

== 5. ==
Deterministischer Automat gegeben - erstelle Potenzautomat
(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. ==
Wie würdest du vorgehen, wenn du testen willst, ob ein Problem NP-vollständig ist?

[[Kategorie:Gedaechtnisprotokoll|FGI1]]

Gedächtnisprotokoll FGI109-1

2009-07-27T18:46:02Z

85.176.95.40: /* 2. */

== Teil 1: Logik ==

== Aufgabe1 ==

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

== Aufgabe2 ==
Es waren verschiedene Formel gegeben und man sollte ein kreuz bei zutreffenden Antworten machen. (Kontingent, (allgemein)gültig, unerfüllbar)
In der Art: Seien F und G Formeln.
G ist Tautologie und F=>G gültig. Was kann F dann sein: gültig, kontingent, unerfüllbar?
und das für mehrere verschiedene formeln/Bedingungen! Waren 6 Formeln

== Aufgabe 3 ==
Definiere Hornklausel, Hornformel, Literal und Implikationsschreibweise.

== Aufgabe 4 ==
Noch eine aus dem ersten Teil zum Markierungsalgorithmus:
a) Welche Eingabe nimmt der Algorithmus, welches Resultat liefert er?
Gib Eingabe und Ausgabe an und beschreibe den Algorithmus möglichst genau!
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.

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

== Aufgabe 6: Unifikation ==
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
P - Aussagensymbol
a) P( irgendwas ) P ( irgendas ) P (Irgendwas)
b) Blub
c) P ( h ( x, f(w) ), x), P( f(y), h(z), y)
(So etwa)

== Aufgabe 7(?) ==
Ist die Menge 2^M abzählbar, wenn
  O M abzählbar ist
  O M aufzählbar ist
  O M entscheidbar ist

waren insgesamt 7 aufgaben im ersten teil, die andere weiß ich grad nicht..

== Teil 2: Formale Sprachen, Automaten und Komplexität ==
== 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

c) Konstruiere einen DFA (mit allen Angaben) zur Sprache L = {w aus {a,b}* | Es gibt eine natürliche Zahl n für die gilt: |w|a = 2n}

== 2. ==
Kellerautomat gegeben

a) Gib alle Wörter bis zur Länge 4 an, die mit Endzustand akzeptiert werden.

b) Gib alle Wörter bis zur Länge 4 an, die mit leerem Keller akzeptiert werden.

c) Gib ein Wort w aus L mit |w| >= 2 inkl. der Konfiguration an, das mit leerem Keller akzeptiert wird.

d) Gib ein Wort w aus L mit |w| >= 2 inkl. der Konfiguration an, das mit Endzustand akzeptiert wird

== 3. Aussagen über formale Sprache, PSpace, NSpace, Entscheidbarkeit ==

b) PSpace ist Teilmenge von Cs ist Teilmenge von NSpace. Ja oder nein?

== 4. ==
a) Definiere Entscheidbarkeit
b) Wieder Aussagen und Fragen

== 5. ==
Deterministischer Automat gegeben - erstelle nichtdeterministischen (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. ==
Wie würdest du vorgehen, wenn du testen willst, ob ein Problem NP-vollständig ist?

[[Kategorie:Gedaechtnisprotokoll|FGI1]]

Gedächtnisprotokoll FGI109-1

2009-07-27T18:44:07Z

85.176.95.40: /* 2. */

== Teil 1: Logik ==

== Aufgabe1 ==

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

== Aufgabe2 ==
Es waren verschiedene Formel gegeben und man sollte ein kreuz bei zutreffenden Antworten machen. (Kontingent, (allgemein)gültig, unerfüllbar)
In der Art: Seien F und G Formeln.
G ist Tautologie und F=>G gültig. Was kann F dann sein: gültig, kontingent, unerfüllbar?
und das für mehrere verschiedene formeln/Bedingungen! Waren 6 Formeln

== Aufgabe 3 ==
Definiere Hornklausel, Hornformel, Literal und Implikationsschreibweise.

== Aufgabe 4 ==
Noch eine aus dem ersten Teil zum Markierungsalgorithmus:
a) Welche Eingabe nimmt der Algorithmus, welches Resultat liefert er?
Gib Eingabe und Ausgabe an und beschreibe den Algorithmus möglichst genau!
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.

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

== Aufgabe 6: Unifikation ==
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
P - Aussagensymbol
a) P( irgendwas ) P ( irgendas ) P (Irgendwas)
b) Blub
c) P ( h ( x, f(w) ), x), P( f(y), h(z), y)
(So etwa)

== Aufgabe 7(?) ==
Ist die Menge 2^M abzählbar, wenn
  O M abzählbar ist
  O M aufzählbar ist
  O M entscheidbar ist

waren insgesamt 7 aufgaben im ersten teil, die andere weiß ich grad nicht..

== Teil 2: Formale Sprachen, Automaten und Komplexität ==
== 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

c) Konstruiere einen DFA (mit allen Angaben) zur Sprache L = {w aus {a,b}* | Es gibt eine natürliche Zahl n für die gilt: |w|a = 2n}

== 2. ==
Kellerautomat gegeben

a) Gib alle Wörter bis zur Länge 4 an, die mit Endzustand akzeptiert werden.

b) Gib alle Wörter bis zur Länge 4 an, die mit leerem Keller akzeptiert werden.

c) Gib ein Wort w aus L mit |w| >= 2 inkl. der Konfiguration an, das mit leerem Keller akzeptiert wird.

d) Gib ein Wort w aus L mit |w| >= 2 inkl. der Konfiguration an, das mit Endzustand akzeptiert wird

== 3. == Aussagen über formale Sprache, NPSpace, NSpace, Entscheidbarkeit

== 4. ==
a) Definiere Entscheidbarkeit
b) Wieder Aussagen und Fragen

== 5. ==
Deterministischer Automat gegeben - erstelle nichtdeterministischen (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. ==
Wie würdest du vorgehen, wenn du testen willst, ob ein Problem NP-vollständig ist?

[[Kategorie:Gedaechtnisprotokoll|FGI1]]

Gedächtnisprotokoll FGI109-1

2009-07-27T18:40:57Z

85.176.95.40: /* 1. */

== Teil 1: Logik ==

== Aufgabe1 ==

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

== Aufgabe2 ==
Es waren verschiedene Formel gegeben und man sollte ein kreuz bei zutreffenden Antworten machen. (Kontingent, (allgemein)gültig, unerfüllbar)
In der Art: Seien F und G Formeln.
G ist Tautologie und F=>G gültig. Was kann F dann sein: gültig, kontingent, unerfüllbar?
und das für mehrere verschiedene formeln/Bedingungen! Waren 6 Formeln

== Aufgabe 3 ==
Definiere Hornklausel, Hornformel, Literal und Implikationsschreibweise.

== Aufgabe 4 ==
Noch eine aus dem ersten Teil zum Markierungsalgorithmus:
a) Welche Eingabe nimmt der Algorithmus, welches Resultat liefert er?
Gib Eingabe und Ausgabe an und beschreibe den Algorithmus möglichst genau!
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.

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

== Aufgabe 6: Unifikation ==
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
P - Aussagensymbol
a) P( irgendwas ) P ( irgendas ) P (Irgendwas)
b) Blub
c) P ( h ( x, f(w) ), x), P( f(y), h(z), y)
(So etwa)

== Aufgabe 7(?) ==
Ist die Menge 2^M abzählbar, wenn
  O M abzählbar ist
  O M aufzählbar ist
  O M entscheidbar ist

waren insgesamt 7 aufgaben im ersten teil, die andere weiß ich grad nicht..

== Teil 2: Formale Sprachen, Automaten und Komplexität ==
== 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

c) Konstruiere einen DFA (mit allen Angaben) zur Sprache L = {w aus {a,b}* | Es gibt eine natürliche Zahl n für die gilt: |w|a = 2n}

== 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. ==
Deterministischer Automat gegeben - erstelle nichtdeterministischen (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. ==
Wie würdest du vorgehen, wenn du testen willst, ob ein Problem NP-vollständig ist?

[[Kategorie:Gedaechtnisprotokoll|FGI1]]

Gedächtnisprotokoll FGI109-1

2009-07-27T18:37:06Z

85.176.95.40: /* 1. */

== Teil 1: Logik ==

== Aufgabe1 ==

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

== Aufgabe2 ==
Es waren verschiedene Formel gegeben und man sollte ein kreuz bei zutreffenden Antworten machen. (Kontingent, (allgemein)gültig, unerfüllbar)
In der Art: Seien F und G Formeln.
G ist Tautologie und F=>G gültig. Was kann F dann sein: gültig, kontingent, unerfüllbar?
und das für mehrere verschiedene formeln/Bedingungen! Waren 6 Formeln

== Aufgabe 3 ==
Definiere Hornklausel, Hornformel, Literal und Implikationsschreibweise.

== Aufgabe 4 ==
Noch eine aus dem ersten Teil zum Markierungsalgorithmus:
a) Welche Eingabe nimmt der Algorithmus, welches Resultat liefert er?
Gib Eingabe und Ausgabe an und beschreibe den Algorithmus möglichst genau!
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.

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

== Aufgabe 6: Unifikation ==
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
P - Aussagensymbol
a) P( irgendwas ) P ( irgendas ) P (Irgendwas)
b) Blub
c) P ( h ( x, f(w) ), x), P( f(y), h(z), y)
(So etwa)

== Aufgabe 7(?) ==
Ist die Menge 2^M abzählbar, wenn
  O M abzählbar ist
  O M aufzählbar ist
  O M entscheidbar ist

waren insgesamt 7 aufgaben im ersten teil, die andere weiß ich grad nicht..

== Teil 2: Formale Sprachen, Automaten und Komplexität ==
== 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. ==
Deterministischer Automat gegeben - erstelle nichtdeterministischen (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. ==
Wie würdest du vorgehen, wenn du testen willst, ob ein Problem NP-vollständig ist?

[[Kategorie:Gedaechtnisprotokoll|FGI1]]

Gedächtnisprotokoll FGI109-1

2009-07-27T18:34:36Z

85.176.95.40: /* Aufgabe2 */

== Teil 1: Logik ==

== Aufgabe1 ==

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

== Aufgabe2 ==
Es waren verschiedene Formel gegeben und man sollte ein kreuz bei zutreffenden Antworten machen. (Kontingent, (allgemein)gültig, unerfüllbar)
In der Art: Seien F und G Formeln.
G ist Tautologie und F=>G gültig. Was kann F dann sein: gültig, kontingent, unerfüllbar?
und das für mehrere verschiedene formeln/Bedingungen! Waren 6 Formeln

== Aufgabe 3 ==
Definiere Hornklausel, Hornformel, Literal und Implikationsschreibweise.

== Aufgabe 4 ==
Noch eine aus dem ersten Teil zum Markierungsalgorithmus:
a) Welche Eingabe nimmt der Algorithmus, welches Resultat liefert er?
Gib Eingabe und Ausgabe an und beschreibe den Algorithmus möglichst genau!
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.

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

== Aufgabe 6: Unifikation ==
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
P - Aussagensymbol
a) P( irgendwas ) P ( irgendas ) P (Irgendwas)
b) Blub
c) P ( h ( x, f(w) ), x), P( f(y), h(z), y)
(So etwa)

== Aufgabe 7(?) ==
Ist die Menge 2^M abzählbar, wenn
  O M abzählbar ist
  O M aufzählbar ist
  O M entscheidbar ist

waren insgesamt 7 aufgaben im ersten teil, die andere weiß ich grad nicht..

== Teil 2: Formale Sprachen, Automaten und Komplexität ==
== 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. ==
Deterministischer Automat gegeben - erstelle nichtdeterministischen (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. ==
Wie würdest du vorgehen, wenn du testen willst, ob ein Problem NP-vollständig ist?

[[Kategorie:Gedaechtnisprotokoll|FGI1]]

Gedächtnisprotokoll FGI109-1

2009-07-27T18:32:37Z

85.176.95.40:

== Teil 1: Logik ==

== Aufgabe1 ==

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

== Aufgabe2 ==
Es waren verschiedene Formel gegeben und man sollte ein kreuz bei zutreffenden Antworten machen. (Kontingent, (allgemein)gültig, unerfüllbar)
In der Art: Seien F und G Formeln.
F ist Tautologie, G unerfüllbar, Ist dann F=>G gültig, kontingent, unerfüllbar?
und das für mehrere verschiedene formeln/Bedingungen! Waren 6 Formeln

== Aufgabe 3 ==
Definiere Hornklausel, Hornformel, Literal und Implikationsschreibweise.

== Aufgabe 4 ==
Noch eine aus dem ersten Teil zum Markierungsalgorithmus:
a) Welche Eingabe nimmt der Algorithmus, welches Resultat liefert er?
Gib Eingabe und Ausgabe an und beschreibe den Algorithmus möglichst genau!
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.

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

== Aufgabe 6: Unifikation ==
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
P - Aussagensymbol
a) P( irgendwas ) P ( irgendas ) P (Irgendwas)
b) Blub
c) P ( h ( x, f(w) ), x), P( f(y), h(z), y)
(So etwa)

== Aufgabe 7(?) ==
Ist die Menge 2^M abzählbar, wenn
  O M abzählbar ist
  O M aufzählbar ist
  O M entscheidbar ist

waren insgesamt 7 aufgaben im ersten teil, die andere weiß ich grad nicht..

== Teil 2: Formale Sprachen, Automaten und Komplexität ==
== 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. ==
Deterministischer Automat gegeben - erstelle nichtdeterministischen (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. ==
Wie würdest du vorgehen, wenn du testen willst, ob ein Problem NP-vollständig ist?

[[Kategorie:Gedaechtnisprotokoll|FGI1]]