Illustrationsbild für den Virtuellen Studienplatz

Lehrveranstaltung 63912 (WiSe 24/25)

 
63912 Grundlagen der Theoretischen Informatik im Wintersemester 2024/2025
grundlegende Überarbeitung: Sommersemester 2019 Umfang: 10.0 ECTS
nächster geplanter Einsatz: -keine Angaben vorhanden- Versionen
Autorinnen und Autoren Teilnahmevoraussetzungen
Beschreibung
Schließen
Beschreibung
KursbeschreibungDiese Lehrveranstaltung beschäftigt sich mit den Grundlagen für das Arbeiten mit formalen Berechnungsmodellen. Es werden hierzu formale Sprachen auf Grundlage der Chomsky Hierarchie untersucht. Zu jeder Klasse in der Chomsky Hierarchie wird ein abgeleitetes Berechnungsmodell vorgestellt und diskutiert (Endlicher Automat, Kellerautomat, Turingmaschine). In diesem Zusammenhang werden unter anderem folgende Themen behandelt: Minimierung Endlicher Automaten, Überführung von Regulären Ausdrücken, Äquivalenz von kontextfreien Grammatiken und Kellerautomaten, Beweis und Anwendung des Pumpinglemmas (regulär und kontextfrei), und anderes. Es wird ausführlich auf das Konzept der Nichtberechenbarkeit eingegangen. Außerdem wird eine Einführung in die Komplexitätstheorie gegeben. In diesem Zusammenhang werden die Komplexitätsmaße Zeit und Speicherplatz eingeführt. Abschließend wird das P-vs-NP-Problem und die NP-Vollständigkeitstheorie eingehend behandelt.
Termine
Veranstaltungsbeginn: 01.10.2024
Versand
Material
Hinweis Diese Lehrveranstaltung beinhaltet zugriffsgeschütztes Material, das nur nach dem Login eingesehen werden kann.
Einheiten Einstieg
Moodle Umgebungen
Betreuung
Betreuende Liste der Campus Standorte bzw. Studienzentren
Zusatzveranstaltungen
Hinweis Die zu dieser Lehrveranstaltung angebotenen Zusatzveranstaltungen werden Teilnehmern nach dem Login angezeigt.

Irrtümer und nachträgliche Datenänderungen vorbehalten.


Seite erstellt in 0,2s  |  24.11.24,01:53 im Wintersemester 2024/2025  |  realisiert durch das LVU-System
FernUni-Logo FernUniversität in Hagen, 58084 Hagen, Telefon: +49 2331 987-01, E-Mail: fernuni@fernuni-hagen.de