Grundlagen der Theoretischen Informatik

  • Moduldetails

    Dozent: Prof. Dr. Heribert Vollmer

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

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

    Prüfung: Klausur

  • Vorlesungsinhalte

    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
  • Informationen zur Prüfung

    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.

Materialien

Alle Materialien finden Sie im Stud.IP.

Prüfungsanmeldung

Aktuelle Prüfungstermine
Online-Prüfungsanmeldung