Informationen zur Vorlesung

Wintersemester 2004

Inhalt

Ziel der Vorlesung ist es, die grundlegenden Denkweisen, Methoden und Ergebnisse der wichtigsten Teilbereiche der Theoretischen Informatik vorzustellen. Wichtigkeit messen wir dabei zum einen anhand des Stellenwertes innerhalb der Theoretischen Informatik (Dinge, die jeder Informatiker wissen sollte), zum anderen anhand ihrer Bedeutung für andere Teilbereiche der Informatik. Wir werden uns mit folgenden Teilgebieten befassen:

•  Berechenbarkeit
  •  Turingmaschinen
  •  entscheidbare und rekursiv aufzählbare Sprachen
  •  nicht entscheidbare Probleme
  •  Halteproblem
  •  nicht rekursiv aufzählbare Probleme
    
    
•  Komplexitätstheorie
  •  Klassen P und NP, Zeitkomplexität
  •  NP-Vollständigkeit
  •  Satz von Cook
  •  Reduktion
    
    
•  Algorithmen: Behandlung NP-vollständiger Probleme
•  Heuristiken: Backtracking, Branch and Bound
•  Approximationsalgorithmen
  
  
•  Formale Sparchen
  •  reguläre Sprachen, reguläre Grammatiken
  •  deterministische und nicht-deterministische Automaten
  •  reguläre Ausdrücke
  •  Äquivalenzsatz
  •  Pumping Lemma
  •  kontextfreie Sprachen, kontextfreie Grammatiken
  •  Kellerautomaten
  •  Chomsky Normalform, Äquivalenzsatz
  •  CYK-Algorithmus

Organisation

Die Unterlagen finden sie im Bereich Skript und weiterführende Literatur im gleichnamigen Abschnitt. Aufgaben, die sie zur Übung lösen sollen und entsprechende Abgabezeiten werden ihnen im Bereich Übungen in verschiedenen Formaten zum download angeboten. Informationen zum zeitlichen Vorlesungsablauf und der Übungsgruppen finden sie im Bereich Termine. Kurzfristige Änderungen, wie Vorlesungs- oder Übungsausfall und noch nicht feststehende Termine, wie z.B. Prüfungstermine finden sie im Newsbereich.