Logbuch „Theoretische Informatik 2“ (SoSe16)

Hier finden Sie (nach den Vorlesungen) Informationen zum Inhalt der einzelnen Vorlesungsstunden sowie gelegentlich ergänzende Bemerkungen.

Di, 12.07.2016

effizientes Model-Checking (vier Quantorenpaare genügen); Prädikatenlogik (der Hilbert-Kalkül (Axiome und Modus Ponens)); Gödelscher Vollständigkeitssatz (Ableitbarkeit im Hilbert-Kalkül = semantische Folgerung); Peano-Arithmetik und die Zahlentheorie; Gödelscher Unvollständigkeitssatz (in jedem rekursiv aufzählbarem Axiomensystem gibt es nicht-beweisbare, aber wahre Formeln)

Material:

Mo, 11.07.2016

Computational Tree Logic (Weg-Quantoren und Temporalquantoren); Berechnungsbaum (Berechnungen und Wege); Syntax und Semantik von CTL; Äquivalenz von CTL-Formeln

Material:

Di, 05.07.2016

Existenz langer Disjunktionsterme für das Schubfachprinzip (Zeugen von D, die Zeugenmengen wachsen nur langsam, Disjunktionsterme mit vielen, aber nicht zu vielen Zeugen sind lang); DPLL-Solver (Zusammenhang zu Resolutionsbeweisen); temporale Aussagenlogik (Kripke-Strukturen)

Material:

Mo, 04.07.2016

Vollständigkeit der Resolution, das Schubfachprinzip (Formulierung, i-kritische Matchings, monotone Beweise, Existenz langer Disjunktionsterme impliziert lange Beweise)

Material:

Di, 28.06.2016

Vollständigkeitssatz für ABS (maximal widerspruchsfreie Formelmengen); Frege-Systeme (verschiedene Frege-Systeme sind polynomiell äquivalent); Kompaktheitssatz; KNF-SAT (Anwendungen);

Material:

Mo, 27.06.2016

Parallelität: P-Vollständigkeit von LFMIS, Zusammenfassung Parallelität (Zusammenhang zur Speicherplatzkomplexität, Parallel Computation Thesis, Logspace-Reduktion, P-Vollständigkeit: CVP, LP, LFMIS)
Aussagenlogik: Beweissysteme und Länge von Beweisen, konventionelle Beweissysteme (ABS: Modus Ponens), Beweisbarkeit impliziert Wahrheit

Material:

Di, 21.06.2016

P-Vollständigkeit (Logspace-Reduktion); das Circuit-Value-Problem ist P-vollständig (CVP, M-CVP, NOR-CVP), lineare Programmierung ist P-vollständig; Parallelisierbarkeit von Greedy-Algorithmen

Material:

Mo, 20.06.2016

uniforme Schaltkreisfamilien, Depth- und Size-Komplexitätsklassen, die Klassen NC und ACk, der Zusammenhang zwischen paralleler Rechenzeit und Speicherplatz (Tiefensuche; boolsches Matrizenprodukt, transitive Hülle)

Material:

Di, 14.06.2016

Speicherplatz: PSPACE und die Komplexität der Bestimmung von Gewinnstrategien, Universalitätsproblem und Äquivalenzproblem für reguläre Ausdrücke bzw. NFAs sind PSPACE-vollständig, effiziente probabilistische und Quantenberechnungen "bleiben" in PSPACE; Speicherplatzkomplexität: eine Zusammenfassung
Parallelität: Definition von Schaltkreisen

Material:

Mo, 13.06.2016

nichtdeterministischer Speicherplatz ist abgeschlossen unter Komplementbildung (Anzahlproblem, Lösung des Anzahlproblems); PSPACE-Härte, QBF, QBF ist PSPACE-vollständig (wie setzt man die Kraft der Quantoren ein?)

Material:

Di, 07.06.2016

platzkonstruierbare Funktionen, eine Speicherplatz-Hierarchie (Diagonalisierung), Satz von Savitch (ein deterministischer Algorithmus für D-Reachability mit wenig Speicherplatz, der allgemeine Fall)

Material:

Mo, 06.06.2016

NL ist eine Teilmenge von P, die Chomsky-Hierarchie (Typ-0-Sprachen und rekursiv aufzählbare Sprachen stimmen überein, Typ-1-Sprachen und NSPACE(n) stimmen überein, es gibt eine NL-vollständige kontextfreie Sprache)

Material:

Di, 31.05.2016

DL ist eine Teilmenge von P (jede Konfiguration kann nur einmal angenommen werden); wie mächtig ist NL? (D-Reachability und die Simulation von NFAs gehören zu NL, wahrscheinlich aber nicht zu DL); LOGSPACE-Reduktionen; NL-Vollständigkeit; D-Reachability ist NL-vollständig (Berechnungsgraph einer nichtdeterministischen Turingmaschine)

Material:

Mo, 30.05.2016

Anwendungen der Unentscheidbarkeit des Postschen Korrespondenzproblems (leerer Schnitt, Eindeutigkeit, Universalität, Äquivalenz); Zusammenfassung (reguläre und kontextfreie Sprachen); Speicherplatzkomplexität (I-O-Turingmaschinen, Komplexitätsklassen für Speicherplatz (DL, NL, PSPACE); was kann DL? (Programmiertricks)

Material:

Di, 24.05.2016

Das Postsche Korrespondenzproblem (PKP); Reduktion von der universellen Sprache U auf das modifizierte PKP (eine akzeptierende Berechnung wird in eine Konfigurationenfolge übersetzt, ein erfolgreiches PKP-Puzzle gibt die Konfigurationenfolge wieder)

Material:

Mo, 23.05.2016

Deterministische Kellerautomaten (DPDAs; warum epsilon-Übergänge?, warum Akzeptanz mit Zuständen?) deterministisch kontextfreie Sprachen (DCFLs); Abschluss unter Komplementbildung, Abschluss unter Schnitt mit regulären Sprachen; Nicht-Abschlusseigenschaften (Durchschnitt, Vereinigung, Konkatenation, Kleene-Stern); fundamentale Eigenschaften: Alle reguläre Sprachen sind DCFLs, jede DCFL ist eindeutig, das Wortproblem für DPDAs ist in Linearzeit lösbar. Wortproblem für konfextfreie Sprachen (Chomsky-Normalform; Algorithmus von Cocke-Younger-Kasami); Entscheidungsprobleme (Wortproblem, Leerheitsproblem, Endlichkeitsproblem)

Material:

Di, 17.05.2016

Kellerautomaten (Akzeptanz durch Zustände, Akzeptanz durch leeren Stack); Simulation einer KFG durch einen PDA; Simulation eines PDAs durch eine KFG (Tripelkonstruktion);

Material:

Di, 10.05.2016

Ogden's Lemma (Beweis und Anwendungen); Abschlusseigenschaften kontextfreier Sprachen (Vereinigung, Konkatenation, Kleene-Stern, rückwärts lesen, Schnitt mit regulären Sprachen), Nicht-Abschlusseigenschaften (Durchschnitt, Komplement); Kellerautomaten

Material:

Mo, 09.05.2016

Kontextfreie Grammatiken und kontextfreie Sprachen (Spezifikation von Programmiersprachen); Ableitungsbäume (eindeutige und mehrdeutige Grammatiken, eindeutige und inhärent mehrdeutige Sprachen, eine eindeutige Grammatik für arithmetische Ausdrücke, if-then-else-Ausdrücke); Pumpinglemma für kontextfreie Sprachen

Material:

Di, 03.05.2016

PFAs (Schwellenwert und Lücke); nicht-reguläre Sprachen werden bei Lücke 0 akzeptiert, nur reguläre Sprachen bei positiver Lücke; Zwei-Wege-Automaten akzeptieren nur reguläre Sprachen, bestimmte Sprachen benötigen im Vergleich zu DFAs/NFAs sehr wenige Zustände

Material:

Mo, 02.05.2016

Reguläre Ausdrücke, Satz von Kleene (eine Sprache ist genau dann regulär, wenn sie einen regulären Ausdruck besitzt); Reguläre Grammatiken (eine Sprache ist genau dann regulär, wenn sie von einer regulären Grammatik erzeugt wird); NFAs und reguläre Grammatiken sind Zwillinge

Material:

Di, 26.04.2016

NFAs (epsilon-NFAs, Fooling-Sets); Abschlusseigenschaften (boolsche Operationen, Konkatenation, Stern, Präfix, Suffix, Reverse, etc; Homomorphismen, inverse Homomorphismen, Substitution); einfache Entscheidungsprobleme (Leerheitsproblem für DFAs und NFAs, Äquivalenzproblem für DFAs; Wortproblem für NFAs); schwierige Entscheidungsprobleme (Äquivalenzproblem für NFAs, Interpolationsproblem für DFAs)

Material:

Mo, 25.04.2016

Der Äquivalenzklassenautomat ist minimal, der Myhill-Nerode-Automat ist ebenfalls minimal; Satz von Myhill-Nerode (der Index entscheidet, ob eine Sprache regulär ist); Pumping-Lemma (Achtung: der Gegner besitzt die Pumping-Konstante und kontrolliert die Zerlegung zumindest teilweise); NFAs (die erweiterte Übergangsfunktion); Potenzmengenkonstruktion (eine Zustandsexplosion für den DFA ist möglich)

Material:

Di, 19.04.2016

Hopcrofts Algorithmus (die Checkmenge, Zerlegung von Klassen in Kinderklassen, Aktualisierung der Checkmenge, Aktualisierung der Zerlegung); die Nerode-Relation, der Index einer Sprache L und die Zustandszahl von Automaten für L

Material:

Mo, 18.04.2016

Der Ansatz von Minimierungsalgorithmen, der Algorithmus von Moore (sukzessive Berechnung der Verschmelzungsrelation der Ordnung i, Tiefe von Automaten, Laufzeitanalyse), Hopcrofts Algorithmus (Zerlegung von Klassen durch eine gegebene Klasse, die Menge Check der Testklassen)

Material:

Di, 12.04.2016

Deterministische endliche Automaten (DFAs), äquivalente Automaten, Verschmelzungsrelation für einen DFA, Minimierungsalgorithmus (Berechnung der Verschmelzungsrelation und Übergänge zwischen den Äquivalenzklassen): wir erhalten den Äquivalenzklassenautomaten

Material:

Mo, 11.04.2016

Administratives, Sprachen, Konkatenation, Kleene-Abschluss, rekursive Definitionen und vollständige Induktion

Material: