Prüfung

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

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