Organisatorisches
- Dozent: Volker Diekert
- Übungen: die wissenschaftlichen Mitarbeiter der theoretischen Informatik
- Ansprechpartner: Armin Weiß
Vorlesungs-/Übungstermine
| Zeit | Raum |
|---|---|
| Mo., 14:00 – 15:30 | V38.04 |
| Di., 09:45 – 11:15 | 0.124 |
Die erste Vorlesung findet am 8. April statt.
Bitte beachten Sie kurzfristige Termin- und Raumänderungen, die an dieser Stelle veröffentlicht werden.
Ab 30.04. findet die Vorlesung dienstags in Raum 0.124 statt.
Inhalte der Vorlesung
Folgende Tabelle gibt eine ungefähre Übersicht über die behandelten Themen.
| Termin | Inhalt |
|---|---|
| 08.04. | Fibonacci-Zahlen (Matrix-Darstellung, explizite Formel, GGT von Fibonacci-Zahlen), lineare Rekurrenzen |
| 09.04. | Lösen linearer Gleichungssysteme über ganzen und natürlichen Zahlen |
| 15.04. | Binomialkoeffizienten, Binomialsatz, Wachstum von Binomialkoeffizienten, obere und untere Schranke für das Wachstum des KGV |
| 16.04. | Aussagen zur Primzahldichte, Bertrandsches Postulat |
| 23.04. | Einführung Primzahltests, Vorstellung AKS-Primzahltest, Beweis Lemma 4.6 (DAM) |
| 29.04. | f irreduzibel ⇔ K[X]/f Körper; Zerfällungskörper (mit Existenzbeweis), AKS-Primzahltest Teil 1 |
| 30.04. | AKS-Primzahltest Teil 2 |
| 06.05. | Besprechung Blatt 1 |
| 07.05. | Besprechung Blatt 1 |
| 13.05. | AKS-Primzahltest Teil 3, Karatsuba-Multiplikation, Diskrete Fouriertransformation |
| 14.05. | keine Vorlesung |
| 20.05. | Schönhage-Strassen-Multiplikation Teil 1 |
| 21.05. | Schönhage-Strassen-Multiplikation Teil 2 |
| 27.05. | Einführung MSO, Beweis regulär => MSO-definierbar |
| 28.05. | Beweis MSO-definierbar => regulär, Einführung LTL |
| 03.06. | Syntaktische Monoide, minimale Automaten, Definition von Rat(M), Reg(M), SF(M) für beliebige Monoide M |
| 04.06. | Beweis Star-free => aperiodisch |
| 17.06. | Divisoren, Lokale Divisoren, Satz von Schützenberger: aperiodisch = Star-free |
| 18.06. | Wiederholung Lokale Divisoren, Besprechung Blatt 2 |
| 24.06. | LTL = AP |
| 25.06. | Fortsetzung Besprechung Blatt 2 |
| 01.07. | Einführung elliptische Kurven |
| 02.07. | Elliptische Kurven, Polynomring über einer elliptische Kurve |
| 08.07. | Elliptische Kurven, Divisoren |
| 09.07. | Abschluss Beweis: Punkte auf einer elliptischen Kurven bilden eine abelsche Gruppe |
| 15.07. | Pseudokurven |
| 16.07. | Faktorisierung mit elliptischen Kurven, Primzahlzertifizierung nach Goldwasser-Kilian |
Übungsblätter
- Blatt 1, Besprechung am 06. und 07. Mai
- Blatt 2, Besprechung am 18. und 24. Juni
- Blatt 3, keine Besprechung
Scheinbedingungen
Scheinbedingung ist eine aktive Teilnahme an den Übungen, insbesondere sollte mindestens einmal vorgerechnet werden. Die Erfüllung der Scheinkriterien ist eine notwendige Voraussetzung um zur Prüfung zugelassen zu werden.
Literatur
- Vorlesungsfolien
- Volker Diekert, Manfred Kufleitner, Gerhard Rosenberger:
Elemente der Diskreten Mathematik, Walter de Gruyter, 2013. - Volker Diekert, Manfred Kufleitner, Gerhard Rosenberger:
Diskrete algebraische Methoden, Walter de Gruyter, 2013. - Volker Diekert, Manfred Kufleitner, Gerhard Rosenberger, Ulrich Hertrampf:
Discrete Algebraic Methods, Walter de Gruyter, 2016. - Philippe Flajolet, Robert Sedgewick:
Analytic Combinatorics, Cambridge University Press, 2009 - Ronald L. Graham, Donald E. Knuth, Oren Patashnik:
Concrete Mathematics: A Foundation for Computer Science, Addison-Wesley, 1994 - Jiří Matoušek, Jaroslav Nešetřil:
Diskrete Mathematik - Eine Entdeckungsreise, Springer-Verlag, 2002