Grundlagen der Theoretischen Informatik

Inhalte:

Im ersten Lehrveranstaltungsteil wird mit Hilfe formaler Sprachen der Begriff der Berechenbarkeit entwickelt. Zunächst werden verschiedene Berechnungsmodelle vorgestellt, welche sich an der Chomsky-Hierarchie orientieren. Besonderes Augenmerk erfahren die regulären, kontextfreien und entscheidbaren Sprachen. Als Modelle werden der endliche Automat, der Kellerautomat und die Turingmaschine vorgestellt. Zudem wird auf das Konzept zur Beschreibung von Sprachen über Grammatiken vorgestellt. Dies führt zur Formulierung und Diskussion der Churchschen These.

Der zweite Lehrveranstaltungsteil widmet sich zuerst den nichtentscheidbaren Problemen. Hier werden wichtige Probleme, wie das Halteproblem, vorgestellt und wichtige Konsequenzen (Satz von Rice, Rekursionstheorem, Postsches Korrespondenzproblem) erläutert. Auch wird auf die Entscheidbarkeit von logischen Theorien eingegangen. In diesem Zusammenhang werden auch die Gödelschen Unvollständigkeitssätze diskutiert. Anschließend wird eine Einführung in die Komplexitätstheorie gegeben. In diesem Zusammenhang werden die Komplexitätsmaße Zeit und Speicherplatz eingeführt. Mit einer eingehenden Behandlung des P-vs-NP-Problems und der NP-Vollständigkeitstheorie schließt dieser Teil.

Qualifikationsziele:

Nach Bearbeiten des Modules 63912 können die Studierenden mit den wesentlichen Grundbegriffen (Berechenbarkeit, Entscheidbarkeit, Aufzählbarkeit) umgehen. Sie können mit formalen Sprachen arbeiten und diese wichtigen Klassen zuordnen (regulär, kontextfrei, entscheidbar). Sie kennen zudem Berechnungs - und Beschreibungsmodelle dieser Sprachklassen und können mit Komplexitätsmaßen umgehen, Probleme Komplexitätsklassen zuordnen und bei schwierigen Problemen einschätzen, ob sie NP - vollständig sind. Sie lernen, wie man zeigen kann, dass Probleme nicht berechenbar sind.

Moodle:

Die Lehrveranstaltung ist so angelegt, dass er aus der Moodle Lernumgebung zu benutzen ist. Dort sind alle wichtigen Informationen und Dokumente zusammenhängend aufgeführt, und im Nachrichtenforum können kurzfristige Ankündigungen abgerufen werden.

• Moodle Lernumgebung

Forum:

Für die Lehrveranstaltung haben wir ein Forum eingerichtet, welches im Gegensatz zu einem reinen Diskussionsforum als Frage und Antwort Forum organisiert ist. Alle Teilnehmenden sind aufgerufen nicht nur Fragen in dieses Forum zu stellen, sondern sich auch aktiv bei der Beantwortung von Fragen einzubringen. Die Nutzung des Forums erfordert eine Anmeldung. Sie müssen sich nicht mit ihrem Klarnamen anmelden (dürfen das aber).

Das Forum ist über Moodle zu erreichen.

Lesen Sie sich bitte auf den Webseiten des Forums die Richtlinien in den FAQs durch. Wer sich erfolgreich in die Betreuung des Forums einbringt, erhält Privilegien für die Moderation des Forums.

Ausführliche Beschreibung des Moduls (Inhalte, Zeitaufwand, Qualifikationsziele ... ):

• B.Sc. Informatik (Seite im Modulhandbuch als PDF-Dokument)
• B.Sc. Mathematik (Seite im Modulhandbuch als PDF-Dokument)
• M.Sc. Mathematik (Seite im Modulhandbuch als PDF-Dokument)

Anmerkung:

Das Modul wurde zum Wintersemester 2018/19 grundlegend überarbeitet. Bezüglich der Prüfungsmodalitäten beachten Sie bitte die Prüfungsinformationen.