Kursinformation

Zum Zugang zum Moodle-Kurs bitte in TUMonline für den Kurs registrieren.

Die Vorlesung ist eine Einfü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: Join, 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 Kombinatorik:
- Zählprinzipien
- Ziehung von Bällen aus Urnen: Variationen, Permutationen, Kombinationen.
- Binomialkoeffizienten: Symmetrie, Identitäten von Pascal und Vandermonde
- Verteilungsprobleme
- Stirling-Zahlen der ersten und zweiten Art
- Geordnete und ungeordnete Zahlpartitionen
- Anwendung Lastverteilung

4) Grundlagen der Graphentheorie:
- Grunddefinitionen
- Bäume
- Eulerkreise: Satz von Euler. Hamiltonkreise: Sätze von Dirac und Ore
- Planargraphen: Eulersche Polyederformel, Satz von Kuratowski
- Matchings: Heiratssatz, augmentierende Pfade
- Matchings mit Präferenzen: Satz von Gale-Shapley

5) Algebraische Grundlagen:
- Grunddefinitionen: Algebra, Gruppe, Ring, Körper
- Gruppen
- Ordnung: Satz von Lagrange, Erzeuger, Gruppenexponent
- Zyklische Gruppen
- Zahlentheoretische Grundlagen: Größter gemeinsamer Teiler,
Erweiterter euklidischer Algorithmus, Eulersche phi-Funktion
- Multiplikative Restklassengruppen
- RSA