Website
Module guide WS 2018-2022

Module CS2000-KP08, CS2000

Theoretical Computer Science (TI)

Duration:


1 Semester
Turnus of offer:


each winter semester
Credit points:


8
Course of studies, specific field and terms:
  • Bachelor Media Informatics 2020 (compulsory), computer science, 3rd semester
  • Bachelor Computer Science 2019 (compulsory), foundations of computer science, 3rd semester
  • Bachelor Robotics and Autonomous Systems 2020 (optional subject), computer science, 5th or 6th semester
  • Bachelor Medical Informatics 2019 (compulsory), computer science, 3rd semester
  • Bachelor Computer Science 2016 (compulsory), foundations of computer science, 3rd semester
  • Bachelor Robotics and Autonomous Systems 2016 (optional subject), computer science, 5th or 6th semester
  • Bachelor IT-Security 2016 (compulsory), computer science, 3rd semester
  • Bachelor MES 2011 (optional subject), computer science, 5th semester
  • Bachelor Medical Informatics 2014 (compulsory), computer science, 3rd semester
  • Bachelor Computer Science 2014 (compulsory), foundations of computer science, 3rd semester
  • Bachelor Media Informatics 2014 (compulsory), computer science, 3rd semester
  • Bachelor Medical Informatics 2011 (compulsory), computer science, 3rd semester
  • Bachelor Computer Science 2012 (compulsory), foundations of computer science, 3rd semester
Classes and lectures:
  • Theoretical Computer Science (exercise, 2 SWS)
  • Theoretical Computer Science (lecture, 4 SWS)
Workload:
  • 90 Hours in-classroom work
  • 135 Hours private studies and exercises
  • 15 Hours exam preparation
Contents of teaching:
  • Formalization of problems using languages
  • formal grammars
  • regular languages, finite automata
  • context free language, push down automata
  • sequential computational models: Turing machines, register machines
  • sequential complexity classes
  • simulations, reductions, completeness
  • satisfiability problem, NP-completeness
  • (In-)decidability and enumerability
  • halting problem and Church-Turing thesis
Qualification-goals/Competencies:
  • Students are able to present the theoretical foundation of syntax and operational semantics of programming languages
  • They are able to transform formalizations using theorems of theoretical computer science.
  • They can classify problems according to their computational complexity
  • They are able to model algorithmic problems and solve them using appropriate tools
  • They can judge what computer science can and cannot achieve in principle
Grading through:
  • written exam and course achievements
Is requisite for:
Requires:
Responsible for this module:
Teachers:
Literature:
  • J. Hopcroft, R. Motwani, J. Ullman: Introduction to Automata Theory, Languages and Computation - Addison Wesley, 2001
Language:
  • offered only in German
Notes:

Admission requirements for taking the module:
- None (the competences of the modules indicated under

Letzte Änderung:
1.2.2022