Vorlesung

Prof. Dr. Ulrich Hertrampf

Termine

Zeit Raum Termine
Di 17:30-19:00 V38.01 am 23.10., 30.10. und 20.11.
Di 15:45-17:15 V38.04 wöchentlich vom 18.12. bis 5.2.
Mi 15:45-17:15 V47.02 wöchentlich vom 24.10. bis 6.2. (außer 21.11. und 30.1)

Insgesamt 21 Termine.

Lehrveranstaltungsäquivalenz

„Ich habe einen Schein in/die Prüfung abgelegt in [Propädeutikum Tonen und Töpfern]1. Wegen eines Studiengangswechsels/Wechsels der Prüfungsordnung benötige ich jedoch einen Schein/die Prüfung in [Theorie des Unterwasserkorbwebens]. Was kann ich tun?”

Wenden Sie sich mit solchen Fragen bitte während seiner Sprechstunde an Professor Hertrampf oder schreiben ihm eine Email.

1 Die genaue Fächerkombination kann bei Ihnen abweichen.

Inhalt

Der erste Teil der Vorlesung (11 Doppelstunden, bis Mitte Dezember) orientiert sich an dem Buch ALGORITHMIK von Uwe Schöning (Spektrum Lehrbuch).

Danach gibt es einen zweiten Teil (10 Doppelstunden), in dem das Thema Diskrete Strukturen behandelt wird. Für diesen Teil dient als Grundlage das Buch ELEMENTE DER DISKRETEN MATHEMATIK von Diekert, Kufleitner, Rosenberger.

Folien und voraussichtliche Termine:
Die Einheiten der nächsten Vorlesung sind stets grün unterlegt.

Die zugreifbaren Folien werden entsprechend in der Vorlesung erarbeitet, und zwar in jeder Vorlesung zwei Einheiten - daher wird es die Einheiten mit den Nummern 0 bis 41 geben.

Einheit Datum Inhalt Folien
023.10.Vorstellung, Arbeitsweise pdf
123.10. Algorithmen, Analyse, Rekursion pdf
224.10. Entwurfsprinzip 1: Divide & Conquer pdf
324.10. Divide & Conquer (Forts.)/Entwurfsprinzip 2: Dynamisches Programmieren pdf
430.10. Dynamisches Programmieren (Forts.)/Entwurfsprinzip 3: Backtracking pdf
530.10. Entwurfsprinzip 4: Greedy-Algorithmen pdf
631.10. Randomisierung pdf
731.10. Das Mastertheorem pdf
807.11. Quicksort: average case Analyse pdf
907.11. Bottom-up Heapsort pdf
1014.11. Ultimatives Heapsort pdf
1114.11. Medianberechnung in Linearzeit pdf
1220.11. Der Dijkstra-Algorithmus pdf
1320.11. Analyse des Dijkstra-Algorithmus pdf
1428.11. Das TSP-Problem mit Dynamischem Programmieren pdf
1528.11. String-Matching: Erste Versuche pdf
1605.12. String Matching: Knuth-Morris-Pratt pdf folgt
1705.12. String Matching (Forts.) pdf folgt
1812.12. 2. Teil: Diskrete Strukturen pdf
1912.12. Algorithmus von Euklid, Lemma von Bézout pdf
2018.12. Modulare Arithmetik pdf
2118.12. Anwendungen, Chinesischer Restsatz pdf
2219.12. Der kleine Satz von Fermat pdf
2319.12. Graphen pdf
2408.01. Eulerwege, Eulerkreise pdf
2508.01. Planare Graphen pdf
2609.01. Das RSA-Verfahren pdf
2709.01. Die Eulersche Phi-Funktion, Satz von Euler pdf
2815.01. Ein exaktes Primzahlzertifikat pdf
2915.01. Die Fibonacci-Zahlen pdf
3016.01. Aufgaben und Zusammenfassung pdf
3116.01. Wachstumsabschätzungen pdf
3222.01. Primzahldichte, Bertrand'sches Postulat pdf
3322.01. Aufgaben und Zusammenfassung pdf
3423.01. Diskrete Wahrscheinlichkeit pdf
3523.01. Zufallsvariablen, Unabhängigkeit, Varianz pdf
3629.01. Kombinatorik pdf
3729.01. Catalan-Zahlen, Dyck-Wörter pdf
3805.02. Saturierte Binärbäume pdf
3905.02. Satz von Ramsey: n=4 pdf
4006.02. Satz von Ramsey: allgemein pdf
4106.02. Zusammenfassung pdf folgt

Übungen

Termine

Gruppe Tutor Zeit Raum Blatt 1 Blatt 2 Blatt 3 Blatt 4 Blatt 5 Blatt 6
🌴 A 1 J.P. Wächter Fr. 15:45 – 17:15 V38.03 02.11. 16.11. 30.11. 14.12. 11.01. 25.01.
🌵 A 2 J. Heusler Fr. 15:45 – 17:15 0.124 02.11. 16.11. 30.11. 14.12. 11.01. 25.01.
🌶 A 3 M. Gaißert Mo. 11:30 – 13:00 0.124 05.11. 19.11. 03.12. 17.12. 14.01. 28.01.
🌹 A 4 T. Böpple Mo. 15:45 – 17:15 0.124 05.11. 19.11. 03.12. 17.12. 14.01. 28.01.
🌻 A 5 J. Kittelberger Di. 09:45 – 11:15 0.124 06.11. 20.11. 04.12. 18.12.* 15.01.* 29.01.
🌽 A 6 L. Baur Di. 09:45 – 11:15 0.363 06.11. 20.11. 04.12. 18.12.* 15.01.* 29.01.
🍅 A+B 7 S. Hasler Di. 14:00 – 15:30 0.124 06.11.
&
13.11.
20.11.
&
27.11.
04.12.
&
11.12.
18.12.
&
08.01.
15.01.
&
22.01.
29.01.
&
05.02.
🍆 A 8 A. Bühler Mi. 17:30 – 19:00 0.363 07.11. 21.11. 05.12. 19.12. 16.01. 30.01.
🍇 A 9 F. Stober Do. 08:00 – 09:30 0.108 08.11. 22.11. 06.12. 20.12. 17.01. 31.01.
Gruppe Tutor Zeit Raum Blatt 1 Blatt 2 Blatt 3 Blatt 4 Blatt 5 Blatt 6
🍊 B 1 J. Obst Fr. 15:45 – 17:15 0.124 09.11. 23.11. 07.12. 21.12. 18.01. 01.02.
🍋 B 3 M. Gaißert Mo. 11:30 – 13:00 0.124 12.11. 26.11. 10.12. 07.01. 21.01. 04.02.
🍌 B 4 T. Böpple Mo. 15:45 – 17:15 0.124 12.11. 26.11. 10.12. 07.01. 21.01. 04.02.
🍍 B 5 J. Kittelberger Di. 09:45 – 11:15 0.124 13.11. 27.11. 11.12. 08.01.* 22.01.* 05.02.
🍎 B 6 L. Baur Di. 09:45 – 11:15 0.363 13.11. 27.11. 11.12. 08.01.* 22.01.* 05.02.
🍐 B 8 A. Bühler Mi. 17:30 – 19:00 0.363 14.11. 28.11. 12.12. 09.01. 23.01. 06.02.
🍒 B 9 F. Stober Do. 08:00 – 09:30 0.108 15.11. 29.11. 13.12. 10.01. 24.01. 07.02.
🍓 B 10 J. Heusler Do. 08:00 – 09:30 0.447 15.11. 29.11. 13.12. 10.01. 24.01. 07.02.

Übungsgruppe A+B7 findet wöchentlich statt. Hier werden die Lösungen ausführlicher besprochen. Die anderen Übungsgruppen finden jeweils 14-täglich statt.
*: Die Übungsgruppen A5 und A6 sowie B5 und B6 finden für Blatt 4 und 5 jeweils gemeinsam in Raum 0.124 statt.

Blätter

  • Blatt 1, Abgabe bis Mi., 31.10.18 um 13:15 Uhr (Ende des Anmeldezeitraums)
    Das Passwort zur Übungsanmeldung finden Sie hier.
  • Blatt 2, Abgabe bis Do., 15.11.18 um 13:15 Uhr
    Neue Version: Bei Aufgabe 5 gab es leider einen Off-By-One-Fehler.
    Noch neuere Version: Bei Aufgabe 5 gab es leider einen weiteren Off-By-One-Fehler.
  • Blatt 3, Abgabe bis Do., 29.11.18 um 13:15 Uhr
    Neue Version: Aufgabe 1: Es muss b > 1 heißen; Aufgabe 2: Der Summenindex muss bei i = 1 beginnen; Aufgabe 3, A4: Schleife klarer formuliert.
  • Blatt 4, Abgabe bis Do., 13.12.18 um 13:15 Uhr
    Neue Version: Tipp bei Aufgabe 4
  • Blatt 5, Abgabe bis Do., 10.01.18 um 13:15 Uhr
  • Blatt 6, Abgabe bis Do., 24.01.18 um 13:15 Uhr

Scheinkriterien

Scheinbedingung ist

  • das Erreichen von mindestens 50% der möglichen Punkte in allen schriftlichen Aufgaben und
  • eine aktive Übungsteilnahme; dies bedeutet insbesondere, dass Sie mindestens einmal in Ihrer Übungsgruppe vorgerechnet haben müssen.

Weitere Informationen zu den Scheinbedingung finden Sie auf Blatt 1.

Ergänzungen

Die erste Ergänzung findet am Freitag, den 26.10. statt. Zeit und Raum werden auf der Ergänzungsseite bekanntgegeben. Dort finden Sie auch alle weiteren Informationen zur Ergänzung.

Literatur

Algorithmen:

  • Uwe Schöning: Algorithmik. Springer Spektrum, 2001.
  • Vorlesungsskript zur Diplomvorlesung Entwurf und Analyse von Algorithmen

Diskrete Strukturen:

  • Volker Diekert, Manfred Kufleitner, Gerhard Rosenberger: Elemente der Diskreten Mathematik. Walter de Gruyter, 2013.

News

[Oct’18] The paper “Worst-Case Efficient Sorting with QuickMergesort” by Stefan Edelkamp and Armin Weiß has been accepted at ALENEX 2019.

[Jun’18] At CCC 2018, Lukas Fleischer received a Best Student Paper Award for his submission “On the Complexity of the Cayley Semigroup Membership Problem”.

[Jun’18] The paper “Testing Simon’s congruence” by Lukas Fleischer and Manfred Kufleitner was accepted at MFCS 2018.

[Jun’18] The paper “The Intersection Problem for Finite Semigroups” by Lukas Fleischer was accepted at DLT 2018.

[Apr’18] The paper “The isomorphism problem for finite extensions of free groups is in PSPACE” by Géraud Sénizergues and Armin Weiß was accepted at ICALP 2018.

[Apr’18] The paper “On the Complexity of the Cayley Semigroup Membership Problem” by Lukas Fleischer was accepted at CCC 2018.

[Jan’18] On March 24-29, 2019 Volker Diekert, Markus Lohrey, Olga Kharlampovich and Alexei Miasnikov will organize the Schloss Dagstuhl Seminar “Algorithmic Problems in Group Theory”.

[Dec’17] The paper “The Intersection Problem for Finite Monoids” by Lukas Fleischer and Manfred Kufleitner was accepted at STACS 2018.

[Jun’17] At the 12th International Computer Science Symposium in Russia (CSR), Lukas Fleischer and Manfred Kufleitner received a Best Paper Award for their publication “Green’s Relations in Finite Transformation Semigroups”, and Armin Weiss received a Best Paper Award for “The conjugacy problem in free solvable groups and wreath product of abelian groups is in $\text{TC}^0$ \text{TC}^0 “ which is joint work with Alexei Miasnikov and Svetla Vassileva.