# Information concerning preconditions

Following the CS master program regulations admission to our master program is only possible with a bachelor degree in computer science which is comparable to the bachelor degree in computer science awarded by our department. Therefore the admission to the master degree program is under the precondition that you fulfil the courses  "Advanced Programming" ant "Logical and Theoretical Foundations of CS". These preconditions have to be fulfiled within the first semester.

These moduls are part of the bachelor degree program and the lectures are taught in German. To prepare for the obligatory exams needed to fulfil the preconditions we recommend the study of the following books and tutorials and participation in the lectures and exercises offered to help you prepare for the exams:

• Logical and Theoretical Foundations of Computer Science (10 ECTS)
• In this lecture the basics of mathematical logic and theory of computation are taught as well as the fundamental techniques of proving. The lecture starts with a profound introduction into propositional logic. This includes declarative sentences, natural deduction, propositional logic as a formal language, semantics of proposition logic, normal forms, and SAT solvers. This part is followed by a section in which the students learn how to apply these methods in theoretical computer science, namely in how to write a decent proof. This section covers not only different ways of proving a given claim but also shall give an intuition for proving - from the start to a nicely written proof. In the third part an introduction to predicate logic is given, namely predicate logic as a formal language, proof theory of predicate logic, and semantics of predicate logic. Afterwards again the students learn how to apply these formal methods to proofs they will have to write in their master's studies. In a fifth part this knowledge is deepened by an introduction to theory of computation. Here the Chomsky hierarchy builds the basis. With the knowledge about decidability, the last part of logic follows: the expressiveness of predicate logic. The last part contains the basics of complexity theory, namely the classes P, NP, and NPC.
In all parts the main focus is on proving fundamental properties like associativity, commutativity, idempotency, etc. as well as soundness, completeness, and closure properties for getting a profound understanding of the connections between computability, decidability in computer science and the mathematical basis.
Mathematical basics like sets, functions, relations including the main properties like injectivity, surjectivity, bijectivity, totality for functions, and symmetry, reflexivity, transitivity, (total) order for relations are assumed to be known.
Literatur:
• "Automata and Computability" by Dexter C. Kozen
• "Logic in Computer Science, Second Edition" by Michael Huth, Mark Ryan