Vorlesung Diskrete Mathematik

Zurück zur Übersicht ...

Titel
Diskrete Mathematik
Title (in english)
Discrete Mathematics
Kürzel (Prüfungsamt)
DSMA
Art der Lehrveranstaltung
Vorlesung (Pflichtfach)
gehört zu
Lehrende(r)
Fakultät
Wird gehalten
im Wintersemester
empfohlenes Semester
Credits
5 CP
Semesterwochenstunden
4 SWS
Leistungsnachweis(e)
WiSe 2014 (MIN2, freigegeben am 16.10.2014)
SoSe 2014 (MIN2, freigegeben am 03.04.2014)

Ziele

Die Studierenden erwerben graphentheoretische und algebraische Grundlagen, die als zeitloses methodisches Rüstzeug für die Beschreibung und Lösung informations- und kommunikationstechnischer Probleme dienen. Diese Konzepte der diskreten Mathematik werden jeweils exemplarisch illustriert an Graphen-Anwendungen und in den Bereichen Kryptographie und Codierungstheorie.

Inhalte

1 Graphentheorie

1.1 Traversieren von Graphen

1.2 Bäume und Wege

1.3 Netzwerke und bipartite Graphen

 

2 Gruppentheorie

2.1 Gruppen-Homomorhismen und -Isomorphismen

2.2 Nebenklassen von Untergruppen, Satz von Lagrange

2.3 Faktorgruppen, Isomorphiesätze

2.4 Kleiner Fermatscher Satz

2.5 Zyklische Gruppen

 

3 Ringe und Körper

3.1 Ring-Homomorhismen und -Isomorphismen

3.2 Faktorringe

3.3 Polynomringe

 

4 Zahlentheorie

4.1 Chinesischer Restsatz

4.2 Eulersche Phi-Funktion

4.3 Satz von Euler

 

5 Public Key-Kryptographie

5.1 Öffentlich-private Schlüsselpaare

5.2 Faktorisierungsproblem, Problem des diskreten Logarithmus

5.3 RSA-Kryptosystem, Diffie-Hellmann-Schlüsseltausch, ElGamal-Verschlüsselung

5.4 Elliptische Kurven

5.5 Primzahl-Erzeugung: Satz von Wilson, Fermat-Test, Miller-Rabin-Test

5.6 Primzahlsatz

 

6 Endliche Körper und Körpererweiterungen

6.1 Additive und multiplikative Gruppe bei endlichen Körpern

6.2 Primitive Elemente

6.3 Konstruktion von Körpern mit Hilfe irreduzibler Polynome

Empfohlene Literatur

Forster

Algorithmische Zahlentheorie, Vieweg, 2013

Socher

Algebra für Informatiker, Hanser, 2012

Steger

 Diskrete Strukturen, Springer, 2007

Teschl/Teschl

Mathematik für Informatiker, Band 1, Springer 2013

Turau

Algorithmische Graphentheorie, Oldenbourg 2009

Witt

Algebraische Grundlagen der Informatik, Vieweg, 2012

Arbeitsaufwand

Voraussetzungen

Grundkenntnisse in Zahlentheorie und linearer Algebra

Form der Wissensvermittlung

Seminaristischer Unterricht, Kurzvorträge zu ausgewählten Themen, Übungen