https://wiki.mafiasi.de/api.php?action=feedcontributions&feedformat=atom&user=84.144.86.0%2F24Fachschaft Informatik - Benutzerbeiträge [de]2026-10-17T19:56:30ZBenutzerbeiträgeMediaWiki 1.46.2https://wiki.mafiasi.de/index.php?title=Ged%C3%A4chtnisprotokoll_FGI109-1&diff=7829Gedächtnisprotokoll FGI109-12009-07-28T10:01:03Z<p>84.144.86.100: Formatierung angepasst</p>
<hr />
<div>== Teil 1: Logik ==<br />
<br />
<br />
== Aufgabe1 == <br />
<br />
1. Erläutere folgende Zeichen (Zeichen für Implikation, Ableitung mittels Modus Ponens und Folgerbarkeit war gegeben).<br />
Erläutere den Zusammenhang zwischen folgenden zeichen:<br />
<br />
<br />
a) Folgerbarkeit - Implikation<br />
<br />
b) Implikation - Modus Ponens<br />
<br />
c) Modus Ponens - Folgerbarkeit<br />
<br />
== Aufgabe2 ==<br />
Es waren verschiedene Formel gegeben und man sollte ein kreuz bei zutreffenden Antworten machen. (Kontingent, (allgemein)gültig, unerfüllbar)<br />
In der Art: Seien F und G Formeln.<br />
G ist Tautologie und F=>G gültig. Was kann F dann sein: gültig, kontingent, unerfüllbar?<br />
und das für mehrere verschiedene formeln/Bedingungen! Waren 6 Formeln<br />
<br />
== Aufgabe 3 ==<br />
Definiere Hornklausel, Hornformel, Literal und Implikationsschreibweise.<br />
<br />
== Aufgabe 4 ==<br />
Noch eine aus dem ersten Teil zum Markierungsalgorithmus: <br />
<br />
<br />
a) Welche Eingabe nimmt der Algorithmus, welches Resultat liefert er? <br />
Gib Eingabe und Ausgabe an und beschreibe den Algorithmus möglichst genau!<br />
<br />
b) Begründen Sie, warum der Algorithmus immer terminiert.<br />
<br />
c) Begründen Sie, dass der Algorithmus "unerfüllbar" nur für unerfüllbare Formeln liefert.<br />
<br />
== Aufgabe 5: Resolution == <br />
Folgerbarkeit einer Formel F von einer Formelmenge M zeigen (stand afaik zeigen da, d.h. es war klar, dass sie Folgerbar war..)<br />
<br />
== Aufgabe 6: Unifikation ==<br />
3 Prädikatenlogische Formelmengen waren gegeben und man sollte begründen/wiederlegen warum man sie (nicht) unifizieren kann<br />
<br />
u, v, w, x, y, z - Variablen<br />
<br />
P - Aussagensymbol<br />
<br />
<br />
a) P( irgendwas ) P ( irgendas ) P (Irgendwas)<br />
<br />
b) Blub<br />
<br />
c) P ( h ( x, f(w) ), x), P( f(y), h(z), y) <br />
<br />
(So etwa)<br />
<br />
== Aufgabe 7(?) - ne, das muss auch irgendwo im 2. Teil gewesen sein. Jeder Teil hatte 6 Aufgaben. ==<br />
Ist die Menge 2^M immer abzählbar, wenn <br />
<br />
O M abzählbar ist <br />
<br />
O M aufzählbar ist <br />
<br />
O M endlich ist <br />
<br />
waren insgesamt 7 aufgaben im ersten teil, die andere weiß ich grad nicht..<br />
<br />
== Teil 2: Formale Sprachen, Automaten und Komplexität ==<br />
== 1. == <br />
Alphabet gegeben (a, b). Gib jeweils geforderte Sprache sowie alle Wörter der Länge 3 über Alphabet-Stern an, die nicht enthalten sind!<br />
<br />
<br />
a) Alle Wörter, in denen kein a vor einem b steht<br />
<br />
b) Alle Wörter, in denen ab oder ba, aber nicht beide enthalten sind<br />
<br />
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}<br />
<br />
== 2. ==<br />
Kellerautomat gegeben<br />
<br />
<br />
a) Gib alle Wörter bis zur Länge 4 an, die mit Endzustand akzeptiert werden.<br />
<br />
b) Gib alle Wörter bis zur Länge 4 an, die mit leerem Keller akzeptiert werden.<br />
<br />
c) Gib ein Wort w aus L mit |w| >= 2 inkl. der Konfiguration an, das mit leerem Keller akzeptiert wird.<br />
<br />
d) Gib ein Wort w aus L mit |w| >= 2 inkl. der Konfiguration an, das mit Endzustand akzeptiert wird<br />
<br />
== 3. Aussagen über formale Sprache, PSpace, NSpace, Entscheidbarkeit ==<br />
Man konnte jeweils "Ja" oder "Nein" ankreuzen<br />
<br />
<br />
a) Das Komplement jeder entscheidbaren Menge ist aufzählbar.<br />
<br />
b) PSpace ist Teilmenge von Cs ist Teilmenge von NSpace.<br />
<br />
d) Jedes Problem in NP ist entscheidbar.<br />
<br />
== 4. ==<br />
a) Definiere Entscheidbarkeit<br />
<br />
b) Wieder Aussagen und Fragen<br />
<br />
== 5. ==<br />
Deterministischer Automat gegeben - erstelle Potenzautomat<br />
<br />
(Zustände q0 und q1, q1 Endzustand, q0 Anfangszustand, <br />
a-Pfeil von q0 nach q1 und von q0 nach q0, b-Pfeil von q1 nach q0, das wars glaub ich..)<br />
<br />
== 6. == <br />
Wie würdest du vorgehen, wenn du testen willst, ob ein Problem NP-vollständig ist?<br />
<br />
<br />
[[Kategorie:Gedaechtnisprotokoll|FGI1]]</div>84.144.86.100https://wiki.mafiasi.de/index.php?title=Ged%C3%A4chtnisprotokoll_FGI109-1&diff=7828Gedächtnisprotokoll FGI109-12009-07-28T09:55:13Z<p>84.144.86.100: Ja/Nein-Fragen hinzugefügt bzw. editiert</p>
<hr />
<div>== Teil 1: Logik ==<br />
<br />
<br />
== Aufgabe1 == <br />
<br />
1. Erläutere folgende Zeichen (Zeichen für Implikation, Ableitung mittels Modus Ponens und Folgerbarkeit war gegeben).<br />
Erläutere den Zusammenhang zwischen folgenden zeichen:<br />
<br />
a) Folgerbarkeit - Implikation<br />
b) Implikation - Modus Ponens<br />
c) Modus Ponens - Folgerbarkeit<br />
<br />
== Aufgabe2 ==<br />
Es waren verschiedene Formel gegeben und man sollte ein kreuz bei zutreffenden Antworten machen. (Kontingent, (allgemein)gültig, unerfüllbar)<br />
In der Art: Seien F und G Formeln.<br />
G ist Tautologie und F=>G gültig. Was kann F dann sein: gültig, kontingent, unerfüllbar?<br />
und das für mehrere verschiedene formeln/Bedingungen! Waren 6 Formeln<br />
<br />
== Aufgabe 3 ==<br />
Definiere Hornklausel, Hornformel, Literal und Implikationsschreibweise.<br />
<br />
== Aufgabe 4 ==<br />
Noch eine aus dem ersten Teil zum Markierungsalgorithmus: <br />
a) Welche Eingabe nimmt der Algorithmus, welches Resultat liefert er? <br />
Gib Eingabe und Ausgabe an und beschreibe den Algorithmus möglichst genau!<br />
b) Begründen Sie, warum der Algorithmus immer terminiert.<br />
c) Begründen Sie, dass der Algorithmus "unerfüllbar" nur für unerfüllbare Formeln liefert.<br />
<br />
== Aufgabe 5: Resolution == <br />
Folgerbarkeit einer Formel F von einer Formelmenge M zeigen (stand afaik zeigen da, d.h. es war klar, dass sie Folgerbar war..)<br />
<br />
== Aufgabe 6: Unifikation ==<br />
3 Prädikatenlogische Formelmengen waren gegeben und man sollte begründen/wiederlegen warum man sie (nicht) unifizieren kann<br />
u, v, w, x, y, z - Variablen<br />
P - Aussagensymbol<br />
a) P( irgendwas ) P ( irgendas ) P (Irgendwas) <br />
b) Blub<br />
c) P ( h ( x, f(w) ), x), P( f(y), h(z), y) <br />
(So etwa)<br />
<br />
== Aufgabe 7(?) - ne, das muss auch irgendwo im 2. Teil gewesen sein. Jeder Teil hatte 6 Aufgaben. ==<br />
Ist die Menge 2^M immer abzählbar, wenn <br />
O M abzählbar ist <br />
O M aufzählbar ist <br />
O M endlich ist <br />
<br />
waren insgesamt 7 aufgaben im ersten teil, die andere weiß ich grad nicht..<br />
<br />
== Teil 2: Formale Sprachen, Automaten und Komplexität ==<br />
== 1. == <br />
Alphabet gegeben (a, b). Gib jeweils geforderte Sprache sowie alle Wörter der Länge 3 über Alphabet-Stern an, die nicht enthalten sind!<br />
<br />
a) Alle Wörter, in denen kein a vor einem b steht<br />
<br />
b) Alle Wörter, in denen ab oder ba, aber nicht beide enthalten sind<br />
<br />
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}<br />
<br />
== 2. ==<br />
Kellerautomat gegeben<br />
<br />
a) Gib alle Wörter bis zur Länge 4 an, die mit Endzustand akzeptiert werden.<br />
<br />
b) Gib alle Wörter bis zur Länge 4 an, die mit leerem Keller akzeptiert werden.<br />
<br />
c) Gib ein Wort w aus L mit |w| >= 2 inkl. der Konfiguration an, das mit leerem Keller akzeptiert wird.<br />
<br />
d) Gib ein Wort w aus L mit |w| >= 2 inkl. der Konfiguration an, das mit Endzustand akzeptiert wird<br />
<br />
== 3. Aussagen über formale Sprache, PSpace, NSpace, Entscheidbarkeit ==<br />
Man konnte jeweils "Ja" oder "Nein" ankreuzen<br />
<br />
a) Das Komplement jeder entscheidbaren Menge ist aufzählbar.<br />
b) PSpace ist Teilmenge von Cs ist Teilmenge von NSpace.<br />
d) Jedes Problem in NP ist entscheidbar.<br />
<br />
== 4. ==<br />
a) Definiere Entscheidbarkeit<br />
b) Wieder Aussagen und Fragen<br />
<br />
== 5. ==<br />
Deterministischer Automat gegeben - erstelle Potenzautomat<br />
(Zustände q0 und q1, q1 Endzustand, q0 Anfangszustand, <br />
a-Pfeil von q0 nach q1 und von q0 nach q0, b-Pfeil von q1 nach q0, das wars glaub ich..)<br />
<br />
== 6. == <br />
Wie würdest du vorgehen, wenn du testen willst, ob ein Problem NP-vollständig ist?<br />
<br />
<br />
[[Kategorie:Gedaechtnisprotokoll|FGI1]]</div>84.144.86.100