Module Import 04IN2019 - Advanced Topics in Theoretical Computer Science

Status: Published
Workload6 ECTS = 180 hrs
Credits, Weight6 ECTS, (n.s.)
Language of Instruction German or English
Semester (n.s.)
Duration1 Sem.
M/E Mandatory
Courses
Course No. Type Name MA/EL Workload Credits Contact Hours Selfstudy Group Size
04IN2019-1 Lecture Advanced Topics in Theoretical Computer Science MA 3 ECTS = 90 hrs 3 ECTS 2 hrs/week = 30 hrs 60 hrs 40
04IN2019-2 Exercise Advanced Topics in Theoretical Computer Science MA 3 ECTS = 90 hrs 3 ECTS 2 hrs/week = 30 hrs 60 hrs 40
Learning Outcomes

The students have a thorough understanding of formal concepts and of the limits of computability, decidability, complexity.

They know various notions of computability and the relationships between them, understand the concepts of decidability and undecidability and can prove undecidability of languages using proofs by reduction or using the theorem of Rice, know about complexity classes and methods for proving that problems belong to a certain complexity class.

Content

(not specified)

04IN2019-1 - Advanced Topics in Theoretical Computer Science

1. Computability:

  • Register machines:
    • LOOP computable functions,
    • WHILE-computable functions,
    • GOTO computable functions
  • Recursive functions:
    • Primitive recursive functions,
    • μ-recursive functions
  • Links between different computation models:
    • LOOP computable functions vs. primitive recursive functions
    • TM-computable functions vs. WHILE/GOTO-computable functions vs. μ-recursive functions
  • Church's Thesis

2. Undecidable Problems

  • Undecidability Proofs by Reduction
  • The theorem of Rice
  • Undecidability and formal languages

3. Complexity

  • Complexity classes
  • NP-complete problems
  • PSPACE completeness and QBF
  • Further directions in complexity theory

4. Applications in computer science and logic

04IN2019-2 - Advanced Topics in Theoretical Computer Science

In the exercises for the lecture "Advanced Topics in Theoretical Computer Science" the material presented in the lectures is repeated in order to achieve a thorough understanding. Solutions to exercises related to the topics of the lectures are presented and discussed by the students.

Teaching Methods

(not specified)

Prerequisites

Knowlege of notions taught in the lecture "Fundamentals of Theoretical Computer Science":

  • Automata and formal languages and the links between them.
  • Computability, decidability, undecidability.
  • Basic notions in complexity theory.
Examination Methods

Written or oral exam depending on the number of participants.

Credit Requirements

(not specified)

References

(not specified)

04IN2019-1 - Advanced Topics in Theoretical Computer Science

Katrin Erk, Lutz Priese, Theoretische Informatik, Springer Verlag, 2000

Michael Garey, David Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman and Co, 1991.

John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullmann. Introduction to Automata Theory, Languages, and Computation. Dritte Ausgabe. Addison Wesley, 2006.

Use of this Module
  1. unmodified as Mandatory  -    BSc Computational Visualistics 2017  -    Mandatory elective courses Computer Science  -    Advanced Topics in Theoretical Computer Science
  2. unmodified as Mandatory  -    BSc Computational Visualistics 2017  -    Mandatory elective courses in Computational Visualistics or computer science  -    Advanced Topics in Theoretical Computer Science
  3. unmodified as Mandatory  -    MSc Computer Science 2017  -    Compulsory subject computer science  -    Advanced Topics in Theoretical Computer Science
  4. unmodified as Mandatory  -    MSc Computational Visualistics 2017  -    Mandatory elective courses Computer Science  -    Advanced Topics in Theoretical Computer Science
  5. unmodified as Mandatory  -    MSc Computational Visualistics 2017  -    Mandatory elective courses in Computational Visualistics or computer science  -    Advanced Topics in Theoretical Computer Science
  6. unmodified as Mandatory  -    MSc Computational Visualistics 2017  -    Mandatory elective courses in theoretical computer science and mathematics  -    Advanced Topics in Theoretical Computer Science
  7. unmodified as Mandatory  -    MSc Computational Visualistics 2017  -    Mandatory elective courses in theoretical computer science and mathematics or natural and social sciences  -    Advanced Topics in Theoretical Computer Science
  8. unmodified as Mandatory  -    MSc Information Systems 2017  -    Mandatory elective courses Application Systems in Business and Administration  -    Advanced Topics in Theoretical Computer Science
Responsible / Organizational Unit
Sofronie-Stokkermans, Viorica / Institute for Computer Science
Additional Information

(not specified)

Last change
Apr 24, 2018 by Frey, Johannes
Last Change Module
Sep 28, 2018 by Frey, Johannes