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

Eine Einführung in Formale Konzepte für Quereinsteiger ist verfügbar. Die Vorlesung orientiert sich inhaltlich an der Vorlesung vom Sommersemester 2016.

Skriptum

Skriptum (6te Auflage, doppelseitig)

pdf

errata

Empfohlene Literatur

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.