Nach positiver Absolvierung der Lehrveranstaltung sind Studierende in der Lage, die fundamentalen Konzepte und Resultate der Automatentheorie und formalen Sprachen, der Berechenbarkeits- und Komplexitätstheorie sowie der formalen Semantik von Programmiersprachen zu verstehen. Die Studierenden besitzen die Fähigkeit, formale Beschreibungen lesen und verstehen und Konzepte formal-mathematisch beschreiben zu können. Sie verstehen die Struktur von Beweisen und Argumentationen und können selber solche führen. Insbesondere verstehen Studierende das abstrakte Konzept der Problemreduktion und können Reduktionsbeweise in den Kontexten der Lehrveranstaltung führen. Sie sind in der Lage, Fragestellungen im Rahmen der theoretischen Informatik selbständig zu bearbeiten und zu lösen. Weiters können die Studierenden ethische Fragestellungen im Kontext dieser Lehrveranstaltung identifizieren, formulieren und diskutieren.

Die Lehrveranstaltung behandelt die grundlegenden Konzepte und Resultate der folgenden Gebiete.

Automatentheorie: deterministische und nichtdeterministische Automaten, Kellerautomaten, Turing-Maschinen
Formale Sprachen: reguläre und kontextfreie Sprachen, Chomsky Hierarchie
Berechenbarkeit und Komplexität: universelle Berechenbarkeit, Komplexitätsklassen wie Unentscheidbarkeit und NP-Vollständigkeit
Formale Semantik von Programmiersprachen: operationale und axiomatische Semantik

Zweimal wöchentlich werden die Lehrveranstaltungsinhalte im Hörsaal präsentiert und relevante Aufgaben und Beispiele diskutiert. Im Lauf des Semesters bearbeiten die Studierenden vier Übungsblätter mit Aufgaben zu den Themengebieten. Ein bis zwei Wochen nach Abgabe der Lösungen erhalten die Studierenden eine Rückmeldung zur Korrektheit ihrer Lösungsversuche sowie Zugang zu Musterlösungen. Fragen werden im Anschluss an die Vorlesung, online im TUWEL-Forum, per E-Mail und in gesonderten Fragestunden beantwortet.

Aufwandsabschätzung

 50h Vorlesung/Übung im Hörsaal
 50h Übungsblätter
 50h Vorbereitung auf den Abschlusstest
---------------------------------------
150h = 6.0 Ects

Die Gesamtbeurteilung ergibt sich aus den Leistungen, die bei vier Übungsblättern (zusammen max. 40 Punkte) sowie beim schriftlichen Abschlusstest (max. 60 Punkte) erbracht werden. Insgesamt können somit 100 Punkte erzielt werden. Für eine positive Gesamtbeurteilung sind mindestens 30 Punkte beim Abschlusstest und eine Gesamtpunkteanzahl von mindestens 50 notwendig. Positive Noten ergeben sich aus der Gesamtpunktezahl nach folgendem Schlüssel:

• 50-61 Punkte: genügend (4)
• 62-74 Punkte: befriedigend (3)
• 75-87 Punkte: gut (2)
• 88-100 Punkte: sehr gut (1)

Grundlegende Kenntnisse der mathematischen Argumentation, der Algorithmik und der Modellierung mit Hilfe von Automaten und formalen Sprachen.