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