Sprungmarken

Servicenavigation

       

Hauptnavigation

Bereichsnavigation

Grundvorlesung Grundbegriffe der theoretischen Informatik

Grundvorlesung

"Grundbegriffe der theoretischen Informatik"

Sommersemester 2005

 
Veranstalter:
Detlef Sieling
Termin:
Dienstag, 10.15-12.00 Uhr, EF50, HS1


Donnerstag, 10.15-12.00 Uhr, Audimax
Beginn der Vorlesung: 
12.4.2005
Übungen:

André Gronemeier, Martin Scholz, Tobias StorchPhilipp Wölfel

Vorlesungsankündigung mit Literaturangaben

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 Cliqueopt auf Cliquedec und BinPackingopt auf BinPackingdec, 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
Nicht prüfungsrelevant sind die Gebiete LR(k)-Grammatiken und bison (Folien 693-722).

Vorlesungsfolien

Die verwendeten Vorlesungsfolien sind hier erhältlich. In den mit "klein" bezeichneten Dateien sind jeweils vier Folien auf einem Blatt angeordnet.

Übungsgruppen

1
Mo, 10.15-12.00
ZB B, rechts
Jan Salmen
2
Mo, 10.15-12.00 GB 4, 228
Tobias Storch
3
Mo, 10.15-12.00 GB 4, 13
Desiree Kraus
4
Mo, 12.15-14.00 ZB B, rechts
Thomas Rothvoß
5
Mo, 12.15-14.00 GB 4, 228
Tobias Storch
6
Mo, 12.15-14.00 GB 4, 13
Matthias Niewerth
7
Mi, 8.15-10.00
ZB B, rechts
Thomas Rothvoß
8
Mi, 8.15-10.00
GB 4, 228
Martin Scholz
9
Mi, 10.15-12.00
ZB B, rechts
Desiree Kraus
10
Mi, 10.15-12.00
GB 4, 228
Martin Scholz
11
Fr, 8.15-10.00
GB 4, 318
Matthias Niewerth
12
Fr, 12.15-14.00
GB 5, 420
Jan Salmen


Übungsblätter

Die Übungsblätter sind hier erhältlich.

Prüfungsfragen

Beispiele für Prüfungsfragen sind hier erhältlich.

Sonstiges

Im Informatik-Portal gibt es ein Forum zur GTI Vorlesung.



21.7.2005 - Detlef Sieling