Inhalt der Vorlesung

• 12.4.2005: Einführung in die theoretische Informatik und Überblick über die Vorlesung, Probleme "Transport von Paketen" und Partition, Begriffe Problem und Sprache, Vergleich von Entscheidungs- und Suchproblemen.
• 14.4.2005: Registermaschinen, algorithmische Komplexität, Turingmaschinen,  Sonderrolle polynomieller Rechenzeiten, Komplexitätsklasse P.
  
• 19.4.2005: Randomisierte Algorithmen, Probability Amplification, Komplexitätsklassen für randomisierte Algorithmen.
• 21.4.2005: Fortsetzung Probability Amplification, Teilmengenbeziehungen zwischen den Komplexitätsklassen.
• 26.4.2005: Zshg. zwischen ZPP, RP und co-RP, Einführung Nichtdeterminismus, NP, Turing-Reduktionen, Vergleich verschiedener TSP-Varianten, Cliquen-Problem.
• 28.4.2005: Reduktion von Clique_opt auf Clique_dec und BinPacking_opt auf BinPacking_dec, Reduktionen zwischen HC, DHC, TSP, SAT-Varianten, Partition, Bin Packing, Clique, Independent Set, Vertex Cover.
• 3.5.2005: Reduktion von 3-SAT auf Independent Set und DHC, Matching- und Flussprobleme, Meisterschaftsprobleme, polynomielle Reduktionen und ihre Eigenschaften.
• 10.5.2005: Definitionen von NP-vollständig und NP-schwer, Ablauf von NP-Vollständigkeitsbeweisen, alternative Charakterisierungen von NP, deterministische Simulation von NP, stereotype Turingmaschinen, Satz von Cook und seine Anwendung, Anfang des Beweises des Satzes von Cook.
• 12.5.2005: Vervollständigung des Beweises des Satzes von Cook, Ansatz von NP-Vollständigkeitsbeweisen für neue Probleme, NP-Vollständigkeitsbeweise für Hamiltonian Path, Bounded degree spanning tree, Subset Sum Problem
• 17.5.2005: Rucksackprobleme, Partition, Bin Packing, Schedulingprobleme, Cliquenprobleme, Graphfärbbarkeit, 3-DM, Set Cover
• 19.5.2005: Meisterschaftsproblem mit 3-Punkte-Regel, Zusammenfassung NP-Vollständigkeitstheorie, Einführung in Teil 2 der Vorlesung, die Entscheidbarkeitstheorie: Universelle Turingmaschine, Turing-Berechenbarkeit, rekursive und rekursiv aufzählbare Sprachen, churchsche These, Diagonalsprache, Halteproblem, Entscheidbarkeitsreduktionen
• 24.5.2005: Universelle Sprache, spezielles Halteproblem, Satz von Rice, Abschlusseigenschaften, postsches Korrespondenzproblem
• 31.5.2005: Unentscheidbarkeitsbeweis für postsches Korrespondenzproblem vervollständigen, Busy-Beaver-Problem, Anmerkungen zum Test und zu mündlichen Prüfungen, Einführung endliche Automaten
• 2.6.2005: Weitere Beispiele für DFAs, Pumping-Lemma
• 7.6.2005: Weitere Anwendung des Pumping-Lemmas, erweitertes Pumping-Lemma, Minimierung von DFAs
• 9.6.2005: Korrektheit des Ansatzes zur Minimierung, nichtdeterministische endliche Automaten: Definition und Beispiele
  
• 14.6.2005: Potenzmengenkonstruktion, Vermeidung der Konstruktion überflüssiger Zustände, Leerheitsproblem, Vollständigkeitsproblem, Endlichkeitstest, Abschlusseigenschaften von regulären Sprachen
• 16.6.2005: Weitere Abschlusseigenschaften, reguläre Ausdrücke, Beweis, dass die regulären Ausdrücke die regulären Sprachen beschreiben
• 21.6.2005: Abschluss gegen Substitution und inverse Homomorphismen, Einführung Grammatiken, Chomsky-Hierarchie, Simulation von TMs durch Chomsky-0-Grammatiken
• 23.6.2005: Simulation von Chomsky-0-Grammatiken durch NTMs und DTMs, Zusammenhang zwischen regulären Sprachen und Chomsky-3-Sprachen, Beispiele für kontextfreie Sprachen, Syntaxbäume, Umformung in Chomsky-Normalform (Schritte 1 und 2)
• 28.6.2005: Umformung in Chomsky-Normalform (Schritte 3 und 4), CYK-Algorithmus, Pumping-Lemma mit Anwendungen und Beweis
• 30.6.2005: Ogdens Lemma mit Beweis und Anwendungen, Beweis der inhärenten Mehrdeutigkeit einer Sprache, Entfernen nutzloser Variablen, Test, ob eine durch eine kontextfreie Grammatik gegebene Sprache leer bzw. endlich ist
• 5.7.2005: Abschlusseigenschaften kontextfreier Sprachen, Unentscheidbarkeitsresultate für kontextfreie Sprachen
• 7.7.2005: Weitere Unentscheidbarkeitsresultate, Überblick über die Klassen der Chomsky-Hierarchie und ihre Eigenschaften, Greibach-Normalform
• 12.7.2005: Vervollständigung des Algorithmus für die Umformung in Greibach-Normalform, NPDAs, Akzeptanzmodi von NPDAs, Umformung von NPDAs, die mit akzept. Zuständen akzeptieren, in NPDAs, die mit leerem Stack akzeptieren
• 14.7.2005: Umformung von PDAs, die mit leerem Stack akzeptieren, in PDAs, die mit akzeptierenden Zuständen akzeptieren; Beweis, dass die NPDAs genau die kontextfreien Sprachen erkennen; weitere Abschlusseigenschaften von kontextfreien Sprachen
• 19.7.2005: Abschluss der deterministisch kontextfreien Sprachen gegen Komplementbildung, ein Beispiel für eine kontextfreie, aber nicht deterministisch kontextfreie Sprache, LR(k)-Grammatiken und der Shift-Reduce-Parser, Konstruktion von Parsern mit Parser-Generatoren
• 21.7.2005: Weitere Beispiele zur Konstruktion von Parsern mit bison (die verwendeten Dateien sind hier erhältlich), Eigenschaften kontextsensitiver Sprachen

Vorlesungsfolien

Übungsgruppen

Übungsblätter

Prüfungsfragen

Sonstiges