Grundlagen der Theoretischen Informatik

Dozent: Prof. Dr. Heribert Vollmer

Frequenz: jährlich im Wintersemester, empf. 3. Semester

Veranstaltungsart: Vorlesung und Übung (2V + 2Ü, 5 LP)

Prüfung: Klausur

Das Modul vermittelt grundlegende Kenntnisse über theoretische Modelle und Konzepte der Informatik. Nach erfolgreichem Abschluss der LV können die Studierenden Probleme in die Chomsky-Hierarchie einordnen. Sie beurteilen die zugehörigen Modelle, wie endliche Automaten, Grammatiken und Turingmaschinen. Sie beurteilen und analysieren algorithmische Probleme hinsichtlich ihrer Berechenbarkeit. Sie entwerfen Grammatiken oder Automaten und Transformationen zwischen diesen sowie entwickeln Einstufungen durch Anwendung des Pumping-Lemma sowie Reduktionen.

Gliederung:

• Sprachen und Grammatiken

• Die Chomsky-Hierarchie

• Reguläre Sprachen

• Kontextfreie Sprachen

• Typ-1- und Typ-0-Sprachen

• Der intuitive Berechenbarkeitsbegriff

• Berechenbarkeit durch Maschinen

• Berechenbarkeit in Programmiersprachen

• Die Church'sche These

• Entscheidbarkeit und Aufzählbarkeit

• Unentscheidbare Probleme

Die Abschlussprüfung des Moduls ist eine schriftliche Klausur über 90 Minuten.

Termin

Die Prüfungstermine finden Sie im zentralen Webauftritt der Universität (siehe Link unten).

Anmeldung

Je nach Prüfungsordnung ist eine Anmeldung im QIS erforderlich (siehe Link unten). Zur Teilnahme als Zulassungsauflage benötigen Sie keine Anmeldung.

Hilfsmittel

Erlaubtes Hilfsmittel ist ein (beidseitig) beschriebenes oder bedrucktes DIN A4-Blatt. Sie benötigen kein eigenes Papier!

Klausurbonus

Die Modalitäten für das Erreichen eines Klausurbonus werden zu Beginn des neuen Semesters bekanntgegeben.

Studienleistung

Die Modalitäten für das Erreichen der Studienleistung werden zu Beginn des neuen Semesters bekanntgegeben.