Illustrationsbild für den Virtuellen Studienplatz

Lehrveranstaltung 63912 (SoSe 24)

 
63912 Grundlagen der Theoretischen Informatik im Sommersemester 2024
Hinweis Das Semester dieser Veranstaltung ist beendet.
Die aktuell stattfindende Lehrveranstaltung mit gleicher Nummer erreichen Sie über diesen Link: 63912 Grundlagen der Theoretischen Informatik (WiSe 24/25).
grundlegende Überarbeitung: Sommersemester 2019 Umfang: 10.0 ECTS
nächster geplanter Einsatz: -keine Angaben vorhanden- Versionen
Autorinnen und Autoren Teilnahmevoraussetzungen
Beschreibung
Schließen
Beschreibung
KursbeschreibungDieser Kurs 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.04.2024
Material
Hinweis Diese Lehrveranstaltung beinhaltet zugriffsgeschütztes Material, das nur nach dem Login eingesehen werden kann.
Einheiten Einstieg
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,1s  |  10.10.24,03:32 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