INF.00882.08 - Automaten und Berechenbarkeit (Veranstaltungsübersicht)
INF.00882.08 - Automaten und Berechenbarkeit (Veranstaltungsübersicht)
INF.00882.08
Institut für Informatik
10 CP
Automaten und Berechenbarkeit
Lehrveranstaltungen SoSe 2024
Teilnahmevoraussetzungen
Modul "Mathematische Grundlagen der Informatik und Konzepte der Modellierung" (Besuch)
Prüfungsvorleistung Modul
Korrekte Bearbeitung der theoretischen Übungsaufgaben in Höhe von mindestens 60% der maximal erreichbaren Punkte, 5 Kurzvorträge über Lösungen von Übungsaufgaben
Prüfungsleistung Modul
mündl. Prüfung oder Klausur
Kompetenzziele
Studierende sollen durch dieses Modul die folgenden Kompetenzen erwerben:
Sie können Sprachen mit Automaten, Grammatiken und Regulären Ausdrücken formalisieren.
Sie können von einer Formalisierungsmethode zu einer anderen übersetzen und die Korrektheit beweisen. Die dabei verwendeten Konstruktionen können sie an Beispielen durchführen und mathematisch allgemein formalisieren.
Sie können Sprachen in der Chomsky-Hierarchie klassifizieren und Nichtzugehörigkeiten zu Klassen beweisen.
Sie kennen die Grenzen der Machbarkeit bezüglich der Berechenbarkeit und Komplexität und können Vollständigkeiten beweisen.