Inhalt
Der Kurs bietet eine Einführung in die Diskrete Mathematik. In der Vorlesung werden die folgenden Themen behandelt, die im Proseminar in weiterführenden Übungen vertieft werden.
- Wohlfundierte Induktion
- Graphen und Bäume
- Grundlagen des Abzählens
- Elementare Zahlentheorie
- Formale Sprachen und endliche Automaten
- Turing Maschinen
- Die Komplexitätsklassen P und NP
- Grundlagen der Wahrscheinlichkeitstheorie
Skriptum
Skriptum (8te Auflage, doppelseitig) | errata |
Empfohlene Literatur
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.