Diskrete Modellierung

WiSe-20xx/xx

Wochenplan

Die Veranstaltung dauert 15 Wochen, die Pläne sind vorläufig:

Einführung.
Mathematische Grundladen. Mengen, Mengenoperationen, Potenzmengen, Kartesisches Produkt, Relationen und Funktionen, Mächtigkeit und Kardinalität.
Aussagenlogik. Syntax, Belegungen, Wahrheitstafeln, erfüllbare/falsifizierbare Formeln, Widersprüche und Tautologien, Semantische Äquivalenz, Disjunktive Normalform, Konjunktive Normalform, KNF-SAT, Resolution, DPLL.
Beweise. Direkte, Kontraposition, Widerspruch, Diagonalisierung, vollständige Induktion, Rekursion
Graphen. Wege, Kreise, Zusammenhang, Matching, Färbung, Isomorphie, Graphklassen.
Bäume. Minimale Spannbäume, Binärbäume, Entscheidungsbäume.
Markov-Ketten. Zufallssurfer, Übergangsmatrix, Irrfahrt einer Markov-Kette, Markov-Ketten, Grenzverteilung, ergodische Ketten, Stationäre Verteilungen, Google’s Page-Rank.
Endliche Automaten. Alphabete, Worte und Sprachen, deterministische endliche Automaten, Minimierung, Verschmelzungsrelation, Paare nicht-äquivalenter Zustände, Äquivalenzklassenautomat, Minimierungsalgorithmus, Nerode-Relation, Nerode-Automat.

Nach der Veranstaltung können die Studierenden:

grundlegende Modellierungsmethoden (Kalkül der Mengen, Aussagen- und Prädikatenlogik, Graphen, Markovketten, endliche Automaten, kontextfreie Grammatiken) und Beweismethoden (Direkter Beweis, Induktion, Widerspruch) beschreiben und anwenden,
praxisbezogene Aussagen mathematisch präzise und formal ausdrücken,
sich über fachbezogene Inhalte mündlich und schriftlich austauschen.

Siehe Wochenplan.

Voraussetzungen. Der Kurs wird typischerweise im ersten/zweiten Semester belegt und hat als notwendige Vorraussetzung die Mathematikkenntnisse aus der Schule.