Diskrete Strukturen für Informatik
Behandelte Themen
- Naive Mengenlehre, Relationen und Funktionen, elementare Kombinatorik.
- Boolsche Funktionen und Aussagenlogik
- Modulorechnung und elementare Zahlentheorie.
- Graphen: Zusammenhang, Färbbarkeit, Bäume, der Satz von Menger (hierzu Video von Studierenden der TUD), eulersche Graphen, Paarungen
- Äquivalenzrelationen: Äquivalenz und Partition, Partitionen zählen, Kern einer Abbildung, Funktionen zählen
- Ordnungsrelationen: lineare Erweiterungen, Quasiordnungen, transitive Hülle, Ketten, Antiketten, Dilworth
- Bäume zählen: der Satz von Cayley, Spannbäume zählen
- Planare Graphen: die Eulersche Polyederformel, Triangulierungen, der Dualgraph, Minoren
- Gerichtete Graphen: Tiefensuche, Starke Zusammenhangskomponenten, Breitensuche, Transportnetze, der Algorithmus von Edmonds-Karp, nochmals Paarungen
Vorlesungszeiten
Die Vorlesung findet wieder in Präsenz statt. Teilnehmer:innen in Quarantäne können der Vorlesung per Zoom folgen.
Videoaufzeichnungen
Übungen
Übungen finden standardmässig in Präsenz statt.
Vorlesungszeiten
|
Mittwoch |
||
|
Freitag |
Hinweise
Vorlesender ist Manuel Bodirsky, Vorlesungssprache ist Deutsch. Es wird dringend empfohlen, in der Vorlesung mitzuschreiben. Aktive Teilnahme an den Übungen ist obligatorisch.
Skript
Literatur
Die Vorlesung folgt keinem Lehrbuch sondern dem Skript. Wer aber nach ergänzender Literatur sucht, dem empfehlen wir `Diskrete Strukturen', Band 1 (Kombinatorik -- Graphentheorie -- Algebra) von Angelika Steger, Springer Verlag.
Übungen
Verantwortliche: Patrick Serwene, Antje Noack. Informationen zum Übungsbetriebs des ganzen Moduls INF 110.