|
|
 |
|
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. |
|
|
FernUniversität in Hagen, 58084 Hagen, Telefon: +49 2331 987-01, E-Mail: fernuni@fernuni-hagen.de