■
Team
■
Teaching
Oberseminar der Theorie
■
Winter 2023
■
Summer 2023
■
Winter 2022
■
Summer 2022
■
Winter 2021
■
Summer 2021
■
Winter 2020
■
Summer 2020
■
Winter 2019
■
Summer 2019
■
Winter 2018
Algebra und Kombinatorik in der Informatik
Algorithmische Gruppentheorie
Ausgewählte Themen der Theoretischen Informatik
Theoretische Informatik I
Ergänzungen zu Theoretische Informatik I
Theoretische Informatik III
■
Summer 2018
■
Winter 2017
■
Summer 2017
■
Winter 2016
■
Summer 2016
■
Winter 2015
■
Summer 2015
■
Winter 2014
■
Summer 2014
■
Winter 2013
■
Summer 2013
■
Winter 2012
■
Summer 2012
■
Winter 2011
Former Semester
BSc, Master-, Student-, Diplomathesis
StuPro/ ProjektINF/ SoPra/ FaPra
Exam Archive
Standard Textbooks
Descriptive Theory
■
Research
■
Publications
 

Theoretische Informatik III

Prüfung

Die Prüfungsergebnisse vom Sommersemester hängen gegenüber von Raum 1.106 aus. Die Einsicht findet am Donnerstag, den 17. Oktober um 13:00 Uhr in Raum 0.124 statt.

Die Prüfungsergebnisse hängen gegenüber von Raum 1.106 aus.</span> Die Einsicht findet am Dienstag, den 09. April um 13:15 Uhr in Raum 1.140 statt.

Zugelassene Hilfsmittel: Maximal einen beidseitig beschriebenen Bogen DIN A4, der mit dem Namen zu versehen und als Hilfsbogen eindeutig zu kennzeichnen ist. Keine elektronischen Hilfsmittel (wie zum Beispiel Taschenrechner).

Kandidaten, die zur Prüfung „Theoretische Informatik III” angemeldet sind, schreiben in folgenden Räumen:

Nachname Raum
A V 57.04
B → Sh V 47.01
Si → Z V 57.03

Kandidaten, die die Prüfung als Ersatz für „Algorithmen und Berechenbarkeit” ablegen, schreiben die Prüfung in Raum V 57.03.

Vorlesung

Prof. Dr. Ulrich Hertrampf

Ankündigung

Mittlerweile hängt die Scheinliste aus. Bitte prüfen Sie, ob Ihre Matrikelnummer darauf aufgeführt ist, um einen reibungslosen Ablauf bei der Prüfung sicherzustellen. Bitte tun Sie dies auch dann, wenn Sie nicht davon ausgehen, die Scheinbedingungen zu erfüllen. Andernfalls kann es passieren, dass Sie eine Verwaltungsfünf erhalten, wenn Sie irrtümlich davon ausgehen keine Zulassung zu besitzen und zur Prüfung nicht erscheinen.

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 29.1.
Mi 15:45-17:15 V47.02 wöchentlich vom 24.10. bis 6.2. (außer 21.11. und 30.1)

Insgesamt 20 Termine. (Bitte beachten Sie: Wegen der StuPro-Vorstellung am 5. Februar entfällt an diesem Tag die Vorlesung.)

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
0 23.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
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
3806.02. Saturierte Binärbäume pdf
3906.02. Satz von Ramsey: n=4 pdf
4006.02. Satz von Ramsey: allgemein pdf

Ü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.
18.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.
Übungsgruppe A9 entfiel am 17.01. und findet stattdessen am Freitag, den 18.01. um 8:00 Uhr in Raum 0.363 statt. Sollten Sie diesen Termin nicht wahrnehmen können, besuchen Sie bitte den Termin von Übungsgruppe B9 oder eine andere Übungsgruppe (und geben Sie dem Tutor dort Bescheid).

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
    Neue Version: Hinweis zu Fibonacci-Zahlen mit negativem Index

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

[Jun’23] The paper “Parallel algorithms for power circuits and the word problem of the Baumslag group” by Caroline Mattes and Armin Weiß has been accepted at Computational Complexity.

[Oct’22] The paper “Lower Bounds for Sorting 16, 17, and 18 Elements” by Florian Stober and Armin Weiß has been accepted at ALENEX 2023.

[Sep’22] The paper “Conelikes and Ranker Comparisons” by Viktor Henriksson and Manfred Kufleitner has been accepted at LATIN 2022.

[Sep’22] The paper “Improved Parallel Algorithms for Generalized Baumslag Groups” by Caroline Mattes and Armin Weiß has been accepted at LATIN 2022.

[Apr’22] The paper “Reachability Games and Parity Games” by Volker Diekert and Manfred Kufleitner has been accepted at ICTAC 2022.

[Apr’22] The paper “Satisfiability Problems for Finite Groups” by Pawel M. Idziak, Piotr Kawalek, Jacek Krzaczkowski and Armin Weiß has been accepted at ICALP 2022.

[Mar’22] The paper “The Power Word Problem in Graph Products” by Florian Stober and Armin Weiß was accepted at DLT 2022.

[Nov’20] Volker Diekert is Partner Investigator in the Australian ARC grant “Geodetic groups: foundational problems in algebra and computer science” at University of Technology Sydney.

[Apr’20] The paper “Groups with ALOGTIME-hard word problems and PSPACE-complete circuit value problems” by Laurent Bartholdi, Michael Figelius, Markus Lohrey and Armin Weiß has been accepted at CCC 2020.

[Apr’20] The paper “Hardness of equations over finite solvable groups under the exponential time hypothesis” by Armin Weiß has been accepted at ICALP 2020.

[Dec’19] The paper “An Automaton Group with PSPACE-Complete Word Problem” by Jan Philipp Wächter and Armin Weiß has been accepted at STACS 2020.

[Nov’19] Carlos Camino was awarded the stuvus Special Prize for exceptional commitment in teaching.

[Jun’19] The paper “The power word problem” by Markus Lohrey and Armin Weiß has been accepted at MFCS 2019.

[May’19] The paper “On the Average Case of MergeInsertion” by Florian Stober and Armin Weiß has been accepted at IWOCA 2019.

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