I210 – Theoretische Informatik

Modul
Theoretische Informatik
Theory of Computing
Modulnummer
I210 [I-210]
Version: 1
Fakultät
Informatik/Mathematik
Niveau
Bachelor/Diplom
Dauer
1 Semester
Turnus
Sommersemester
Modulverantwortliche/-r

Prof. Dr. Boris Hollas
boris.hollas@htw-dresden.de

Dozent/-in(nen)

Prof. Dr. Boris Hollas
boris.hollas@htw-dresden.de

Lehrsprache(n)
ECTS-Credits

5.00 Credits

Workload

150 Stunden

Lehrveranstaltungen

4.00 SWS (2.00 SWS Vorlesung | 2.00 SWS Übung)

Selbststudienzeit

0.00 Stunden

Prüfungsvorleistung(en)
Keine
Prüfungsleistung(en)

Schriftliche Prüfungsleistung
Prüfungsdauer: 90 min | Wichtung: 100%
in "Theoretische Informatik"

Lehrform

2/2/0  V/Ü/P

Medienform
Keine Angabe
Lehrinhalte/Gliederung
  • Reguläre Sprachen: DFA, NFA, reguläre Grammatiken, reguläre Ausdrücke, Pumping-Lemma.
  • Kontextfreie Sprachen: PDA, kontextfreie Grammatiken, CYK-Algorithmus, Mehrdeutigkeit, einfache Top-Down und Bottom-Up-Parser.
  • 0L-Systeme, Chomsky-Hierarchie.
  • Entscheidbarkeit, Halteproblem, unentscheidbare Probleme.
  • Komplexitätsklassen P und NP, NP-vollständige Probleme.
Qualifikationsziele

Die Theorie der Formalen Sprachen soll beherrscht und die Grenzen der Berechenbarkeit erkannt werden.

Sozial- und Selbstkompetenzen
Keine Angabe
Besondere Zulassungsvoraussetzung
Keine Angabe
Empfohlene Voraussetzungen

Grundlagen der Informatik

Fortsetzungsmöglichkeiten
Keine Angabe
Literatur

Boris Hollas: Grundkurs Theoretische Informatik: Mit Aufgaben und Anwendungen. Springer-Vieweg, 2. Auflage 2015

Aktuelle Lehrressourcen

Siehe oben

Hinweise
Keine Angabe