Teilmodul Grundlagen der Theoretischen Informatik B Kurs 01658 |
| Inhalt: |
Anschließend an den Kurs 01657 gibt dieser Kurs eine Einführung in Berechnungskomplexität und formale Sprachen.
Im ersten Teil werden die Komplexitätsmaße Zeit und Speicherplatz, untere und obere Schranken für die Komplexität von Problemen und Komplexitätsklassen eingeführt sowie Hierarchiesätze hergeleitet. Mit einer Behandlung des P-NP-Problems (nichtdeterminierte Maschinen und Komplexitätsklassen, NP-vollständige Probleme) schließt dieser Teil. Im zweiten Teil werden die Sprachen der Chomsky-Hierarchie behandelt mit besonderem Augenmerk auf reguläre Mengen und (deterministisch) kontextfreie Sprachen. |
| Qualifikationsziele: |
| Nach erfolgreicher Teilnahme an dem Kurs können die Studierenden mit Komplexitätsmaßen umgehen, Probleme Komplexitätsklassen zuordnen und bei schwierigen Problemen einschätzen, ob sie NP-vollständig sind. Sie können mit Grammatiken und erkennenden Automaten umgehen und formale Sprachen den entsprechenden Klassen zuordnen. |
| Literatur: |
- J. Hopcroft, J. Ullman, Einführung in die Automatentheorie, Formale Sprachen ... , Addison-Wesley, Bonn, 1988
- K. Wagner, Einführung in die Theoretische Informatik, Springer, Berlin, 1994
- M. Sipser, Introducton to the theory of computation, Brooks/Cole, London, 1997
|
| Lehrform: |
| Kurs mit Übungen (2+1 SWS) und freiwilligen Studientagen. Im Kurstext gibt es Übungsaufgaben mit Lösungen in denen die Begriffe und Verfahren des Kurstextes an Beispielen vertieft werden; außerdem werden individuell korrigierte Einsendeaufgaben angeboten. An den Studientagen wird ein kompakter Überblick über die Kursinhalte gegeben und es werden unter Anleitung Aufgaben gelöst. |
| Arbeitsaufwand: | Leistungspunkte: | Stellenwert Note der Modulprüfung für die Endnote: |
| 150 Stunden | 5 | |
| Art der Prüfung: |
| s. Gesamtmodul |
| Inhaltliche Voraussetzungen: |
| Kurs 01657 |
| Häufigkeit: | Dauer: |
| Jährlich im Sommersemester | 1 Semester |
| Modulverantwortliche: | Lehrende: |
| Rutger Verbeek | Rutger Verbeek |
