Prüfungsergebnisse Herbst 2020
Die Prüfungsergebnisse wurden versandt.
Prüfungsergebnisse Frühjahr 2020
Notenschlüssel In dem unten stehenden Dokument finden Sie den Notenschlüssel zur Prüfung Theoretische Informatik III am 27.02.20
Für die Prüfung Algorithmik gilt folgender Notenschlüssel:
Punkte | Note |
---|---|
ab 96 | 1,0 |
ab 92 | 1,3 |
ab 88 | 1,7 |
ab 83 | 2,0 |
ab 78 | 2,3 |
ab 73 | 2,7 |
ab 68 | 3,0 |
ab 63 | 3,3 |
ab 57 | 3,7 |
ab 50 | 4,0 |
unter 50 | 5,0 |
Vorlesung
Termine
Zeit | Raum | Termine |
---|---|---|
Do 17:30-19:00 | V38.01 | wöchentlich vom 17.10. bis 6.2. (außer 24.10., 7.11., 12.12., 30.1.) |
Mi 15:45-17:15 | V38.01 | wöchentlich vom 23.10. bis 5.2. (außer 13.11., 20.11., 18.12., 22.1.) |
Insgesamt 21 Termine - genaue Termine können der Tabelle unten entnommen werden.
Scheinliste: Die Scheinliste hängt nun am schwarzen Brett des FMI aus. Auf dieser Liste stehen alle Studenten, welche im WS 19/20 den Schein für die Theoretische Informatik 3 erhalten haben. Bitte überprüfen Sie, ob Sie auf dieser Liste stehen, sollten Sie die Scheinkriterien erfüllt haben.
Scheinklausur: Die erste Scheinklausur findet am 18.12. um 15:45 (übliche Vorlesungszeit) statt. Thematisch werden die Inhalte aus dem Block Algorithmik der Vorlesung geprüft werden.
Eine Musterlösung für die erste Scheinklausur wurde im entsprechenden ILIAS-Kurs zur Verfügung gestellt.
Zweite Scheinklausur: Die zweite Scheinklausur findet am 30.01. um 17:30 (übliche Vorlesungszeit) statt. Thematisch werden die Inhalte aus dem Teil “Diskrete Strukturen” der Vorlesung geprüft werden. Dabei sind die Themen, welche bis zum 23.01. in der Vorlesung behandelt wurden, für die Klausur relevant.
Raumaufteilung für die Scheinklausur am 30.01. Die Studenten, deren Nachnamen mit den Buchstaben A-L beginnen, schreiben in V38.01 die Klausur, die Studenten deren Namen mit M-Z beginnen schreiben die Klausur in V38.04.
Inhalt
Der erste Teil der Vorlesung (9-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 fett markiert.
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 |
---|---|---|
00 | 17.10. | Vorstellung, Arbeitsweise (pdf) |
01 | 17.10. | Algorithmen, Analyse, Rekursion (pdf) |
02 | 23.10. | Entwurfsprinzip 1: Divide & Conquer (pdf) |
03 | 23.10. | Divide & Conquer (Forts.) / Entwurfsprinzip 2: Dynamisches Programmieren (pdf) |
04 | 30.10. | Dynamisches Programmieren (Forts.)/Entwurfsprinzip 3: Backtracking (pdf) |
05 | 30.10. | Entwurfsprinzip 4: Greedy-Algorithmen (pdf) |
06 | 31.10. | Randomisierung (pdf) |
07 | 31.10. | Das Mastertheorem (pdf) |
08 | 06.11. | Quicksort und seine Varianten (pdf) |
09 | 06.11. | Average-case Analyse von Quicksort, Heapsort (pdf) |
10 | 14.11. | Bottom-up Heapsort, Ultimatives Heapsort (pdf) |
11 | 14.11. | Medianberechnung in Linearzeit (pdf) |
12 | 21.11. | Der Dijkstra-Algorithmus (pdf) |
13 | 21.11. | Analyse des Dijkstra-Algorithmus (pdf) |
14 | 27.11. | Das TSP-Problem mit Dynamischem Programmieren (pdf) |
15 | 27.11. | String-Matching: Erste Versuche (pdf) |
16 | 28.11. | String Matching mit endlichem Automat (pdf) |
17 | 28.11. | String Matching: Der KMP-Algorithmus (nach Knuth, Morris, Pratt) (pdf) |
18 | 04.12. | 2. Teil: Diskrete Strukturen (pdf) |
19 | 04.12. | Algorithmus von Euklid, Lemma von Bézout (pdf) |
20 | 05.12. | Modulare Arithmetik (pdf) |
21 | 05.12. | Anwendungen der modularen Arithmetik (pdf) |
22 | 11.12. | Der Chinesische Restsatz(pdf) |
23 | 11.12. | Fermat-Test, Graphen (pdf) |
24 | 19.12. | Wege und Kreise (pdf) |
25 | 19.12. | Eulerwege und Eulerkreise (pdf) |
26 | 08.01. | Planare Graphen (pdf) |
27 | 08.01. | Das RSA-Verfahren (pdf) |
28 | 09.01. | Die Eulersche phi-Funktion (pdf) |
29 | 09.01. | Satz von Euler, exaktes Primzahlzertifikat (pdf) |
30 | 15.01. | Fibonacci-Zahlen (pdf) |
31 | 15.01. | Aufgaben und Zusammenfassung (pdf) |
32 | 16.01. | Wachstumsabschätzungen (pdf) |
33 | 16.01. | Primzahldichte, Bertrand’sches Postulat (pdf) |
34 | 23.01. | Aufgaben und Zusammenfassung (pdf) |
35 | 23.01. | Diskrete Wahrscheinlichkeit (pdf) |
36 | 29.01. | Erwartungswerte, Varianz (pdf) |
37 | 29.01. | Kombinatorik (pdf) |
38 | 05.02. | Catalan-Zahlen, Dyck-Wörter (pdf) |
39 | 05.02. | Saturierte Binärbäume (pdf) |
40 | 06.02. | Satz von Ramsey: n=4 (pdf) |
41 | 06.02. | Satz von Ramsey: allgemein (pdf) |
Übungen
Termine
Gruppe | Tutor | Termin | Blatt 1 | Blatt 2 | Blatt 3 | Blatt 4 | Blatt 5 | Blatt 6 |
---|---|---|---|---|---|---|---|---|
01 | Proissl | Mo 11:30-13:00, 0.124 | 28.10. | 11.11. | 25.11. | 09.12. | 13.01. | 27.01. |
02 | Stober | Mo 14:00-15:30, 0.363 | 28.10. | 11.11. | 25.11. | 09.12. | 13.01. | 27.01. |
03 | Walter | Di 08:00-09:30, 0.363 | 29.10. | 12.11. | 26.11. | 10.12. | 14.01. | 28.01. |
04 | Obst | Di 14:00-15:30, 0.124 | 29.10. | 12.11. | 26.11. | 10.12. | 14.01. | 28.01. |
05 | Kotowsky | Di 14:00-15:30, 0.363 | 29.10. | 12.11. | 26.11. | 10.12. | 14.01. | 28.01. |
06 | entfällt | |||||||
07 | Gaißert | Mi 11:30-13:00, 0.363 | 30.10. | 13.11. | 27.11. | 11.12. | 15.01. | 29.01. |
08 | Camino | Mi 11:30-13:00, 0.124 | 30.10. | 13.11. | 27.11. | 11.12. | 15.01. | 29.01. |
09 | Mattes | Mo 11:30-13:00, 0.124 | 04.11. | 18.11. | 02.12. | 16.12. | 20.01. | 03.02. |
10 | Proissl | Mo 14:00-15:30, 0.363 | 04.11. | 18.11. | 02.12. | 16.12. | 20.01. | 03.02. |
11 | Walter | Di 08:00-09:30, 0.363 | 05.11. | 19.11. | 03.12. | 17.12. | 21.01. | 04.02. |
12 | Obst | Di 14:00-15:30, 0.124 | 05.11. | 19.11. | 03.12. | 17.12. | 21.01. | 04.02. |
13 | Kotowsky | Di 14:00-15:30, 0.363 | 05.11. | 19.11. | 03.12. | 17.12. | 21.01. | 04.02. |
14 | Klein | Di 17:30-19:00, 0.447 | 05.11. | 19.11. | 03.12. | 17.12. | 21.01. | 04.02. |
15 | Gaißert | Mi 11:30-13:00, 0.363 | 06.11. | 20.11. | 04.12. | 18.12. | 22.01. | 05.02. |
16 | Camino | Mi 11:30-13:00, 0.124 | 06.11. | 20.11. | 04.12. | 18.12. | 22.01. | 05.02. |
Blätter
Die mit [P] gekennzeichneten Aufgaben werden in der Übung als Vorbereitung besprochen.
Alle anderen Aufgaben sind schriftlich im Ilias abzugeben.
Abgabegruppen mit bis zu 3 Personen sind erwünscht.
- Blatt 1 (Abgabe bis 13.11.2019, 15:45 Uhr)
- Blatt 2 (Abgabe bis 27.11.2019, 15:45 Uhr)
- Blatt 3 (Abgabe bis 11.12.2019, 15:45 Uhr)
- Blatt 4 (Abgabe bis 6.1.2020, 15:45 Uhr )
- Blatt 5 (Abgabe bis 27.1.2020, 15:45)
- Blatt 6 (Abgabe bis 10.2.2020, 15:45)
Achtung Bei der Aufgabe 1 (i) auf Blatt 5 gab es eine Änderung zur letzten Version. Die jetzt hier hochgeladene Version ist die, die bearbeitet werden soll!
Achtung Aufgrund der Übungstermine wurde der Abgabezeitpunkt von Blatt 5 nun verschoben!
Scheinkriterien
Es müssen alle der folgenden Bedingungen erfüllt sein:
- Mind. die Hälfte der Punkte aus Quizzen und schriftlichen Abgaben (summiert)
- In beiden Scheinklausuren müssen jeweils mind. 30% der jeweiligen Punkte erreicht werden
- In beiden Scheinklausuren müssen insgesamt mind. 50% der gesamten Punkte erreicht werden (d.h. falls in der ersten Scheinklausur 35% erreicht werden müssen in der zweiten Scheinklausur 65% erreicht werden)
Ergänzungen
Die TI3-Ergänzung findet (ab 21.10.19) Montags um 9:45 Uhr in V7.04 statt.
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.