M1.1 Diskrete Strukturen (1. Teil des Moduls M1: Mathematik für die Informatik 1) - Detailseite

Die Prüfung zu dem ganzen Modul kann nach dem Ende des Sommersemesters abgelegt werden, nachdem der zweite Teil des Moduls (M1.2 „Lineare Algebra und ihre Bezüge zur Informatik“) abgeschlossen ist.

• Mathematische Grundbegriffe: Menge der natürlichen Zahlen; Unendlichkeit; (Über)Abzählbarkeit; Prinzip der Diagonalisierung; kartesische Produkte; Relationen; Funktionen; rekursive Definitionen; Klärung der Begriffe „Definition“, „Satz“, „Lemma“, „Korollar“
• Mathematische Beweise verstehen und selbst formulieren: Aussagen und ihre Verknüpfungen; Beweistechniken (direkter Beweis, Beweis durch Kontraposition, Beweis durch Widerspruch, vollständige Induktion)
• Graphen und Bäume: Grundbegriffe (gerichtete und ungerichtete Variante; Wege; Kreise) und grundlegende Eigenschaften; Isomorphie; Zuordnungsprobleme und ihre Bedeutung für die Informatik (z.B. Modellierung von Problemen durch Matching- oder Färbungsprobleme); Grundbegriffe zu speziellen Graphen (z.B. vollständige Graphen; Binärbäume; bipartite Graphen; planare Graphen)
• Algebraische Strukturen: modulare Arithmetik; Grundbegriffe zu Gruppen, Körpern und Ringen; endliche Körper und Polynomringe und ihre Bedeutung in der Informatik, z. B. in der Codierungstheorie
• Kombinatorik: kombinatorische Abzählregeln; das Prinzip des doppelten Abzählens; Binomialkoeffizienten; Schubfachprinzip
• Diskrete Stochastik: Ereignisse und ihre Wahrscheinlichkeiten; diskrete Wahrscheinlichkeitsräume; Zufallsvariablen; Erwartungswert und Varianz; Markov-Ungleichung; Tschebyscheff-Ungleichung; Ausblick auf randomisierte Algorithmen und deren erwartete Laufzeit bzw. Erfolgswahrscheinlichkeit

Diese Lehrveranstaltung ist als Pflicht-LV relevant für die Studierenden im Bachelorstudium im Fach Informatik - Kern- und Zweitfachbezug des Kombistudiengang mit Lehramtsbezug nach der SPO 2015.

Gemäß der SPO 2024 für das Bachelorstudium im Fach Informatik - Kern- und Zweitfachbezug des Kombistudiengang mit Lehramtsbezug - heißt die Lehrveranstaltung „Diskrete Strukturen für das Lehramt Informatik“ (s. LV 3313090 + 3313091).