[TZI]  [IAI]  [h-da]  [Faculty 3, Mathematics/Computer Science]  [University of Bremen] 

Vorlesungsfolien

Vorlesungsskript

Übungen

Programme

Vorlesung
Theoretische Informatik

Dozent

Stefan Edelkamp

Übungen: Pascal Bormann, Nikita Balychew, Vivian Erbenich

SWS (CP)

4+2 (7.5)

Prüfung

Klausur

Vorleistung

50% der Übungsaufgaben

Termine

3.3.- 30.6.2017, Montags 16-17:30, Dienstags 12-13:30

Thema

In dieser Vorlesung wird ein algorithmischer Zugang zur theoretischen Informatik gelegt. Inhaltsverzeichnis (auf Basis Ingo Wegeners Büchern "Theoretische Komplexität" sowie Uwe Schönings Buch "Theoretische Informatik - kurzgefasst")

Studienbrief 1: Einleitung und Landau'sche O-Notation

  • 1.1 Einleitung und Übersicht
  • 1.2 Beweisprinzipien und die reelen Zahlen
  • 1.3 O-Notation

Studienbrief 2: Turingmaschinen, churchsche These und Entscheidbarkeit

  • 2.1 Registermaschinen und deterministische Turingmaschinen
  • 2.2 Techniken zur Programmierung von Turingmaschinen
  • 2.3 Simulationen zwischen Turingmaschinen und Registermaschinen
  • 2.4 Universelle Turingmaschinen
  • 2.5 Die churchsche These
  • 2.6 Die Unentscheidbarkeit des Halteproblems

Studienbrief 3: Die NP-Vollständigkeitstheorie

  • 3.1 Die Komplexitätsklasse P
  • 3.2 Nichtdeterministische Turingmaschinen und die Komplexitätsklasse NP
  • 3.3 NP-Vollständigkeit
  • 3.4 Die NP-Vollständigkeit wichtiger Probleme

Studienbrief 4: Endliche Automaten

  • 4.1 Schaltwerke und endliche Automaten
  • 4.2 Die Minimierung endlicher Automaten
  • 4.3 Das Pumping-Lemma für endliche Automaten
  • 4.4 Nichtdeterministische endliche Automaten
  • 4.5 Effiziente Algorithmen für die Konstruktion endlicher Automaten und die Entscheidung von Eigenschaften regulärer Sprachen

Studienbrief 5: Grammatiken, die Chomsky-Hierarchie und das Wortproblem

  • 5.1 Grammatiken und die Chomsky-Hierarchie
  • 5.2 Chomsky-0-Grammatiken und rekursiv aufzählbare Sprachen
  • 5.3 Chomsky-3-Grammatiken, reguläre Sprachen und Ausdrücke, lexikalische Analyse
  • 5.4 Kontextsensitive Grammatiken und Sprachen

Studienbrief 6: Kontextfreie Grammatiken und Sprachen

  • 6.1 Beispiele kontextfreier Sprachen und Syntaxbäume
  • 6.2 Die Chomsky-Normalform für kontext freie Grammatiken
  • 6.3 Der Cocke-Younger-Kasami-Algorithmus
  • 6.4 Das Pumping-Lemma und Ogdens Lemma für kontextfreie Sprachen
  • 6.5 Effiziente Algorithmen für die Konstruktion kontextfreier Grammatiken und die Entscheidung von Eigenschaften kontextfreier Sprachen
  • 6.6 Unentscheidbare Probleme
  • 6.7 Eine inhärent mehrdeutige kontextfreie Sprache

Theoretische Informatik

Stefan Edelkamp (edelkamp@tzi.de)