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
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.