Content

The course offers an introduction into discrete structures. The following themes will be covered in the lectures, and treated in more detail in the proseminars.

• directed and undirected graphs
• relations and functions
• orders and induction
• trees and dags
• finite and infinite counting
• elementary number theory
• Turing machines, algorithms, and complexity
• decidable and undecidable problems

An introduction to formal concepts is available (in German). The lecture is an adaptation of the Diskete Mathematik lecture of Sommersemester 2018, but since the time available, and ECTS awarded, have been reduced, less material will be covered. The exam is based on the contents of the slides. That content will be discussed in detail in the proseminars.

Recommended literature

D.~Tonien, A Simple Visual Proof of the Schröder-Bernstein Theorem, Elem. Math. 62 (2007), 118-120.

J.L. Hein, Discrete Structures, Logic, and Computability, Jones and Bartlett Publishers, 2002.

J.E. Hopcroft, R. Motwani, D. Ullman, Einführung in die Automatentheorie, Formale Sprachen und Komplexität, Pearson Studium, 2002.

M. Sipser, Introduction to the Theory of Computation, Course Technology, 2012.