Skip to main content

Grundlagen der Theoretischen Informatik III

Winter

(B.Sc.)

(engl. Introduction to the Theory of Computation III )

Modulnummer: FIN-INF-110464

Kürzel

GThI 3

CP

5

Semester

Winter

Fachsem.

Dauer

1 Semester

Sprache

deutsch

Niveau

Bachelor

Link zum LSF: LSF
Zugang beschränkt: false
Verantwortung: Prof. Dr. Stefan Schirra
Dozent:in: Prof. Dr. Stefan Schirra
Lehrveranstaltungen:
  • Vorlesung Grundlagen der Theoretischen Informatik III
  • Übung Grundlagen der Theoretischen Informatik III
Verwendbarkeit: - B.Sc. INF: Informatik - Wahlpflicht
- B.Sc. INF: Informatik Wahlpflicht (SPO 2027)
- B.Sc. CV: Informatik - Wahlpflicht
- B.Sc. CV: Computervisualistik - Wahlpflicht
- B.Sc. CV: Computervisualistik Wahlpflicht (SPO 2027)
- B.Sc. INGINF: Informatik - Wahlpflicht
- B.Sc. INGINF: Informatik Wahlpflicht (SPO 2027)
- B.Sc. INF (bilingual): Informatik - Wahlpflicht
- B.Sc. INF (bilingual): Informatik Wahlpflicht (SPO 2027)

Angestrebte Lernergebnisse:
Studierende lernen, formale Sprachen in die Chomsky-Hierarchie einzuordnen und beurteilen zu können. Sie verstehen algebraische Zugänge zu Formalen Sprachen. Ferner lernen sie Optionen kennen, mit schweren Problemem umzugehen, und diese anzuwenden.

Inhalt:

  • Weiteres zu regulären und kontextfreien Sprachen,
  • Kleene Algebren,
  • Exakte Exponentialzeitalgorithmen,
  • Algorithmen für spezielle Graphklassen,
  • Festparameterhandhabbarkeit,
  • Approximationsalgorithmen und Nichatapproximierbarkeit
  • Elementare Komplexitätstheorie.

Arbeitsaufwand:
56h Präsenzzeit + 94h selbstständige Arbeit

Prüfungsvorleistungen: Studien-/Prüfungsleistungen: Lehrform / SWS:

Aktive Teilnahme an der Veranstaltung

Klausur (schriftlich) 120 Minuten

  • Vorlesung (3 SWS)
  • Übung (1 SWS)
Voraussetzungen nach Prüfungsordnung: Empfohlene Voraussetzungen:

keine

Grundlagen der Theoretischen Informatik und Grundlagen der Theoretischen Informatik II (Bachelor)

Medienformen: Literatur:


  • Sipser; Theory of Computation
  • Kozen; Automata and Computability
  • Shallit; A Second Course on Automata and Computability Theory

Hinweise:
Dies ist die Bachelorvariante zur gleichnamigen Masterveranstaltung. Voraussetzung sind die (Inhalte der) Veranstaltungen Grundlagen der Theoretischen Informatik und Grundlagen der Theoretischen Informatik II. Ein Bachelorzeugnis ist folglich keine zwingende Voraussetzung für diese Veranstaltung, die den Stoff aus den Teilen 1 und 2 vertieft und ergänzt. Der Aufwand ist eigentlich 6 CP, aber dies ist im Bachelorbereich leider nicht möglich, also sind es im Bachelor nur 5. Dafür müssen Studierende in der Bachelorvariante weniger Übungsaufgaben bearbeiten.

Back to top