= Datum der Prüfung
19.02.2016

= Benötigte Lernzeit als Empfehlung
1 Woche

= Verwendete Materialien (Bücher, Skripte etc...)
Skript

= "Atmosphäre" der Prüfung / Verhalten der Beisitzer
locker aber konzentriert

= Prüfungsfragen
- Wörter eines (gegeben) NFAs entscheiden und den Automaten in einen DFA umwandeln
- Einen DFA minimieren, Relationen angeben, Repräsentantensystem
- Zeigen das eine Sprache nicht regülär ist, Pumpingzahl einer Sprache finden
- PDA zu Grammatik und in CHompskynormalform umwandeln
- Typ-1 Grammatik zu einer Sprache finden
- Aussagen zu Sprachen bezüglich Schnitt etc entscheiden
- Aussagen bezüglich entscheidbarkeit entscheiden
- Reduktion
- Graphenprobleme (Matching, Färbarkeit, Eulertour...)

= Datum der Prüfung
24.02.2017

= Benötigte Lernzeit als Empfehlung
Ich habe eine Woche lang jeden Tag etwa 6-8h gelernt, allerdings einige Themen ausgelassen. Daher empfehle ich etwa 2 Wochen, je nachdem wie gut man die Übungen erledigen konnte

= Verwendete Materialien (Bücher, Skripte etc...)
Ich habe mir die wichtigsten Automaten, Algorithmen etc. auf ca 10 Seiten zusammengefasst und mitgenommen. Erlaubt war aber alles außer Bücher und elektronische Hilfsmittel.

= "Atmosphäre" der Prüfung / Verhalten der Beisitzer
Typische Prüfungsstimmung. Zu Anfang wurde jede einzelne Frage vorgelesen und es konnten Fragen gestellt werden, was ich als sehr angenehm empfand.

= Prüfungsfragen
1) 13pt
Gegeben: zwei DFAs (wie im Skript, nur a's und b's vertauscht)
-Explizite Beschreibung und regulären Ausdruck für beide DFAs angeben
-Aus beiden DFAs einen Automaten für den Schnitt konstruieren
-Einen DFA für die Vereinigung angeben, der höchstens 4 Zustände hat

2) 18pt
Gegeben: ein DFA
-DFA minimieren
-Repräsentantensystem für die Nerode Relation angeben
-4 unterschiedliche Wörter der Länge 4 welche bezüglich der Nerode Relation zu einem gegebenen Wort äquivalent sind

3) 15pt
Gegeben: eine Sprache
-Typ-0 Grammatik angeben
-PDA angeben
-DTM angeben

4) 22pt
Gegeben: 2 Sprachen und eine Definition (welche im Skript steht) als Hilfestellung
-Eine eindeutige Typ-2 Grammatik für eine Sprache angeben und den Syntaxbaum für ein Wort
-Mithilfe eines gegebenen Wortes zeigen, dass die andere Sprache nicht Kontextfrei ist
-Zwei Aufgaben vom Typ „gibt es eine Sprache die mit Schnitt einer der gegebenen Sprachen in einer bestimmten Klasse ist“

5) 10pt
Gegeben: 2 Sprachen
-Für jede Sprache begründen ob sie entscheidbar ist oder nicht

6) 10pt
Für zwei Probleme angeben ob sie in P liegen oder NP-hart oder co-NP-hart sind

7) 26pt
Gegeben: ein Graph
-4 Parameter bestimmen (max-Clique, min-färbung, max-Matching und min-Knotenüberdeckung)
-für 2 Subgraphen entscheiden ob es einen Homomorphismus gibt

8) 6pt
-Gebe einen Graphen mit 8 Knoten an, dessen maximales Matching 1 ist
-Gebe einen Graphen mit Hamiltonpfad, aber ohne Eulerlinie an

= Note (Optional)
Noch nicht korrigiert

= Fazit (Gute/schlechte Prüfung , angemessene Benotung etc...)
Prüfung schien einfacher als die Übungsaufgaben. Viele „leichte“ Punkte (DFA, Graphen), wenig Punkte für „komplexere“ Aufgaben. Etwas knappe Zeit (habe 2 Aufgaben nicht gemacht und war trotzdem erst kurz vor Ende fertig). Angemessene Benotung kann ich noch nicht beurteilen.

= Datum der Prüfung
24.02.2017
= Benötigte Lernzeit als Empfehlung
-4 Wochen
= Verwendete Materialien (Bücher, Skripte etc...)
-das Skript (sehr gut)
-die Vorlesungsfolien(das selbe wie das Skript nur bunter)
-die Übungsaufgaben
-die Klausuren der letzten Jahre
= "Atmosphäre" der Prüfung / Verhalten der Beisitzer
angenehm
= Prüfungsfragen
ist 2018 wahrscheinlich die Probeklausur
= Note (Optional)
4,0
= Fazit (Gute/schlechte Prüfung , angemessene Benotung etc...)
Auch wenn man sich immer auf alles vorbereiten soll, waren diese Aufgaben komplett anders als die Jahre zuvor, deshalb sehr überraschende Prüfung

= Datum der Prüfung
05.04.2017
= Benötigte Lernzeit als Empfehlung
4 Wochen
= Verwendete Materialien (Bücher, Skripte etc...)
Skript und Übungsaufgaben
= "Atmosphäre" der Prüfung / Verhalten der Beisitzer
angenehm
= Prüfungsfragen
1) 20 Punkte
Gegeben ein NFA
- Wörter entscheiden, Automaten in einen DFA umwandeln und äquivalenten Ausdruck angeben
2) 19 Punkte
Gegeben ein DFA
- Minimierung und 2 disjunkte Repräsentatensysteme für die Nerode-Relation
3) 16 Punkte
Gegeben Grundmenge und Relationen
- Finden zusätzlicher Parre zur Erfüllung bestimmter Eigenschaften
- Ordnung nestimmen
- Relation zur Herstellung von Isomorphie bestimmen
4) 35 Punkte
Gegeben eine CNF-Grammatik
- CYK-Algorithmus
- PDA konstruieren
- Beweis der Kontextfreiheit
- Pumping-Lemma anwenden
5) 10 Punkte
Gegeben 2 Sprachen
-Für jede Sprache begründen ob sie entscheidbar ist oder nicht
6) 10pt
Für zwei Probleme angeben ob sie in P liegen oder NP-hart oder co-NP-hart sind
7) 10 Punkte
2 Graphen mit best. Eigenschaften angeben
= Note (Optional)
3,7
= Fazit (Gute/schlechte Prüfung , angemessene Benotung etc...)
Prüfung schien einfacher als die Übungsaufgaben, aber Zeit sehr knapp bemessen

= Datum der Prüfung
= Benötigte Lernzeit als Empfehlung
4 Wochen
= Verwendete Materialien (Bücher, Skripte etc...)
Skript, Folien (WS17/18), Theoretische Informatik kurzgefasst (Uwe Schöning), 
https://www.youtube.com/user/leifaktor
= "Atmosphäre" der Prüfung / Verhalten der Beisitzer
Sehr entspannt. Prof. Dr. Köbler gestaltet die Prüfung ruhig, aber anspruchsvoll. Wenn man mal nicht weiterkommt, wird mit kleinen Denkanstößen geholfen. Dr. Kössler war Protokollant und hat sich bis auf ein Kopfnicken bei korrekten Antworten sehr unauffällig verhalten. Das gelernte Wissen muss ggf. auf einem Blatt Papier formal korrekt aufgeschrieben werden und auf die Korrektheit wird sehr geachtet. Also nicht nur einfach auswendig lernen, sondern auch verstehen, warum man z.B. bei Produktionen mit -> arbeitet und bei Ableitungen von Wörtern mit => (wie unterscheiden sich diese beiden Relationen voneinander?)
= Prüfungsfragen
Die mündliche Prüfung verläuft wohl immer relativ ähnlich. Zuerst geht es durch gesamte Chomsky-Hierachie, angefangen mit den einzelnen Sprachtypen, später dann zu Berechenbarkeitstheorie (wenn man soweit kommt).
Regulären Sprachen (Typ-3):
-Reguläre sprachen wie haben wir diese in der VL definiert? (Charakteristika)
-Beispielsprache selbst überlegen (a*b*), die reguläre Grammatik aufstellen (welche Einschränkungen gibt es hier?(u -> v; u € V, v € SIGMA V ∪ SIGMA ∪ {epsilon}; A->aB, A->a, A->epsilon), den dazugehörigen DFA konstruieren, wie kann man hier die Korrektheit zeigen?
-Wie sieht die Sprache aus, die von einem DFA erkannt wird? (L(M)={...})
-Ist der Automat minimal? Woran erkennt man das? -> Äquivalenzklassen/Nerode Relation definieren und erklären, warum die Anzahl der Zustände minimal ist.
Kontextfreie Sprachen (Typ-2):
-Wie wurde CFL in der VL definiert? (Charakteristika)
-Kontextfreie Grammatiken, welche Einschränkungen gibt es hier? Beispiel für eine Kontextfreie Grammatik geben (a^n b^n), wie sieht die Grammatik aus? 
-Wie sieht die Sprache aus, die von einer kontextfreien Grammatik erkannt wird? (L(G)={...})
Kontextsensitive Sprachen (Typ-1):
-Wie wurde CSL in der VL definiert? (Charakteristika) 
-Einschränkungen von CSG (|u|<=|v|)
-Tupelbeschreibung für LBA, wie sieht die Bedingung aus, damit eine NTM ein LBA ist?
-Wird bei der Übergabe des Wortes an den LBA nur das letzte Zeichen markiert? Warum nicht das Erste?

= Fazit (Gute/schlechte Prüfung , angemessene Benotung etc...)
Da es hier noch keine (bis auf alte Prüfungen; Theoretische Informatik 2) Gedächtnisprotokolle zu mündlichen Prüfungen in EThI gibt (3. Versuch), füge ich das hier mal hinzu, damit anderen Leuten etwas die Angst vor dem Ungewissen genommen wird. Die Prüfung ist sehr machbar und man merkt, dass es Prof. Dr. Köbler wichtig ist, dass der Student die Prüfung besteht. Wie die älteren Protokolle bereits gesagt haben, muss man sehr fit im Umgang mit der formellen Schreibweise sein. In dieser Prüfung kam nichts zu Berechenbarkeit oder Komplexität ran. Je schneller man die Fragen beantwortet, desto weiter geht es im Stoff und desto besser wird auch die Note. Wenn man mal irgendwo hängt, dann wird dieses Thema nicht übersprungen, sondern durch Hilfestellungen versucht, einen noch auf den richtigen Gedanken zu lenken. Wenn man die Maschinenmodelle verstanden hat (Tupelschreibweise, Startkonfiguration, Folgekonfiguration, akz. Sprache, etc.), Algorithmen wie Potenzmengenkonstruktion/DFA Minimierung (wie verändern sich hier die Tupel?), Beispiele für alle Typen der Chomsky-Hierachie (Maschinenmodelle für Beispielsprachen, Grammatiken für diese Sprache etc.), dann muss man sich kaum Sorgen machen vor der Prüfung. Viel Erfolg!!

= Datum der Prüfung
28.02.19
= Benötigte Lernzeit als Empfehlung
4 mal 4,5h. Allerdings lag die Vorlesung bei mir schon ein Jahr zurück, hatte im ersten Semester nicht mitschreiben können. 
= Verwendete Materialien (Bücher, Skripte etc...)
Übungsaufgaben und alte Probeklausuren
= "Atmosphäre" der Prüfung / Verhalten der Beisitzer
angenehm, konzentriert.
= Prüfungsfragen
1) Grammatik G gegeben (30 Punkte)
a) NFA N zur Grammatik erstellen
b) NFA N', der L(N)* als Srpache hat
c) N zum DFA machen
d) regulären Ausdruck für L(G) angeben
e) andere Sprache gegeben, dafür Minimal-DFA angeben und Index der Nerode-Relation angeben

2) Menge A gegeben mit Relation R (11 Punkte)
a) Zeigen, dass Schnitt einer Äquivalenzrelation mit Ordnung ebenfalls eine Ordnung ist
b) Hasse Diagramm von R
c) Supremum/Infimum einer Menge bzgl R

3) 16 Punkte Zeigen oder Widerlegen
a) Für beliebige A, B e DCFL gilt (A Komplement vereinigt B Komplement)* e NP
b) Es gibt ein GOTO-Programm P, das die Funktion f(n)=2^n berechnet und für jede Einfaben n höchstens n Befehle ausführt
c) PCP-Instanz hat eine Lösung
d) f, g, h totale Funktionen von {0,1}* nach {0,1}* mit h(x) =f(x)g(x) (Konkatenation)
Falls dann f und h berechenbar sind, ist auch g berechenbar

4) 21 Punkte, kontextfreie Grammatik gegeben
a) Grammatik in CNF umwandeln
b) Entscheiden ob andere Sprache kontext frei ist oder nicht
c) Entscheiden ob andere Sprache kontext frei ist oder nicht

5) Für jede der Sprachen entscheiden ob entscheidbar, semi-entscheibar oder nicht semi-entscheidbar.  Begründen. w jeweils aus {0,1}*. 12 Punkte.
a) Es gibt ein x aus {0,1}*: |x|<=|w| und Mw(x) hält nicht innerhalb von |w| Schritten ("<=" soll kleiner gleich sein)
b) Es gibt ein x aus {0,1}*: Mw(x) hält nicht innerhalb von |w| Schritten
c) Es gibt ein x aus {0,1}*: Mw(x) hält nicht 

6) 2 Graphen G, H gegeben, 30 Punkte
a) Zeigen dass G und H nicht isomorph
b) Zeigen dass isomorphe Graphen entstehen wenn je ein gegebener Knoten entfernt wird
c) 4 Cliquen angeben, die G komplett abdecken
d) Cliquenzahl und Stabilitätszahl von G angeben
e) CliqueFREE(G,k,l): Gibt es eine Knoten-Teilmenge der Größe |l| die keine Clique der Größe K als Teilmenge hat? Für 3 Instanzen entscheiden ob ja oder nein
f) Zeigen, dass CliqueFREE NP-hart und co-NP-hart ist indem sie zeigen dass sowohl IS als auch Komplement von CLIQUE in Polynomialzeit auf CliqueFREE reduzierbar sind
g) Geben sie mit Begründung jeweils an, ob G einen Hamiltonpfad bzw, Hamiltonkreis enthält

= Note (Optional)
2,0

= Fazit (Gute/schlechte Prüfung , angemessene Benotung etc...)
In der Klausur wird viel mehr Grundlagenwissen abgefragt, als die Probeklausuren vermuten lassen. Also nicht verunsichern lassen, wenn ihr da irgendwas nicht wisst. In der Klausur habt ihr eh nicht genug Zeit für alle Aufgaben (ich habe z.B. die 6f gar nicht gemacht), da bringt es euch nichts, wenn ihr beim Lernen viel Zeit darauf verwendet, die schwereren Sachen wie z.B. Reduktion zu üben. Lieber NFA/DFA minimieren/umformen und ein bisschen mit Grammatiken üben und das dafür dann sicher und schnell können!
Hatte das Gefühl, dass diese Klausur etwas härter benotet wurde als sonst (und das haben auch die Übungsleiter so ins Forum geschrieben). 41 von ~120 sind durchgefallen, mal sehen ob bei der Klausureinsicht etwas Kulanz gezeigt wird.