Formale Sprachen und KomplexitätFormal Languages and Complexity

Die aktuellen Folien sind im Unterverzeichnis Material verfügbar.

Es wird auch auf die Unterlagen von Hans Jürgen Ohlbach aus dem Sommersemester 2017 hingewiesen, die für das Verständnis des Stoffes dieser Vorlesung hilfreich sein können, siehe hierfür Punkt 8. Unterlagen auf der Webseite vom Sommersemester 2017.

Das Modul vermittelt Grundkenntnisse in den Gebieten Formale Sprachen, Berechenbarkeit und Komplexitätstheorie. In der Vorlesung werden u.a. Automatentheorie und Formale Sprachen, insbesondere die Chomsky-Hierarchie, reguläre Sprachen und endliche Automaten, kontextfreie Sprachen und Kellerautomaten, kontextsensitive Sprachen, Berechenbarkeit, insbesondere primitive Rekursion, Unentscheidbarkeit, rekursiv aufzählbare Probleme, Komplexitätstheorie am Beispiel der Klassen P und NP sowie NP-Vollständigkeit eingeführt.

Eine detaillierte Inhaltsangabe wird im Laufe der Vorlesung aktualisiert.

Die Modulprüfung besteht aus einer Semestralklausur. Gasthörer und Studierende im Seniorenstudium sind nicht berechtigt, an der Modulprüfung teilzunehmen.

In den Übungen kann ein Notenbonus erworben werden. Hierzu müssen alle mit schriftlich bearbeiten gekennzeichneten Übungsaufgabe sinnvoll bearbeitet werden. Für jedes sinnvoll bearbeitete Übungsblatt köonnen 1% Bonuspunkte (bzgl. der in der Klausur zur erwerbenden Punkte) erworben werden, jedoch maximal 5%.

Ein erworbener Notenbons kann nur auf eine bestandene Klausur angerechnet werden. Die beste erreichbare Note bleibt allerdings 1,0. Dieser Notenbonus ist nur in der Semestralklausur und in der Wiederholungsklausur zu diesem Modul im Sommersemester 2018 anwendbar.

Zur Teilnahme an einer Klausur ist eine vorherige elektronische Platzreservierung verbindlich. Diese dient organisatorischen Zwecken und ist keine Zulassung und keine Anmeldung im Sinne einer Prüfungsordnung.

• Wer keinen Platz reserviert hat, kann nicht teilnehmen.
• Wer einen Platz reserviert hat und nicht teilnimmt, hat die Prüfung nicht bestanden.
• Nicht bestandene Püfungen werden in den Notentranskripts dokumentiert.

Details dazu finden sich in der Neuregelung für die Dokumentation der Prüfungen durch den Institutsvorstand.

Hürsaalzuteimung für die Klausur:

• Hörsall B201: Nachname A-K
• Hörsall B101: Nachname L-Z

Studierende, die eine individuelle Zuordnung für die Klausur zu einem Hörsaal bekommen haben, finden sich bitte in dem individuell mitgeteilten Hörsaal ein.

Informationblatt	vom
Informationsblatt 1	Mittwoch, 12.04.2018 (aktualisiert)
Informationsblatt 2	Mittwoch, 27.06.2018
Informationsblatt 3	Mittwoch, 22.06.2018

In der Regel erscheint jede Woche montags ein Übungsblatt. Dieses ist eine Woche vor Abgabe hier zugänglich und wird in den folgenden Übungsstunden behandelt.

Die aktuellen Fassungen sind auf Backstage verfügbar. Aus technischen Gründen können Aktualisierungen hier nur verspätet nachgezogen werden.

Übungsblatt	Abgabe bis	Lösungsskizze
Tutoriumsblatt 1		Tutoriumsblatt 1
Übungsblatt 1	Mo, 23.04.2018, 8:00	Übungsblatt 1
Tutoriumsblatt 2		Tutoriumsblatt 2
Übungsblatt 2	Mo, 07.05.2018, 8:00	Übungsblatt 2
Tutoriumsblatt 3		Tutoriumsblatt 3
Übungsblatt 3	Mo, 14.05.2018, 8:00	Übungsblatt 3
Tutoriumsblatt 4		Tutoriumsblatt 4
Übungsblatt 4	Mo, 28.05.2018, 8:00	Übungsblatt 4
Tutoriumsblatt 5		Tutoriumsblatt 5
Übungsblatt 5	Mo, 04.06.2018, 8:00	Übungssblatt 5
Tutoriumsblatt 6		Tutoriumsblatt 6
Übungsblatt 6	Mo, 11.06.2018, 8:00	Übungssblatt 6
Tutoriumsblatt 7		Tutoriumsblatt 7
Übungsblatt 7	Mo, 18.06.2018, 8:00	Übungssblatt 7
Tutoriumsblatt 8		Tutoriumsblatt 8
Übungsblatt 8	Mo, 25.06.2018, 8:00	Übungssblatt 8
Tutoriumsblatt 9		Tutoriumsblatt 9
Übungsblatt 9	Mo, 02.07.2018, 8:00	Übungssblatt 9
Tutoriumsblatt 10		Tutoriumsblatt 10
Übungsblatt 10	Mo, 09.07.2018, 8:00	Übungssblatt 10
Tutoriumsblatt 11		Tutoriumsblatt 11
Übungsblatt 11	Mo, 16.07.2018, 8:00	Übungssblatt 11

Buch zur Vorlesung:

• Uwe Schöning: Theoretische Informatik — kurzgefasst, Spektrum Akademischer Verlag, Heidelberg, 5. Auflage, 2008, ISBN 978-3-8274-1824-1.

Ergänzende Literatur:

• John E. Hopcroft, R. Motwani, and J. D. Ullmann: Introduction to Automata Theory, Languages, and Computation, Pearson Education Limited, Third Edition, 2013, ISBN 978-129203905-3.
  In Deutsch: Einführung in Automatentheorie, Formale Sprachen und Berechenbarkeit, Pearson Studium, 3. Auflage, 2011, ISBN 978-386894082-4
• Ingo Wegener: Theoretische Informatik — Eine algorithmenorientierte Einführung, Teubner-Verlag, 3. Auflage, 2005. ISBN 978-3835100336
• Ingo Wegener: Kompendium Theoretische Informatik — Eine Ideensammlung, Teubner Verlag, 1996, ISBN 978-3519021452