Vorlesung
Theoretische Informatik

Dozent

Übungen: Pascal Bormann, Nikita Balychew, Vivian Erbenich

SWS (CP)

Prüfung

Vorleistung

Termine

Thema

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