I210 – Theory of Computing

Module
Theory of Computing
Theoretische Informatik
Module number
I210 [I-210]
Version: 1
Faculty
Informatics/Mathematics
Level
Bachelor/Diploma
Duration
1 Semester
Semester
Summer semester
Module supervisor

Prof. Dr. rer. nat. Boris Hollas
boris.hollas(at)htw-dresden.de

Lecturer(s)

Prof. Dr. rer. nat. Boris Hollas
boris.hollas(at)htw-dresden.de

Course language(s)
ECTS credits

5.00 credits

Workload

150 hours

Courses

4.00 SCH (2.00 SCH Lecture | 2.00 SCH Seminar)

Self-study time

0.00 hours

Pre-examination(s)
None
Examination(s)

Written examination
Examination time: 90 min | Weighting: 100%
in "Theoretische Informatik"

Form of teaching

2/2/0  V/Ü/P

Media type
No information
Instruction content/structure
  • 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.
Qualification objectives

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

Social and personal skills
No information
Special admission requirements
No information
Recommended prerequisites

Grundlagen der Informatik

Continuation options
No information
Literature

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

Current teaching resources

Siehe oben

Notes
No information