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, 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. 

Zoom Link

Videoaufzeichnungen

Link zum Videocampus

Übungen

Übungen finden standardmässig in Präsenz statt.

Vorlesungszeiten

Hinweise

Vorlesender ist Manuel Bodirsky, Vorlesungssprache ist Deutsch. Es wird dringend empfohlen, in der Vorlesung mitzuschreiben. Aktive Teilnahme an den Übungen ist obligatorisch.

Skript

Skript zur Vorlesung.

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.