Beschreibung
Wir verwenden heute wie selbstverständlich für unsere Routenplanung Google Maps oder Naviki, E-Mails versenden wir nur noch verschlüsselt und durch Scannen von QR-Codes mit dem Mobiltelefon kommen wir schnell zur gewünschten Information. Dabei verwenden wir bewußt oder unbewußt Methoden aus dem Gebiet der Diskreten Strukturen: Graphen organisieren Verkehrswege und erlauben es, mittels Algorithmen optimale Routen schnell zu finden. Die Zerlegung von Zahlen in Primzahlen ist die Basis einer asymmetrischen Verschlüsselung und algebraische Strukturen ermöglichen das Rechnen mit endlichen Zahlenmengen und damit die Erzeugung von QR-Codes. Die Veranstaltung Diskrete Strukturen führt in die drei Themengebiete Zahlentheorie, Algebraische Strukturen und Graphentheorie ein.
Studienverlauf
Die Veranstaltung Diskrete Strukturen ist Pflichtmodul im 3. Fachsemester für die Studierenden der Bachelorstudiengänge Informatik und Informatik dual. Sie wird im Wechsel von Prof. Effinger, Prof. te Vrugt und Prof. Bauer gelesen.
Stundenumfang Diskrete Strukturen: 4V+2Ü
Inhalte der Lehrveranstaltung
Zahlentheorie
Teilbarkeit, ggT, kgV, Euklidischer Algorithmus, Lemma von Bézout, Primfaktorzerlegung, modulare Arithmetik, Kongruenz modulo n, Äquivalenzrelation, Restklassen, Kongruenzsatz, Quotientenmenge, Eulersche phi-Funktion, Satz von Euler und Fermat, Bedeutung für symmetrische und asymmetrische Verschlüsselung, Überblick über RSA-Algorithmus, Signaturverfahren
Algebraische Strukturen
Gruppen, Gruppen niedriger Ordnung, Gruppenhomomorhismen,Permutationen, vollständige symmetrische Gruppe, zyklische Gruppen, diskreter Logarithmus, Exkurs: ElGamal-Verfahren, Ringe, Körper, endliche Körper, Polynome über endlichen Körpern, irreduzible Polynome, Konstruktion von Körpern, Galois-Felder
Graphentheorie
Anwendungsgebiete, Grundbegriffe, Wege, Kreise, Zusammenhang, Schlingen, Mehrfachkanten, Multigraphen, Gewichte, Flüsse, vollständige und bipartite Graphen, planare Graphen, Satz von Euler, Bäume, aufspannende Bäume, Wurzelbäume, minimale Spannbäume, Eulersche Graphen, Hamiltonsche Graphen, Satz von Dirac, Anwendungen
Qualifikationsziele
Entwickelte Fachkompetenz:
Die Studierenden verstehen und beherrschen die grundlegenden Begriffe und Methoden der höheren Mathematik in den Teilgebieten Zahlentheorie, Algebra, und Graphentheorie.
Entwickelte Sozialkompetenz:
Die Lösung von Aufgaben in Kleingruppen erhöht die Fähigkeit zur Kommunikation über abstrakte Begriffe und Lösungsverfahren.
Entwickelte Selbstkompetenz:
Lernbereitschaft, Arbeitsorganisation und Selbstmanagement werden weiterentwickelt.
Entwickelte Methodenkompetenz:
Die Studierenden verfügen über die Kompetenz zur Anwendung von Methoden der Diskreten Mathematik in der Informatik und sind in der Lage, sie zur Modellbildung einzusetzen.
Literatur (Auswahl)
[1] W. Struckmann, D. Wätjen, Mathematik für Informatiker, Springer 2016
[2] A. Beutelspacher, M.-A. Zschiegner, Diskrete Mathematik für Einsteiger, Springer 2014
[3] M. Schubert, Mathematik für Informatiker, Vieweg-Teubner, 2. Auflage, 2012
[4] G. Teschl, S. Teschl, Mathematik für Informatiker, Band 1: Diskrete Mathematik und Lineare Algebra, Springer, 4. Auflage, 2014
[5] K.-U. Witt, Algebraische und zahlentheoretische Grundlagen für die Informatik: Gruppen, Ringe, Körper, Primzahltests, Verschlüsselung, Springer Vieweg, 2014
Voraussetzungen
Kenntnisse aus dem Modul Mathematik I und II
Unterlagen zu den Vorlesungen
Weiter Unterlagen, Skripte etc. finden Sie hier ...