Grundlagen der Theoretischen Informatik
(engl. Introduction to the Theory of Computation)
Modulnummer: FIN-INF-110105 |
| Link zum LSF: | LSF |
| Verantwortung: | Prof. Dr. Stefan Schirra |
| Dozent:in: | Prof. Dr. Stefan Schirra |
| Lehrveranstaltungen: |
|
| Verwendbarkeit: |
|
Kürzel GThI |
CP 5 |
Semester Winter |
Fachsem. ab 3. |
Dauer 1 Semester |
Sprache deutsch |
Niveau Bachelor |
Angestrebte Lernergebnisse:
- Grundlagen von Automatentheorie und formalen Sprachen zur Problemlösung
- Fähigkeit, Probleme hinsichtlich Berechenbarkeit und Komplexität einordnen zu können
Inhalt:
- Einführung in Formale Sprachen (reguläre und kontextfreie Sprachen, Grammatiken),
- elementare Automatentheorie (endliche Automaten, Kellerautomaten),
- Berechnungsmodelle und Churchsche These,
- Entscheidbarkeit und Semi-Entscheidbarkeit,
- Komplexitätsklassen P und NP, NP-Vollständigkeit
Arbeitsaufwand:
- 70h Präsenzzeit
- 80h selbstständige Arbeit
| Studien-/Prüfungsleistungen: | Lehrform / SWS: |
|
Prüfungsvorleistung: Erfolgreiche Teilnahme an den Übungen (s. Vorlesung)
Klausur 120 Minuten |
|
| Voraussetzungen nach Prüfungsordnung: | Empfohlene Voraussetzungen: |
|
keine |
|
| Medienformen: | Literatur: |
|
|
|
Hinweise: