### Page Content

### to Navigation

## What is Theoretical Computer Science?

**Theoretical Computer** **Science** is sometimes seen as a *structural science*, sometimes as a *formal science*. Using abstraction and formal modelling, it explores the foundations of Computer Science (the structure, processing, transmission, and reproduction of information). For this purpose, Theoretical Computer Science exploits mathematical methods and structures that differ from those of classical engineering mathematics and that have been further developed especially for Computer Science or have been invented from scratch. The objective of Theoretical Computer Science is to convey the most important terms and concepts for the formal description and analysis of IT systems (software/hardware). One of the goals is to be able to unambiguously describe, analyze, and manipulate computer artifacts such as algorithms and data structures in sufficient detail; however, algorithms and data structures belong to the discipline of Practical Computer Science. Similarly, digital circuit logic is part of Computer Engineering, whereas the formal basics required for this are taught in the field of Theoretical Computer Science.

The basic studies in Theoretical Computer Science comprises at least four modules with 6 ECTS credit points each within the Bachelorâ€™s program of Computer Science at TU Berlin. In *Formal Languages and Automata*, the focus is on formal languages in the context of the Chomsky hierarchy. Formal grammars for the generation of languages and machine models for the recognition of languages are introduced and related to each other. Two additional modules ensue: propositional logic and predicate logic are subjects that are taught in *Logic*, with the help of which students should be able to translate linguistic content into formal structures. In addition to the mere syntax and semantics, however, algorithmic problem-solving methods and calculations of evidence for the truth value of formulas are also important. In* Computability and Complexity, *students learn to understand and recognize the inherent limits of the computability of IT systems, which are characterized, for example, by the halting problem, questions of undecidability and also by the Church-Turing thesis. An additional focus is put on complexity classes which can be used to characterize and analyze the computing effort and memory requirements of algorithms. Based on these three modules, students have to choose an additional module in Theoretical Computer Science; for this requirement, each of the three above-mentioned modules can be followed up with a directly related specialization module.