Grundlagen der Theoretischen Informatik
Winter
(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: | - B.Sc. INF: Mathematik / Theoretische Informatik - B.Sc. CV: Mathematik / Theoretische Informatik - B.Sc. INGINF: Mathematik / Theoretische Informatik - B.Sc. WIF: Verstehen und Gestalten - Wahlpflicht - B.Sc. INF (bilingual): Mathematik / Theoretische Informatik |
|
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
| Prüfungsvorleistungen: | Studien-/Prüfungsleistungen: | Lehrform / SWS: |
|
Erfolgreiche Teilnahme an den Übungen, d.h. für je 4 aufeinanderfolgende Übungsblätter 50% der Aufgaben erfolgreich votieren (siehe moodle und Vorlesung) |
Klausur 120 Minuten (schriftliche Prüfung)
|
|
| Voraussetzungen nach Prüfungsordnung: | Empfohlene Voraussetzungen: |
|
keine
|
|
| Medienformen: | Literatur: |
|
|
|
Hinweise: