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, as practiced via the exercise sheets for the proseminars and discussed there.

Software

M. Haselrieder, WebApp for Warshall and Floyd, Bachelor Thesis (2020).

Recommended literature

There is a lot of literature on Discrete Mathematics and Discrete Structures. We here only give some pointers to literature that is relatively close, contentwise, to this course. (Note that the exam will be based exclusively on the material as presented in the lecture/on the slides. That is, the literature below is to be seen as supplementary only.)

G. Moser, Diskrete Mathematik, Ein Skriptum zum Vorlesung, 2019. (Course notes in German for a predecessor course; covering in detail almost all content of the present course (and more).)

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

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

J.E. Hopcroft, R. Motwani, D.r 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.