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
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 | |
1 | 23.10. | Algorithmen, Analyse, Rekursion | |
2 | 24.10. | Entwurfsprinzip 1: Divide & Conquer | |
3 | 24.10. | Divide & Conquer (Forts.)/Entwurfsprinzip 2: Dynamisches Programmieren | |
4 | 30.10. | Dynamisches Programmieren (Forts.)/Entwurfsprinzip 3: Backtracking | |
5 | 30.10. | Entwurfsprinzip 4: Greedy-Algorithmen | |
6 | 31.10. | Randomisierung | |
7 | 31.10. | Das Mastertheorem | |
8 | 07.11. | Quicksort: average case Analyse | |
9 | 07.11. | Bottom-up Heapsort | |
10 | 14.11. | Ultimatives Heapsort | |
11 | 14.11. | Medianberechnung in Linearzeit | |
12 | 20.11. | Der Dijkstra-Algorithmus | |
13 | 20.11. | Analyse des Dijkstra-Algorithmus | |
14 | 28.11. | Das TSP-Problem mit Dynamischem Programmieren | |
15 | 28.11. | String-Matching: Erste Versuche | |
16 | 05.12. | String Matching: Knuth-Morris-Pratt | |
17 | 05.12. | String Matching (Forts.) | pdf folgt |
18 | 12.12. | 2. Teil: Diskrete Strukturen | |
19 | 12.12. | Algorithmus von Euklid, Lemma von Bézout | |
20 | 18.12. | Modulare Arithmetik | |
21 | 18.12. | Anwendungen, Chinesischer Restsatz | |
22 | 19.12. | Der kleine Satz von Fermat | |
23 | 19.12. | Graphen | |
24 | 08.01. | Eulerwege, Eulerkreise | |
25 | 08.01. | Planare Graphen | |
26 | 09.01. | Das RSA-Verfahren | |
27 | 09.01. | Die Eulersche Phi-Funktion, Satz von Euler | |
28 | 15.01. | Ein exaktes Primzahlzertifikat | |
29 | 15.01. | Die Fibonacci-Zahlen | |
30 | 16.01. | Aufgaben und Zusammenfassung | |
31 | 16.01. | Wachstumsabschätzungen | |
32 | 22.01. | Primzahldichte, Bertrand'sches Postulat | |
33 | 22.01. | Aufgaben und Zusammenfassung | |
34 | 23.01. | Diskrete Wahrscheinlichkeit | |
35 | 23.01. | Zufallsvariablen, Unabhängigkeit, Varianz | |
36 | 29.01. | Kombinatorik | |
37 | 29.01. | Catalan-Zahlen, Dyck-Wörter | |
38 | 06.02. | Saturierte Binärbäume | |
39 | 06.02. | Satz von Ramsey: n=4 | |
40 | 06.02. | Satz von Ramsey: allgemein |
Übungen
-
Übungen: Mitarbeiter der Abteilung Theoretische Informatik
-
Ansprechpartner: Jan Philipp Wächter
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.