Zur Hauptnavigation / To main navigation

Zur Sekundärnavigation / To secondary navigation

Zum Inhalt dieser Seite / To the content of this page

Hauptnavigation / Main Navigation

Sekundärnavigation / Secondary navigation

Mathematik für Informatiker: Algebraische Strukturen

Inhaltsbereich / Content

Mathematik für Informatiker: Algebraische Strukturen

Dr. Michael Kunte

Dipl.-Math. Dipl.-Phys. Philipp Korell

Termine

 

Vorlesung

WochentagZeitRaum
Dienstag13:45 - 15:1548-210
Freitag08:15 - 09:4524-102

Übungen

ÜbungWochentagZeitRaumÜbungsleiter
Übung1Mittwoch11:45 - 13:1544-380Sarah Haufe

Übung2

Mittwoch11:45 - 13:1548-453Rebekka Haese
Übung3Mittwoch15:30 - 17:0052-204Mirjam Wehr

Aktuelles

  • Bitte melden Sie sich für die Übungsteilnahme bis einschließlich Freitag, 27.10.2017, 12 Uhr, online in URM an. Das System führt Sie durch die einzelnen Schritte. Sie benötigen lediglich eine uni-interne Emailadresse. Voraussichtlich am Nachmittag des Freitag, 27.10.2017, erfolgt dann anhand Ihrer Angaben die Einteilung in die einzelnen Übungsgruppen. Sie bekommen eine Email, aus der hervorgeht, in welche Gruppe Sie eingeteilt worden sind.
  • Wir starten mit den Übungen per Präsenzübung (d.h. die Aufgaben können dort direkt von Ihnen gelöst werden und Sie müssen kein Übungsblatt vorher abgeben) in der zweiten Vorlesungswoche. Aufgrund der Feiertage am 31.10. und 1.11. bieten wir verschiedene Ersatztermine am Donnerstag, den 2.11.17, um 13:45-15:15 in 48-538 (Achtung: Raumänderung!), und am Freitag, den 3.11.17, um 11:45-13:15 in 44-336 an.
  • Mit dem regulären Übungsbetrieb beginnen wir am Mittwoch, den 8.11.17.
  • Wir bieten jede zweite Woche, beginnend mit Montag, den 6.11.17, 15-16 Uhr, eine zusätzliche Fragestunde zu den Übungsaufgaben und den Vorlesungsstoff an, in der - in der Regel - der Dozent für Fragen zur Verfügung steht. Diese Fragestunde findet im Rahmen des Lernzentrum Mathematik im Raum 48-306 statt.
  • Ausnahmsweise ist die nächste Fragestunde außerhalb dieses Turnus am Montag, den 27.11.17, 15-16 Uhr, in 48-306. Danach ist die darauf folgende Fragestunde am Montag, den 18.12.17, in 48-306.
  • Probeklausur: Am Dienstag, 16.1.18, wird statt der Vorlesung zur normalen Vorlesungszeit (d.h. 13:45-15:15 in 48-210) eine Probleklausur durchgefürt. D.h. Sie können live testen, wie gut Sie in einer Klausur abschneiden würden - auch wenn die Zeit in der Probeklausur kürzer ist. Das Klausurergebnis wird nicht offiziell gewertet - es dient nur Ihrer Information. Allerdings: Die Punkte, die Sie in der Probeklausur erreichen, zählen wie normale Zusatzpunkte auf den Übungsblättern für Ihre Klausurzulassung.
  • Sonderübung / Fragestunde zur Vorbereitung auf die Abschlussklausur: Kurz vor der Abschlussklausur werden wir einen gemeinsamen Termin als Fragestunde zur Klausur und als Besprechung des letzten Übungsblattes (Blatt 12) vereinbaren. Es besteht keine Anwesentheitspflicht, die Anwesentheit wird aber als Klausurvorbereitung besonders empfohlen. Der Termin findet in 48-210 am Mittwoch, 14.3., um 10 Uhr statt.
  • komplette Verständnisfragen online: Bei den Übungsblättern kann jetzt eine Sammlung, die natürlich keine vollständige Liste ist, von Fragen incl. des Kapitels "Vektorräume" heruntergeladen werden. Die Beschäftigung mit diesen Fragen dient der Vorbereitung auf die Klausur.

 

 

Inhalt

In der Vorlesung werden einführende Konzepte und weitere Grundlagen der Zahlentheorie, Gruppentheorie, Ringtheorie und Linearen Algebra vermittelt. Dabei sollen folgende Ziele erreicht werden: Sie sollen einen guten Zugang zu der deduktiven Herangehensweise der Mathematik entwickeln, Sie sollen ein auch für weitere Studien grundlegendes Verständnis der betrachteten mathematischen Konzepte bekommen und Sie sollen einen Einblick in die direkten Anwendungen am Beispiel von kryptographischen Verfahren und fehlerkorrigierenden Codes erhalten.

Die Vorlesung gliedert sich in mehrere Abschnitte.

  • Grundkonstruktionen: Wir werden mit einer Einführung zu den Begriffen der Mengen, Relationen und Abbildungen starten. Zusätzlich besprechen wir grundlegende Techniken, zum Beispiel vollständige Induktion.
  • Zahlen: Wir führen den Ring der ganzen Zahlen als Äquivalenzklassen auf den natürlichen Zahlen ein und konstruieren daraus den Körper der rationalen Zahlen. Basierend auf dem Begriff der Primzahl beweisen wir den Fundamentalsatz der Arithmetik. Außerdem führen wir den euklidischen Algorithmus ein. Wir werden verstehen simultane Kongruenzen mittels chinesischem Restsatz zu lösen.
  • Gruppen: Wir starten mit Grundbegriffen der Gruppentheorie und schauen uns dann genauer Permutationsgruppen und allgemeine Operationen von Gruppen auf Mengen an. Schließlich definieren wir den Begriff des Normalteilers und der Quotientengruppe, um dann den Homomorphiesatz zu beweisen. 
  • Ringe: Nach einer grundlegenden Einführung betrachten wir Polynomringe sowie Z/nZ genauer. Letztlich führen wir die Eulersche Phi-Funktion ein und können den kleinen Satz von Fermat beweisen. Damit sind wir für die ersten grundlegenden Anwendungen gerüstet: RSA-Verschlüsselung und Diffie-Hellman Schlüsselaustausch. Weitere Themen dieses Abschnitts sind Ideale, euklidische Ringe und der verallgemeinerte Chinesische Restsatz. Dadurch gelangen wir zu weiteren Anwendungen: Modulares Rechnen und Lagrange-Interpolation.
  • Vektorräume: Dieser letzte Abschnitt der Vorlesung ist so grundlegend, dass er auch als eigenständiger Teil betrachtete werden kann. Er bietet eine Einführung in die lineare Algebra, die wiederum als Theorie der linearen Gleichungsysteme und der Vektorräume verstanden werden kann. Wir starten mit dem Gauß-Algorithmus für homogene lineare Gleichungssysteme, um über deren Lösungsräume den Begriff des Vektorraums zu motivieren. Diesen ergänzen wir durch Basis und Dimension. Wir betrachten strukturerhaltende Abbildungen zwischen Vektorräumen (Homomorphismen) und führen Matrizen als Darstellungsform derer ein. Auf dieser Grundlage können wir den Gauß-Algorithmus von einem abstrakten Standpunkt aus betrachten. Schließlich wollen wir Vektorraumhomorphismen modulo Basiswechsel klassifizieren und den Homomorphiesatz beweisen. Damit gelangen wir zum zweiten großen Anwendungsblock der Vorlesung: Wir können fehlerkorrigierende Codes für das Versenden von Nachrichten entwickeln. Wir schließen den Abschnitt und die Vorlesung mit dem Begriff der Determinanten und führen Eigenvektoren und Eigenwerte ein.

Skript und Literatur

Es wird kein öffentliches Manusskript zu dieser Vorlesung erstellt werden. Die Vorlesung wird aber im wesentlichen dem Skript von Janko Böhm folgen.

Darüber hinaus ist es empfehlenswert, den Stoff der Vorlesung auch aus anderen Blickwinkeln nachzulesen. Unten sind einige Literaturtipps genannt, vor deren potentieller Anschaffung Sie aber erstmal einen Blick in die betreffenden Bücher werfen sollten. Eventuell sind einige im Semesterapparat oder online für Studenten verfügbar.

  • B. Kreußler, G. Pfister: Mathematik für Informatiker; Algebra, Analysis, Diskrete Strukturen; Springer
  • G. Frey: Elementare Zahlentheorie; Vieweg
  • A. Beutelspacher: Kryptologie; Vieweg
  • G. Fischer: Lineare Algebra; Vieweg
  • K. Jänich: Lineare Algebra; Springer
  • W. Willems: Codierungstheorie; deGruyter

Verwendete Computeralgebrasysteme

  • Maple

Auf dem Server lindb.rhrk.uni-kl.de des Rechenzentrums haben Sie als Student/in Zugriff über Ihren RHRK-Account. Dazu loggen Sie sich unter Unix mit
ssh -X benutzername@lindb.rhrk.uni-kl.de
ein. Das graphische Interface von maple starten Sie dann mit 
module load maple/latest
xmaple

  • GAP

Das System GAP für Gruppentheorie ist frei verfügbar und kann unter https://www.gap-system.org/Releases/index.html heruntergeladen und installiert werden.



Übungsaufgaben

Auf dieser Webseite werden wöchentlich Aufgabenblätter bereitgestellt, die dazu dienen, den Vorlesungsstoff zu wiederholen, tiefer zu verstehen und einzuüben. Die Übungsaufgaben können Sie in Gruppen mit beliebig vielen Kommilitonen bearbeiten. Gerade die dabei entstehenden Diskussionen sind in der Regel sehr hilfreich. Es ist aber empfehlenswert, dass Sie eine gefundene Lösung selbst und in eigenen Worten aufschreiben. Die Abgaben zur Korrektur können und sollen dann in Gruppen von zwei oder drei Teilnehmern erfolgen. Die Abgaben werden von den Übungsleitern korrigiert und eine korrekte Lösung in der Übungsstunde mit Ihnen besprochen. Auch hier ist es aus didaktischen Gründen am besten, wenn Sie möglichst oft Ihre (möglicherweise korrigierte) Lösung selbst vortragen. Die Übungsleiter werden anhand der Abgaben dafür geeignete Teilnehmer vorab auswählen.

Einige Regeln zur Abgabe sollten noch formuliert werden:

  • Die Übungsblätter werden in der Regel eine Woche vor Abgabetermin online gestellt.
  • Die genauen Abgabetermine stehen in der unten angegebenen Liste.
  • Die Abgaben werden handschriftlich erstellt und in den gekennzeichneten Briefkasten im 48 (vierter Stock, Treppenhaus hinter der Feuerschutztür) eingeworfen.
  • Für eine vollständige Lösung sollen alle logischen Zwischenschritte - in ähnlicher Weise wie in der Vorlesung - formuliert werden.
  • Für jede Aufgabe werden in der Regel 0 bis 4 Punkte vergeben.
  • Wie oben angegeben sollen die Abgaben in Teams von zwei bis drei Mitgliedern erfolgen, wobei jedes Teammitglied für die gesamte Abgabe verantwortlich ist und zu dieser komplett Auskunft geben können muss. Dazu gehört auch, nach Aufforderung der Übungsleiter eine beliebige Aufgabe an der Tafel vorzutragen.

 

 

Leistungsnachweis und Abschlussklausur

Eine Klausurzulassung erwerben Sie dieses Semester durch die Erfüllung der folgenden beiden Punkte

  • Sinnvolle Bearbeitung von mindestens 70% aller Übungsaufgaben (ohne Zusatzaufgaben), wobei eine sinnvolle Bearbeitung vorliegt, sobald mindestens 1 Punkt auf die Lösung der Aufgabe vergeben wurde. ODER Erreichen von mindestens 40% aller erreichbaren Punkte (wobei die Bezugsgröße nicht die Punkte auf Zusatzaufgaben einbezieht)
  • Aktive Teilnahme an den Übungen u.a. durch: Bereitschaft zum Vorrechnen der Übungsaufgaben und regelmäßige Anwesenheit in den Übungsstunden.

Wenn Sie durch die oben genannten Kriterien oder in einem vorangegangenen Semester eine Zulassung erworben haben, können Sie an der Abschlussklausur teilnehmen.

Sie erhalten den Schein zur Vorlesung, wenn Sie diese Abschlussklausur bestehen. Die Übungspunkte sind nur für die Klausurzulassung relevant, als Prüfungsleistung zählt allein das Klausurergebnis.

Da die Vorlesung sowohl im Wintersemester als auch im Sommersemester angeboten wird, gibt es keine Nachklausur. Sollten Sie die Klausurzulassung erwerben, aber die Abschlussklausur nicht bestehen (oder nicht teilnehmen), können Sie die Klausur in künftigen Semestern mitschreiben. In diesem Fall empfehlen wir Ihnen dringend als Klausurvorbereitung an der entsprechenden Vorlesung und den zugehörigen Übungen teilzunehmen.

Die Abschlussklausur findet am Montag, den 19. März 2018, von 11:00 bis ca. 13:00 Uhr in 42-115 (Audimax) statt. Die Bearbeitungszeit für die Klausur beträgt 120 Minuten. Einzig zugelassene Hilfsmittel: Ein handschriftlich beidseitig beschriebenes DIN-A4-Blatt. Elektronische Geräte sind auszustellen und wegzupacken. Bitte bringen Sie den Studentenausweis zur Identitätskontrolle mit.