Für die Klausur in den Theoretischen Grundlagen der Informatik sollte man Folgendes auf jeden Fall wissen:
- Wie konstruiert man mittels Potenzmengen einen äquivalenten deterministischen endlichen Automaten zu einem Nichtdeterministischen? → Antwort
- Wie bringt man eine Grammatik in Chomsky-Normalform? → Antwort.
- Was macht der CYK-Algorithmus und wie funktioniert er? → siehe Beispiel ab Folie 15
- Was ist die Chomsky-Hirarchie, welche Grammatiken gibt es und mit welchen Operationen sind sie Abgeschlossen? → Antwort.
- Was ist das Post’sche Korrespondenzproblem?
- Welche Komplexitätsklassen sind \(\cal P, NP, NPC, DTAPE, NTAPE, NPI\)? → Antwort
- Wie sind Kellerautomaten definiert, wann sind sie formal nicht-deterministisch und in welcher Beziehung stehen sie zur Greibach-Normalform? Wie formt man einen Kellerautomaten von einem akzeptierenden Endzustand in einen mit leerem Stack um? → Antwort.
- Wie lautet das Pumping-Lemma (für reguläre und kontextfreie Sprachen? Wie lautet Ogdens Lemma? Und wie benutzt man diese für Beweise? → Antwort
- Wie beweist man NP-Vollständigkeit?
Some Random Facts
- “aaa” ist in der Sprache aller Worter, die zwei mal “aa” enthalten. [1]
- Die Grammatik \(G_1(\{S\}, \{\varepsilon\}, \{S \rightarrow \varepsilon\},S)\) erzeugt die Sprache \(L(G_1) = \{\varepsilon\}\).[2]
- Die Grammatik \(G_2(\{S\}, \{\varepsilon\}, \{\},S)\) erzeugt die Sprache \(L(G_2) = \{\}\).
- \(L_1 := \{aba, bab, ab\}, L_2 := \{bb,ab,ba\}\). Dann ist
\(L_1 / L_2 = \{\varepsilon, a, b\}\) und
\(L_1 \setminus L_2 = \{aba, bab\}\)[3] - \(PKP \notin \cal NPC\)[4]
- Es kann sein, dass die Ableitung eines Wortes nicht eindeutig ist, aber der Syntaxbaum eindeutig ist.
- Für jedes Wort w gibt es einen DEA, der w akzeptiert[5]
- \(L’ \alpha L\) bedeutet, dass L’ polynomial transformierbar in L ist.
- \(L’ \alpha_T L\) bedeutet, dass L’ Turing-reduzierbar in L ist.
Termin
Datum: Mittwoch, der 22.02.2012 um 14:00 Uhr (siehe Vorlesungswebsite)
Ort: Steht hier. Ich schreibe im Tulla, manche noch im Gaede und andere im HS a. F., Daimler oder Benz. Laut dieser Liste schreiben 295 Personen diese Klausur!
Dauer: 120 min. (siehe erste Folie)
Punkte: Bisher waren es meist ca. 60, von denen man 20 zum Bestehen benötigt hat.
Übungsschein: Liste der 195 Leute, die ihn bestanden haben. Der Übungsschein bringt einen Klausurbonus. Allerdings habe ich keine Ahnung, wie hoch dieser ist.
edit: +0,3 zur Klausurnot (Danke Alexander 
)
Ach ja, ich habe “Yet Another Info 3 Resume” noch gar nicht verlinkt. Das ist sehr kurz und hat viele wichtige Informationen.
Einzelnachweise
1. ↑: 2. Klausur WS 2003/2004, Aufgabe 1a
2. ↑: 1. Klausur WS 2003/2004, Aufgabe 5
3. ↑: 1. Klausur WS 2007/2008, Aufgabe 3c
4. ↑: 1. Klausur WS 2007/2008, Aufgabe 5
5. ↑: 1. Klausur WS 2010/2011, Aufgabe 5
