Vorlesungs-Folien
H. Peter Gumm: Theoretische Informatik
Vorlesungsfolien Sommer 2008
- Organisatorisches
- Inhalt
- Literatur
- Organisatorisches
- Übungen, Klausur, Credits
- Überblick
- Der Aufbau von Sprachen
- Compiler
- Berechenbarkeit
- Komplexität
- Alphabete, Worte, Sprachen
- Alphabete, Worte
- Sprachen
- Spracherkennung
- Entscheidbarkeit
- Reguläre Sprachen
- Reguläre Ausdrücke
- Gleichungen
- Syntaxdiagramme
- Erweiterungen und Anwendungen
- Deterministische Automaten
(Druckversion)
- Akzeptoren
- Homomorphismen, Faktoren
- Trennbarkeit, Nerode Kongruenz
- Pumping Lemma, Grenzen von Automaten
- Minimierung
- Nichtdeterministische Automaten
(Druckversion)
- Nichtdeterminismus
- Epsilon-Transitionen
- Akzeptanz
- Vom NFA zum DFA
- Äquivalenz
- Regulärer Ausdruck ==> NFA
- DFA ==> Regulärer Ausdruck
- Äquivalenzsatz
- flex
- Kontextfreie Sprachen und Parser
- Grammatiken und Parser
- Stack-Automaten
- Parserstrategien
- Recursive Descent Parser und LR-Parser
- Berechenbarkeit
- Turingmaschinen
- LOOP, While, Goto-Programme
- Primitive Rekursion, µ-Rekursionm
- Halteproblem, Satz von Rice
- Komplexitätstheorie
- Nichtdeterministisch polynomiale Probleme
- SAT ist NP-hart
- Polynomiale Reduzierbarkeit
- NP-vollständige Probleme