Module CS2000-KP08, CS2000

Duration

1 Semester

Turnus of offer

each winter semester

Credit points

8

Course of studies, specific fields and terms:

• Bachelor Media Informatics 2020, compulsory, computer science
• Bachelor Computer Science 2019, compulsory, foundations of computer science
• Bachelor Robotics and Autonomous Systems 2020 , optional subject, computer science
• Bachelor Medical Informatics 2019, compulsory, computer science
• Bachelor Computer Science 2016, compulsory, foundations of computer science
• Bachelor Robotics and Autonomous Systems 2016, optional subject, computer science
• Bachelor IT-Security 2016, compulsory, computer science
• Bachelor MES 2011, optional subject, computer science
• Bachelor Medical Informatics 2014, compulsory, computer science
• Bachelor Computer Science 2014, compulsory, foundations of computer science
• Bachelor Media Informatics 2014, compulsory, computer science
• Bachelor Medical Informatics 2011, compulsory, computer science
• Bachelor Computer Science 2012, compulsory, foundations of computer science

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:

• Parallel Computing (CS3051-KP04, CS3051)

Requires:

• Algorithms and Data Structures (CS1001-KP08, CS1001)
• Introduction to Programming (CS1000-KP08, CS1000SJ14-MML/MI, CS1000SJ14-MIW)
• Introduction to Programming (CS1000-KP10, CS1000SJ14)

Responsible for this module:

• Prof. Dr. Rüdiger Reischuk

Teacher:

• Institute for Theoretical Computer Science
• Prof. Dr. Rüdiger Reischuk
• Prof. Dr. rer. nat. Till Tantau
• Prof. Dr. Maciej Liskiewicz

Literature:

• J. Hopcroft, R. Motwani, J. Ullman : Introduction to Automata Theory, Languages and Computation Addison Wesley, 2001

Language:

• offered only in German

Notes:

Last Updated:

01.02.2022