Qualifikationsziele: Die Studierenden können algorithmische Probleme als formale Sprachen darstellen und deren Eigenschaften be-nennen. Sie sind in der Lage, verschiedene Darstellungen von regulären Sprachen ineinander umzuwandeln oder zu interpretieren oder zu einer gegebenen Beschreibung eine geeignete Darstellung als reguläre Sprache anzu-geben oder zu argumentieren, dass eine solche nicht existiert. Sie können Turing-Maschinen zu elementaren al-gorithmischen Problemen angeben und das Phänomen der Berechenbarkeit diskutieren. Sie können gegebene algorithmische Probleme auf ihre (Semi-)Entscheidbarkeit untersuchen4 und das Ergebnis formal begründen. Sie sind in der Lage, zu einer gegebenen Beschreibung eine kontextfreie Grammatik anzugeben oder die Nichtexistenz einer kontextfreien Grammatik zu begründen oder gängige Verfahren für kontextfreie Grammatiken anzuwenden oder zu interpretieren. Sie sind in der Lage, algorithmische Probleme auf ihre Komplexität zu untersuchen und durch Reduktionen zueinander in Beziehung setzen.

Inhalte: Studierende lernen formale Sprachen und verschiedene algorithmische Probleme kennen und üben exemplarisch deren Anwendung. Darüber hinaus erlernen sie reguläre Sprachen, erarbeiten sich einzelne Darstellungsformen und diskutieren ihre grundlegenden Eigenschaften. Sie lernen Turing-Maschinen kennen, erarbeiten sich Entscheid-barkeit und Semi-Entscheidbarkeit, die Church-Turing-These, sowie Reduktionen und üben deren Anwendung. Zu-letzt erlernen sie einzelne formale Grammatiken, Chomsky-Hierarchie, kontextfreie Sprachen und die Theorie der NP-Vollständigkeit.