Zielgruppe
Studierende des Bachelorstudiengangs Informatik im 2. Semester.
Form
Vorlesung (2 SWS) und Übung (2 SWS)
Inhalte
- Automatentheorie & Formale Sprachen
-
Im ersten Kapitel wird die allgemeine Form eines Problems i.S.d. Informatik eingeführt: Formale Sprachen und die Frage der Zugehörigkeit einer Zeichenkette zu einer solchen (Wortproblem). Die Untersuchung von Automatenmodellen, welche das Wortproblem für bestimmte Klassen von formalen Sprachen lösen können führt an den Begriff der allgemeinen Berechenbarkeit heran. Konkrete Anwendungen der Ergebnisse dieser Untersuchung finden sich z.B. im Compilerbau (Lexer und Parser) und im Patternmatching (reguläre Ausdrücke) sowie allgemein in der Modellierung.
- Berechenbarkeit
- Churchsche These
- Loop- und While-Berechenbarkeit
- Unentscheidbarkeit des Halteproblems
- primitiv-rekursive und mü-rekursive Funktionen
- Ackermann-Funktion
- Komplexitätstheorie
- O-Notation
- Komplexitätsklassen
- P/NP-Problem
- NP-Vollständigkeit, NP-vollständige Probleme
Literatur
U. Schöning,Theoretische Informatik -kurz gefasst, 5. Auflage 2009
D. W. Hoffmann, Theoretische Informatik, 5. Auflage
A. Schulz, Grundlagen der Theoretischen Informatik