Zum Zugang zum Moodle-Kurs bitte in TUMonline für den Kurs registrieren.
Die Vorlesung ist e
ine E
inführung
in die Begriffe und Bereiche der Diskreten Mathematik für
Informatiker. Sie gliedert sich
in fünf Teilen:
1) Grundbegriffe der Mengen, Relationen und Funktionen:
- Mengen: Grundoperationen, Äquivalenzgesetze, KV-Diagramme,
Abzählbarkeit, Satz von Cantor
- Relationen: Jo
in, Transitive Hülle, Relationale Algebra
- Funktionen: Grundeigenschaften, Komposition,
Inverse
2) Grundlagen der Aussagenlogik und Logik erster Stufe:
- Aussagenlogik:
- Syntax und Semantik
- Wahrheitstabellen und Bezug zu KV-Diagramme
- Äquivalenzgesetze
- KNF, DNF, Normalisierungsverfahren, Erfüllbarkeitsäquivalenz
- SAT-Verfahren: DPLL, Resolution. Korrektheitsnachweis
- Modellierung mit Aussagenlogik
- Prädikatenlogik
- Syntax und Semantik
- Äquivalenzgesetze
- Modellierung mit Prädikatenlogik
3) Grundlagen der Komb
inatorik:
- Zählpr
inzipien
- Ziehung von Bällen aus Urnen: Variationen, Permutationen, Komb
inationen.
- B
inomialkoeffizienten: Symmetrie, Identitäten von Pascal und Vandermonde
- Verteilungsprobleme
- Stirl
ing-Zahlen der ersten und zweiten Art
- Geordnete und ungeordnete Zahlpartitionen
- Anwendung Lastverteilung
4) Grundlagen der Graphentheorie:
- Grunddef
initionen
- Bäume
- Eulerkreise: Satz von Euler. Hamiltonkreise: Sätze von Dirac und Ore
- Planargraphen: Eulersche Polyederformel, Satz von Kuratowski
- Match
ings: Heiratssatz, augmentierende Pfade
- Match
ings mit Präferenzen: Satz von Gale-Shapley
5) Algebraische Grundlagen:
- Grunddef
initionen: Algebra, Gruppe, R
ing, Körper
- Gruppen
- Ordnung: Satz von Lagrange, Erzeuger, Gruppenexponent
- Zyklische Gruppen
- Zahlentheoretische Grundlagen: Größter geme
insamer Teiler,
Erweiterter euklidischer Algorithmus, Eulersche phi-Funktion
- Multiplikative Restklassengruppen
- RSA