= Datum der Prüfung: 
24.7.2015
= Benötigte Lernzeit als Empfehlung: 
mehrere Wochen.
= Relevante Materialien 
Vorlesungsskript, Übungsaufgaben
= "Atmosphäre" der Prüfung / Verhalten der Beisitzer
Angenehme Atmosphäre, am Tisch nebeneinander auf einem Blatt, Beisitzer im Verlauf der Prüfung nichts gesagt. Es wird einem die Möglichkeit gegeben, sich an Sachen zu erinnern oder diese kurz herzuleiten und leicht geholfen falls das nicht funktioniert.
= Prüfungsverlauf
Was für Methoden hatten wir, zu zeigen, dass etwas in einer Logik nicht definierbar ist?
    (Alle aufgezählt, auf Reduktion kurz eingegangen, kompositionslemmata vergessen)
Wie waren die 0-1 Gesetze formal definiert, schreiben sie mal alles auf, was man dafür braucht.
Warum gelten die 0-1 Gesetze für FO auf UG? 
    (Angefangen, dass Erweiterungsaxiome in fast allen endlichen Strukturen gelten und gewinnstrategien für duplicator beschreiben)
Wie genau sieht die Gewinnstrategie für Duplicator aus in zwei Strukturen, die beide die EA erfüllen?
    (Konnte ich beantworten)
Wie sieht es aus, wenn zusätzlich zu E die Signatur noch ein Konstantensymbol enthält?
    (Konnte ich beantworten, hat keine 0-1 Gesetze mit Beispiel einer Strukturklasse, bei der mu_n(phi|(UG,c))= 1/2

Was sagt der Satz von Gaifmann?
    (Konnte ich beantworten)
Wann ist eine Formel lokal?
    (Konnte ich nach einigem rumgerudere unsicher herleiten, war richtig)
Was ist ein basislokaler Satz?
    (Habe vergessen, dass die enthaltene lokale Formel nur eine freie variable hat)
Was sagt der Satz von Seese?
    (Konnte ich beantworten)
Wie sieht der Algorithmus aus?
    (Konnte ich nicht mehr genau beantworten, sowohl Schritt 1 (Knoten die die Formel erfüllen markieren) als auch Schritt 2 (In der markierten Knotenmenge genug finden, die den richtigen Abstand hatten) konnte ich nicht angeben. Ich bin nicht auf die Idee gekommen, den auf Hanf basierenden alternativen Algorithmus stattdessen anzugeben)

Was sagt der Satz von Immermann und Vardi?
    (Gibt zwei Sätze, konnte beide angeben)
Bei dieser Frage bin ich mir nicht mehr sicher, irgendwas in der Richtung "Warum beschreibt LFP nicht P auf FIN"?
    (Gegenbeispiel ist mir 20 sekunden nach Prüfungsende eingefallen, wäre EVEN gewesen)
Definieren sie Graphenzusammenhang in LFP
    (Konnte ich)

Note (Optional): 2.0
= Fazit (Gute/schlechte Prüfung , angemessene Benotung etc...)
Ich gehe davon aus, dass bei einem etwas besseren Verlauf der Prüfung auch schwerere Fragen noch gekommen wären.

Es wurde genau das Thema (r-lokalität, Gaifmann) getroffen, in dem ich unsicher war. Schweikardt meinte, sie hat dies erkannt und berücksichtigt, grundsätzlich hätte ich das Thema verstanden, deshalb 2.0. Benotung war absolut fair.

= Datum der Prüfung
24.07.15

= Benötigte Lernzeit als Empfehlung
Habe 4 Tage gelernt, etwas mehr wäre besser gewesen.

= Verwendete Materialien (Bücher, Skripte etc...)
Skript und Aufzeichnungen aus VL + Übung

= "Atmosphäre" der Prüfung / Verhalten der Beisitzer
Gemütliche Atmosphäre, Beisitzer hält sich komplett raus

= Prüfungsfragen
- Nennen Sie Beispiele für Zusammenhänge zwischen Logiken und Komplexitätsklassen (also Beispiele für "L definiert C auf S")
- Was sind 0-1-Gesetze und für welche Logiken und welche Strukturklassen gelten sie?
- Wie lassen sich L_{\infty\omega}^\omega und PFP auf FIN unterscheiden?
- Wie funktioniert der Beweis für "PFP beschreibt PSPACE auf FIN_<"? (Grobe Skizze, detaillierte Fragen zu einzelnen Teilen des Beweises, z.B. die Abbruchbedingung der Fixpunktiteration)
- Was sagt der Satz von Hanf aus? (Aufschreiben, Voraussetzungen erklären, Beweis per Induktion über m skizzieren)
- Wie lässt sich der Satz von Seese beweisen? (über Satz von Gaifman oder Satz von Hanf, eine der Möglichkeiten detailliert erklären)

= Note (Optional)
1,3

= Fazit (Gute/schlechte Prüfung , angemessene Benotung etc...)
Gute Prüfung mit fairen Fragen. Fehler werden nicht direkt korrigiert, sondern Frau Schweikardt versucht, einen durch geschicktes Nachfragen dazu zu bringen, sich selbst zu korrigieren. Wenn man das schafft, gibt es auch keinen großen Abzug.
Insgesamt wurde nur ein Teil des Stoffes abgefragt, dafür an manchen Stellen sehr detailliert. Die Details musste man aber nicht unbedingt auswendig wissen, wenn man sie sich schnell genug herleiten konnte.

= Datum der Prüfung
2023-07-20

= Benötigte Lernzeit als Empfehlung
14 Tage nach Ende der VL-Zeit.
Wegen Prüfungstermin in der letzten VL-Woche konnte ich jedoch nur 3 ganze und 4 halbe Tage zur Wiederholung nutzen.

= Verwendete Materialien (Bücher, Skripte etc...)
Alles an Material von der Website (Prof. Schweikardts handschriftliche Notizen, provisorisches Skript, eigene Mit-/Abschriften, eigene Lösungen und Mitschriften aus den Übungsstunden, vereinzelt die Bücher [EF] und [L])
Die VL hatte ich nur sporadisch besucht, aber zeitnah zuhause vor- bzw. nachgearbeitet. Ich war bei allen Übungsstunden und habe alle Blätter gewissenhaft bearbeitet.

= "Atmosphäre" der Prüfung / Verhalten der Beisitzer
Prüferin, Beisitzer und Prüfling sitzen an einem Doppeltisch. Alle haben Papier und Stift vor sich. Der Beisitzer macht sich die meiste Zeit Notizen (daran merke ich, ob ich gerade etwas Sinnvolles gesagt habe). Die Prüferin schreibt einerseits Dinge auf, die ich nur mündlich gesagt habe, um Präzisierungen zu verlangen, und andererseits notiert sie neue Fragen. Die Prüferin sitzt lässig zurückgelehnt und stellt ihre Fragen sehr ruhig. Gerade wenn ich schneller werde, und mich beginne zu verhaspeln, spricht sie besonders langsam, um die Situation zu entspannen. Häufig kann ich an ihrer Mimik erkennen, ob ich auf dem richtigen Weg bin. Bei den Transferfragen bleibt sie aber erst neutral, um nichts zu verraten. Wenn ich etwas arg durcheinanderbringe, dann guckt sogar der Beisitzer fragend, aber ich habe versucht, nicht auf ihn zu achten.
Insb. zum Ende hin wurde es ein lockereres Gespräch, was auch daran zu bemerken war, dass der Beisitzer den Stift weggelegt und sich ebenfalls zurückgelehnt hat. Da hat er sich sogar eingemischt, als ich damit argumentieren wollte, dass ESO 2-Färbbarkeit ausdrücken kann. Die einzig andere Interaktion mit dem Beisitzer war die Frage der Prüferin nach der Zeit.

Prof. Schweikardt hatte beim letzten VL-Termin angekündigt, dass es ihr lieber ist, wenn wir direkt sagen, wenn wir zu einem Thema nichts sagen können, damit wir in der Prüfung damit keine Zeit verschwenden und stattdessen mehr zu etwas anderem erzählen können. (Halte ich für erwähnenswert, da das nicht alle Prüfer*innen so sehen.)

= Prüfungsfragen
Was sagt der Satz von Fagin?
- Es gibt ja mehrere Sätze von Fagin. Die aufgezählt, bei Ajtai und Fagin die infinitäre Logik mit EMSO verwechselt.

Wie haben wir den Satz von Fagin „ESO beschreibt NP auf FIN“ bewiesen?
- Erst grobe Idee erzählt, dann weiter ins Detail anhand von Nachfragen. Darauf eingegangen, dass wir Polyzeit als Einschränkung brauchen, damit wir die Zeitpunkte als k-Tupel über dem Universum darstellen können. Vergleich zu Immerman und Vardi gezogen.

(Transfer) Können wir diese Konstruktion aus dem Satz von Fagin mit einer einzigen Relationsvariablen machen?
- Vmtl ja, denn bei Immerman und Vardi ging das ja auch, aber mit der Ordnung müssen wir vmtl aufpassen. Wir können die Subrelationen anhand einer Markerkomponente auftrennen wie in Immerman und Vardi.

Was sagt der Satz von Immerman und Vardi denn aus?
- Aussage, Beweisidee und Unterschiede zu Fagin. Beschrieben, wie die Induktionsstufen der Lauf der DTM simulieren.

Was sagt der Satz von Knaster und Tarski?
- Einordnung ins Thema Fixpunktlogik, Aussage, Beginn des Beweises, bei der Richtung des ersten Beweisschrittes verzettelt, von ihr abgebrochen.

In welche Logik können wir die Fixpunktlogiken einbetten?
- IFP \leq LFP \leq PFP < L_{infty, omega}^{omega}. Die erste Ungleichung müsste andersrum sein, von ihr auf den richtigen Pfad gebracht, konnte aber nicht zu allen Hinweisen etwas Sinnvolles sagen. Nach einem Beispiel für etwas, das wir in infinitärer Logik ausdrücken können, aber in PFP nicht, wurde nicht gefragt.

(Transfer) Was wissen wir über das Verhältnis von LFP und SO auf FIN_<?
- Verbindung von Immerman-Vardi und Fagin.

(Transfer) Gleiches auf FIN ohne Ordnung?
- Nach Bedenkzeit und Hinweisen der Prüferin: Uns genügt, dass LFP in PTIME ausgewertet werden kann (unabhängig von Ordnung). Wir müssen nicht wissen, welche Komplexitätsklasse LFP auf FIN (ohne Ordnung) beschreibt.

0-1-Gesetze. Was ist das? Erstmal für ungerichtete Graphen.
- Erst grobe Erklärung, dann Aussage, dass FO das 0-1-Gesetz bzgl UG hat. Beweisvorgehen: erst Erweiterungsaxiome, Idee am Bildchen, Formel aufschreiben, wie wir daraus das 0-1-Gesetz beweisen, weiterer Zwischenschritt: wenn zwei Strukturen alle EA_k für k \leq m erfüllen, dann sind sie m-äquivalent.

Für welche Logiken bzgl. welcher Klassen von Strukturen haben wir 0-1-Gesetze gezeigt?
- Alles aufgezählt, inkls den Fixpunktlogiken und warum (Einbettung von eben gerade).

(Transfer) Hat ESO ein 0-1-Gesetz?
- Bedenkzeit, erst falsches Beispiel (ESO kann bipartite Graphen definieren, aber die sind eh sparse), dann ein sinnvolles, weil wir wegen Fagin wissen, dass wir mit ESO alle NP-Eigenschaften ausdrücken können: ESO kann gerade Universen definieren, daher kein 0-1-Gesetz (genau das Beispiel hatten wir am letzten VL-Termin besprochen).

= Note (Optional)
1,0

= Fazit (Gute/schlechte Prüfung, angemessene Benotung etc...)
War wie bei den bisherigen beiden Prüfungen bei Schweikardt. Dass es diesmal 1,0 und nicht 1,3 geworden ist, war eher Glückssache (Fragen und Tagesform).

= Datum der Prüfung 
19.02.26
= Benötigte Lernzeit als Empfehlung
Habe das Semester über Mitschriften gemacht. Damit haben 5 Tage Lernen früh bis spät gereicht. Aber mehr zu empfehlen, wenn man noch ein Leben haben will :(

= Verwendete Materialien (Bücher, Skripte etc...)
Eigene Mitschriften, (Skript)
= "Atmosphäre" der Prüfung / Verhalten der Beisitzer
Angenehm, Sie konnte Druck wegnehmen
= Prüfungsfragen


- HAMILTON ist in welchen Logiken definierbar und in welchen nicht

- eingegangen auf warum für MSO nicht und Satz von Büchi (Elgot Trakhtenbrot) (REG --> EMSO)

- warum ist HAMILTON für ESO definierbar (Formel bzw. Satz von Fagin)

- Wie kann HAMILTON in infinitärer Logik beschrieben werden (gebe Formel an)

- Wieso geht es nicht in infinitärer Logik mit beschränkter Variablenanzahl (Beweis dafür)

- Warum geht es für die Fixpunktlogiken nicht? (Zeigen, dass pfp <= L_infty, omega ^omega)



- Definition 0-1-Gesetze (und was dazu gehört)

- welche Logiken haben auf welchen Klassen 0-1-Gesetze

- warum hat ESO keins auf UG? (EVEN --> warum erfüllt es das? --> Formel/Fagin/Büchi mit EMSO)

- Wenn du für ungerichtete Graphen noch eine Konstante hinzufügst, hat FO dann immer noch ein 0-1-Gesetz?

- --> Bin ich nicht drauf gekommen und wurde geleitet --> was ist mit einstelligen Relationen statt E? (drin oder nicht --> \mu=0.5) Was ist mit gerichteten Graphen? (Pfad zu sich selber --> \mu 0.5)
- trotzdem nicht auf Lösung der ursprünglichen Frage gekommen


= Note (Optional)
1.0
= Fazit (Gute/schlechte Prüfung , angemessene Benotung etc...)
Sehr angenehme Prüfung, hat mir persönlich Spaß gemacht.

= Datum der Prüfung
Wintersemester 25/26, erster Prüfungszeitraum

= Benötigte Lernzeit als Empfehlung
Ich habe ca 12-15 volle Tage verteilt auf 3 Wochen gelernt. Ich denke die Zeit reicht auch für eine bessere Prüfung aus, wenn sie effizienter genutzt wird.
Während des Semesters habe ich fast alle Übungsblätter komplett bearbeitet, war bei fast allen Übungen und etwas mehr als der Hälfte der Vorlesungen anwesend.

= Verwendete Materialien (Bücher, Skript etc...)
Die Skriptfragmente, handschriftlichen Notizen und Übungsblätter von der Website, sowie meine Lösungen der Übungsblätter, bzw. der Mitschriften aus der Übung.
Zusätzlich habe ich während des Lernens eine Zusammenfassung zu den Zusammenhängen der Logiken & Komplexitätsklassen (NP=ESO auf FIN, ESO-Horn=P auf FIN_<, Fixpunktlogiken < k-Frgament der infinitären Logiken auf FIN, etc.) sowie der Definierbarkeit von Graphzusammenhang, reachability (in gerichteten und ungerichteten Graphen) und Hammilton-Kreis, sowie der Gültigkeit der 0-1-Gesetzte inkl. Beweis(ideen) auf allen behandelten Logiken geschrieben

= "Atmosphäre" der Prüfung / Verhalten der Beisitzer
Die Prüferin und der Beisitzer haben ihr bestes getan, für eine ruhige & entspannte Atmosphäre zu sorgen. 
Es wurde klar auf Basis der ersten Frage anhand eines roten Fadens entlang die weiteren Fragen gestellt. Auch basierend auf den Antworten auf vorherige Fragen, bzw. meiner Fähigkeit diese überhaupt zu beantworten.

= Prüfungsfragen
# Graphzusammenhang
    - Frage: In welchen der von uns behandelten Logiken können wir Graphzusammenhang definieren.
    - Antwort: Ich bin die Logiken in der selben Reihenfolge, wie ich sie auf meinem Lernzettel hatte, durchgegangen, habe gesagt, ob es geht, oder nicht und bei den, wo es nicht ging das ganz kurz begründet (wirklich mit max. einem Satz). Bei MSO bin ich kurz durcheinander gekommen, bin dann aber doch noch selbstständig drauf gekommen, dass es doch geht.
    
## auf MSO
    - Frage: (Ich denke, weil ich da vorher durcheinander gekommen bin) Wie sieht denn eine solche Formel in MSO aus?
    - Antwort: Erst mündlich, dann auf nachfrage explizit hingeschrieben, dass man über den Allquantor und alle mengen die die Transitive Hülle enthalten reachability definieren kann. Da bin ich bei den freien & gebundenen Variablen etwas durcheinander gekommen und habe die (um ehrlich zu sein grundlegenden Fehler) erst mit 1-2 Nachfragen gesehen und korrigiert.
    
## Auf ESO
    - Frage: Warum brauchen wir für die geg. MSO-Formel den Allquantor? und (nach kurzer Begründung, dass wir in MSO nicht verhindern können, dass in die Transitive Hülle zusätzliche Zusammenhangkomponenten geschmuggelt werden):
    Wieso geht das denn in ESO?
    - Antwort: Zunächst angefangen eine explizite Formel aufzuschreiben, mit der Nachfrage, ob es denn nicht auch einfacher geht dann schnell gesagt, dass Zusammengang klar in NP ist und ESO=NP auf FIN gilt.
    
## EMSO
    - Frage: Warum geht das nich in EMSO?
    - Antwort: grob erklärt, wie wir das mit dem Ajtaji-Fagin-Spiel gezeigt haben unter Erwähnung davon, dass der Kreis "groß genug" sein muss, damit Spoiler gezwungen ist, zwei identische 3^m-Umgebungen zu erzeugen
    - Nachfrage(n): kurzes Hin und her, wie "groß genug" denn aussieht, was ich verstanden habe als, dass die explizite Größe hergeleitet/begründet werden soll. Gemeint war aber, wie der Kreis geschnitten wird/warum das funktioniert.
    - Antwort: Erklärt, wie wir den Kreis schneiden (festlegen auf eine Richtung, Schneiden nach den Elementen mit selbem 3^m Umgebungstyp, dann zusammenkleben) und das wir damit keine 3^m Umgebungen verändern und mit Hanf dann eine Duplicator-Strategie für das EF-Spiel haben.
    
# Satz von Hanf
## Statement
    - Frage: Was sagt der Satz von Hanf? 
    - Antwort: den Satz gestatet.
## Aussage
    - Frage: Wie haben wir den Gezeigt?
    - Antwort: Beweisidee Angegeben:
        - Induktionsinvariante gestatet (mit den r_i, da zunächst nur 3^#verbleibende Runden gesagt, von ihr korrigiert worden mit der Aussage, dass das +1 wichtig ist)
        - Fallunterscheidung zwischen komplett enthalten in der r_i-Umgebung und komplett disjunkt von der r_{i+1}-Umgebung begründet und die Invariante in beiden Fällen mit der Induktionshypothese begründet
    - Rückfrage: Was ist mit komplett disjunkt gemeint?
    - Antwort: Das die Knotenmengen sich nicht überschneiden
    - Hinweis durch die Prüferin, dass es für den Beweis auch noch essentiell war, dass die Nachbarschaften nicht benachbart sind und wir daher die +1 in den r_i brauchten.

# infinitäre Logiken
## Graphzusammenhang (cont.)
    - Frage: Wieso ist Graphzusammenhang auf einem endlichen Variablen-Fragment der infinitären Logik definierbar?
    - Antwort: Weil es in den Fixpunktlogiken geht und die < L_\infty_\omega^\omega sind.
    - Nachfrage: Wie geht das denn auf LFP?
    - Auch wieder gesagt, dass wir reachability durch das iterative Bauen der transitiven Hülle definieren können und versucht das aufzuschreiben
        - das ist leider komplett gescheitert, ich habe das ganze eher als SO-Formel aufgeschrieben und nicht beachtet, dass nach der Semantik ja automatisch zu R hinzugefügt wird. Daher denke ich auch der folgende Block an Fragen:
        
## LFP Grundlagen
    - Frage: wie sieht denn LFP aus?
    - Antwort: Rekusionsvorschriften wie in FO + den lft-Operator, dann den definiert und die Idee hinter der Semantik angegeben
    (ohne dabei explizit auf die Definition der Funktion F_{\mathcal A \varphi} einzugehen).
    - Darauf dann "den" Fehler in der LFP formel gesehen und die Formel korrekt aufgestellt, angegeben, welche Variablen frei sind und welche dann in der Formel [lfp_{R, b} \varphi](b) frei sind.

## Knaster-Tarski
    - Frage: Was sagt der Satz von Knaster-Tarski aus?
    - Antwort: Nach etwas Bedenken und Unsicherheit bzgl. der Teilmenge in dem zweiten schnitt korrekt hin geschrieben.

## LFP=SO?
    - Frage: Wie stehen LFP und SO zueinander (beide Richtungen: <=/>=, angefangen mit LFP<= SO?)
    - Antwort: LFP<=SO stimmt, dazu aber leider eine falsche Begründung gegeben (Idee war LFP <= PSpace <= NP = SO, aber Pspace <= NP gilt nicht (da war etwas Unsicherheit, ob das nicht sogar ein offenes Problem ist)). Wurde glaube ich nicht allzu groß angekreidet, da der Fehler in einem Themenbereich außerhalb der Vorlesung lag.
    - Hinweis, dass es gilt und man über Knaster-Tarski einen entsprechenden SO-Satz bauen könnte, um den Fixpunkt zu beschreiben (jetzt wo ich das schreibe, glaube ich, dass wir das sogar in der Vorlesung hatten. Ist mir in der Prüfung aber nicht aufgefallen.)
    - Rückfrage: Und was ist mit >=?   
    -Antwort: Intuitiv glaube ich nicht, dass das gilt. Nach kurzem Überlegen drauf gekommen, dass wir den Hammilton-Kreis nicht in L_\infty_\omega^\omega, also auch nicht in LFP, aber in SO definierbar ist.
    

= Note (Optional)
Ich fand sie auf Basis meiner Performance vollkommen angemessen, nicht zu gut und nicht zu schlecht. Negativ aufgefallen waren speziell die falsch hingeschrieben expliziten MSO/IFP - Formeln.

= Fazit (Gute/schlechte Prüfung , angemessene Benotung etc...)
Ich kann (auch auf Basis der anderen Prüfungsprotokolle und Gespräche mit anderen Teilnehmer*innen) sagen, dass eine Übersicht (und diese auch komplett zu können) dazu, was wir wo und warum (nicht) definieren können sehr empfiehlt, speziell für Graphen. Darauf wird die Prüfung anscheinend immer aufgebaut, das ist also irgendwo eine Grundlage.
Auf Basis meiner Prüfung kann ich außerdem empfehlen, zu üben Formeln explizit hin zu schreiben (wenn du da sonst auch Probleme in einer Stress-Situation mit hättest).