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 10 ist nun korrigiert (Folien 10.3 und 10.5 wurden geändert)

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 folgt
1320.11. Analyse des Dijkstra-Algorithmus pdf folgt
1428.11. Das TSP-Problem pdf folgt
1528.11. Analyse des TSP-Algorithmus pdf folgt
1605.12. String Matching pdf folgt
1705.12. String Matching (Forts.) pdf folgt
1812.12. Algebraische und Zahlentheoretische Algorithmen (1) pdf folgt
1912.12. Algebraische und Zahlentheoretische Algorithmen (2) pdf folgt
2018.12. Algebraische und Zahlentheoretische Algorithmen (3) pdf folgt
2118.12. Algebraische und Zahlentheoretische Algorithmen (4) pdf folgt
2219.12. Einführung: Diskrete Strukturen pdf folgt
2319.12. Diskrete Strukturen (1) pdf folgt
*xx.12. Weihnachten kein pdf
2408.01. Diskrete Strukturen (2) pdf folgt
...xx.01. Fortsetzung folgt demnächst... ...

Ü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.

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

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.