Diskrete Strukturen II für Informatiker
Fr 8-10 Uhr, Hörsaal 0446, Wilhelmshöher Allee 71-73
Übungen Fr 10-12, Hörsaal 0446
Die Vorlesung erstreckt sich über zwei Semester,
nämlich das zweite und dritte Studiensemester.
Die zweistündige Vorlesung wird durch eine zweistündige
Übung ergänzt.
Diskrete Strukturen bilden eine grundlegende
Voraussetzung für die Informatik, insbesondere
für die theoretische Informatik.
Der Inhalt gliedert sich wie folgt:
-
Logik
-
Aussagenlogik und Prädikatenlogik (Existenzquantor und Allquantor)
-
Beweistechniken (direkter Beweis, indirekter Beweis,
Widerspruchsbeweis, vollständige Induktion)
-
Mengen, Funktionen, Relationen
-
Mengenalgebra, Boolesche Algebra
-
Funktionen und Relationen
(insbesondere Äquivalenzrelation und Ordnungsrelation)
-
Elementare Zählprinzipien / Kombinatorik
-
Gleichheits-, Summen- und Produktregel, doppeltes Abzählen, Schubfachprinzip
-
Auswahl mit/ohne Wiederholung, mit/ohne Beachtung der Reihenfolge
-
Diskrete Wahrscheinlichkeitsrechnung
-
diskrete Wahrscheinlichkeitsräume
-
bedingte Wahrscheinlichkeiten und Unabhängigkeit
-
Zufallsvariablen, Erwartungswert und Varianz, Unabhängigkeit
-
Binomialverteilung, hypergeometrische Verteilung, geometrische Verteilung
-
Rekursionen
-
Asymptotik, das Master-Theorem
-
Lösung linearer Rekursionen mit konstanten Koeffizienten
-
Algebraische Strukturen
-
Gruppen, Ringe, Körper
-
Restklassenringe, modulare Arithmetik
-
Euklidischer Algorithmus
-
Endliche Körper
-
Einführung in Codierungstheorie und Kryptographie
-
Graphentheorie
-
Grundlegende Definitionen und Sätze
-
Darstellung von Graphen
-
Erzeugende Funktionen
-
Lineare Optimierung, Simplexalgorithmus
Literatur:
Martin Aigner, Diskrete Mathematik, Vieweg, Braunschweig/Wiesbaden, 1993.
Angelika Steger, Diskrete Strukturen, Bd.1: Kombinatorik, Graphentheorie, Algebra,
Springer, Berlin-Heidelberg, 2001.
Thomas Schickinger und Angelika Steger, Diskrete Strukturen, Bd.2: Wahrscheinlichkeitstheorie
und Statistik, Springer, Berlin-Heidelberg, 2001.
Willibald Dörfler und Werner Peschek, Einführung in die Mathematik für Informatiker,
Carl-Hanser, München, 1988.
Werner Nehrlich: Diskrete Mathematik: Basiswissen für Informatiker;
eine Mathematica-gestützte Darstellung, Carl-Hanser, München, 2003.
Der Leistungsnachweis (studienbegleitende Prüfung)
für die zweisemestrige Lehrveranstaltung erfolgt durch die Teilnahme
an einer jeweils zweistündigen Klausur am Ende des jeweiligen
Semesters im Prüfungszeitraum.