Inhalt

Es werden grundlegende mathematische Begriffe und Techniken eingeführt. Dabei werden die Anwendungen in der Informatik in den Vordergrund gestellt. Schwerpunkte liegen auf den Methoden aus der diskreten Mathematik, die zur Entwicklung und Analyse von effizienten Algorithmen gebraucht werden. Induktion, Kombinatorik, Zahlentheorie, Graphentheorie, Algebra sind besonders wichtige Gebiete für die Informatik und Grundlage weiterer Anwendungen, wie zum Beispiel Kryptographie und Kodierungstheorie. Bei der Darstellung des Stoffes soll neben der mathematisch exakten Vorgehensweise besonders das intuitive Verständnis gefördert werden. Dies wird durch zahlreiche Beispiele und Übungsaufgaben unterstützt.

Inhaltsverzeichnis

  1. Logik
    Junktoren, Formeln, Äquivalenz von Formeln, Normalformen, Minimierung.

  2. Mengenlehre
    Operationen, Potenzmenge, Kreuzprodukt.

  3. Relationen
    Verkettung, Umkehrrelation, Äquivalenzrelationen, Ordnungsrelationen.

  4. Funktionen
    Bijektionen, Permutationen, Mächtigkeiten.

  5. Vollständige Induktion
    Summen, Rekursion, Eulersche Polyeder Formel, planare Graphen, Graph Färbung, Schleifen-Invarianten.

  6. Kombinatorik
    Anzahlprobleme, Binomial-Koeffizienten, Pascalsches Dreieck, Binomialtheorem.

  7. Zahlentheorie
    Teilbarkeit, größter gemeinsamer Teiler, kleinstes gemeinsames Vielfaches, Euklidischer Algorithmus, Primzahlen, Kongruenz, chinesischer Restsatz, Eulersche Phi-Funktion, Identitätssatz für Polynome.