Inhalt der Vorlesung

• 4.4.2006: 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.
• 6.4.2006: Registermaschinen, algorithmische Komplexität, Turingmaschinen,  Sonderrolle polynomieller Rechenzeiten.
• 11.4.2006: Komplexitätsklasse P, Wiederholung einiger Grundlagen zur Wahrscheinlichkeitstheorie,  Randomisierte Algorithmen: Einführung und Beispiel
• 13.4.2006: Komplexitätsklassen für randomisierte Algorithmen, Probability Amplification
  
• 18.4.2006: Komplementbildung, Zusammenhänge zwischen den Komplexitätsklassen für randomisierte Algorithmen, Nichtdeterminismus, NP
• 20.4.2006: Turing-Reduktionen, Vergleich verschiedener TSP-Varianten, Cliquen-Problem, Reduktion von Clique_opt auf Clique_dec und BinPacking_opt auf BinPacking_dec, Vergleich der verwandten Probleme DHC, HC, TSP
• 25.4.2006: Reduktionen zwischen  SAT-Varianten, Partition, Bin Packing, Clique, Independent Set, Vertex Cover,
  
• 27.4.2006: Polynomielle Reduktionen und ihre Eigenschaften, Einführung NP-Vollständigkeitstheorie, Rate-Verifikations-NTMs, Charakterisierung von NP, stereotype Turingmaschinen
• 2.5.2006: Simulation von Turingmaschinen durch stereotype Turingmaschinen, Satz von Cook, Zusammenfassung, Reduktion von 3-SAT auf Subset Sum
• 4.5.2006: Korrektheitsbeweis zur Reduktion von 3-SAT auf Subset Sum, NP-Vollständigkeit des Rucksackproblems, sowie von Partition, Bin Packing, Sequencing with Intervals, Teilgraphisomorphie und Graphfärbbarkeit. Zusammenfassung Komplexitätstheorie
• 9.5.2006: Entscheidbarkeitstheorie: Universelle Turingmaschine, Begriffe Turing-berechenbar, rekursiv, rekursiv aufzählbar, churchsche These, Halteproblem, Diagonalsprache, Diagonalisierung, Entscheidbarkeitsreduktionen, die universelle Sprache, das spezielle Halteproblem
• 11.5.2006: Satz von Rice, Abschlusseigenschaften von rekursiven und rekursiv aufzählbaren Sprachen, das postsche Korrespondenzproblem, die Reduktion von MPKP auf PKP
• 16.5.2006: Die Reduktion von H auf PKP, endliche Automaten: Grundlagen und einführende Beispiele
• 18.5.2006: Das Pumping-Lemma für reguläre Sprachen, Minimierung von DFAs: Entfernen nicht erreichbarer Zustände, Äquivalenzklassenautomat
• 23.5.2006: Algorithmus zur Berechnung des Äquivalenzklassenautomaten, Beweis, dass der Äquivalenzklassenautomat minimal ist
• 30.5.2006: Nichtdeterministische endliche Automaten, Beispiele, Potenzmengenkonstruktion, Vermeidung überflüssiger Zustände, Leerheits- und Vollständigkeitsproblem für DFAs und NFAs
  
• 1.6.2006: DFAs und NFAs: Endlichkeitstest, Abschluss gegen Komplementbildung, Vereinigung, Durchschnitt, symmetrische Differenz, Konkatenation, kleenescher Abschluss, Äquivalenztest für DFAs, reguläre Ausdrücke, Beweis, dass die regulären Ausdrücke genau die regulären Sprachen beschreiben
• 6.6.2006: endliche Sprache, Zusammenfassung reguläre Sprachen, Grammatiken, Chomsky-Sprachen, rekursiv aufzählbare Sprachen und Chomsky-0-Sprachen, reguläre Sprachen und Chomsky-3-Sprachen, einfache Beispiele für kontextfreie Sprachen
• 8.6.2006: Weitere Beispiele, Eindeutigkeit, Chomsky-Normalform, Umformung einer kontextfreien Grammatik in Chomsky-Normalform, der Cocke-Younger-Kasami-Algorithmus
• 13.6.2006: Informationen zu Prüfungen, das Pumping-Lemma für kontextfreie Sprachen, Ogdens Lemma, Anwendungen
• 20.6.2006: Entfernen nutzloser Variablen, Leerheits- und Endlichkeitstest für kontextfreie Sprachen, Abschlusseigenschaften, Unentscheidbarkeitsresultate für das Schnitt- und Mehrdeutigkeitsproblem, Überblick über Eigenschaften von Chomsky-1-Sprachen, Zusammenfassung Chomsky-Hierarchie, Greibach-Normalform
• 22.6.2006: Umformung in Greibach-Normalform, NPDAs, Vergleich der Akzeptanzmodi von NPDAs
• 27.6.2006: Konstruktion von NPDAs aus kontextfreien Grammatiken, Tripelkonstruktion, Einführung LR(k)-Grammatiken
• 29.6.2006: Arbeitsweise von LR(k)-Parsern, Erzeugung von LR-Parsern mit bison
• 4.7.2006: Einführung in lineare Programmierung, geometrische Grundlagen des Simplex-Algorithmus
  
• 6.7.2006: Weitere Grundlagen der linearen Programmmierung
• 11.7.2006: Simplex-Algorithmus
• 13.7.2006: Randomisiertes Runden
  

Vorlesungsfolien

Übungsgruppen

Übungsblätter

Prüfungen

Sonstiges