Effiziente Algorithmen 1+2 (Sommer 2019)
Aktuelles
- Zum Logbuch.
- Teil 1 umfasst die 13 Vorlesungen vom 16.04. bis 28.05., Teil 2 die 13 Vorlesungen vom 04.06. bis 18.07.
Organisatorisches
- Dozent: Prof. Dr. Martin Hoefer
- Übungsbetrieb: Dr. Daniel Schmand
- Einträge im LSF: Teil 1, Teil 2, beide Teile
- Vorlesung: Dienstag und Donnerstag, 10:15 Uhr - 11:45 Uhr, Magnus-Hörsaal (R.M.S. 11-15)
- Tutorien:
Dienstag, 14:15 - 15:45 Uhr SR 11 (R.M.S. 11-15) Martin Ludwig Mittwoch, 14:15 - 15:45 Uhr NM 113 (Neue Mensa) Conrad Schecker
- Klausur: Montag, 29.07.2019, 9:00 Uhr - 12:00 Uhr, Magnus-Hörsaal
- Nachklausur: Montag, 07.10.2019, 9:00 Uhr - 12:00 Uhr, Magnus-Hörsaal
- Erlaubtes Hilfsmittel: Jede Person darf genau ein beidseitig handbeschriebenes DIN-A4-Blatt benutzen.
Materialien
Vorlesungsfolien und Notizen
| Kapitel | Stand | Vorlesungen | |
|---|---|---|---|
| Teil 1: | |||
| Organisation, Einführung | Folien | 16.04.2019 | 16.04. |
| Randomisierte Algorithmen 1 | Folien | 09.05.2019 | 25.04. - 09.05. |
| Markoff-Ketten | Folien | 21.05.2019 | 09.05. - 21.05. |
| Online Algorithmen 1 | Folien | 28.05.2019 | 23.05., 28.05. |
| Einführung | Notizen | 26.04.2019 | 16.04., 23.04. |
| Stochastik Wiederholung | Notizen | 16.04.2019 | 18.04. |
| Optimalität im Sekretärproblem | Notizen | 23.04.2019 | 23.04. |
| Randomisierte Algorithmen 1 | Notizen | 07.05.2019 | 25.04. - 07.05. |
| Miller-Rabin Test | Notizen | 30.04.2019 | 30.04. |
| Markoff-Ketten | Notizen | 21.05.2019 | 09.05. - 21.05. |
| Lastbalancierung mit Random Walks | Notizen | 21.05.2019 | 21.05., 23.05. |
| Online Algorithmen 1 | Notizen | 28.05.2019 | 23.05., 28.05. |
| Teil 2: | |||
| Online Algorithmen 2 | Folien | 18.06.2019 | 04.06. - 25.06. |
| Randomisierte Algorithmen 2 | Folien | 02.07.2019 | 25.06. - 02.07. |
| Online Algorithmen 2 | Notizen | 11.06.2019 | 04.06. - 18.06. |
| Randomisierte Algorithmen 2 | Notizen | 24.06.2019 | 25.06. - 02.07. |
| Pseudo-Random Generatoren | Notizen | 04.07.2019 | 04.07. |
| Flüsse und Matchings | Notizen | 25.07.2019 | 09.07. - 18.07. |
Übungsblätter
Bitte bei der Abgabe von Übungsblättern darauf achten, dass die Abgaben geheftet sind und zum Aufschreiben nur dokumentenechte Stifte (kein Bleistift, kein Tipp-Ex, ...) benutzt wurden. Außerdem sind Antworten, wenn nicht anders angegeben, grundsätzlich immer zu begründen oder zu beweisen.Hausaufgaben können auch in einem pdf-Dokument zusammengefasst per Mail an Daniel Schmand (Mailadresse ist unten auf den Übungsblättern) abgegeben werden.
Teil 1:
- Blatt 1, Ausgabe: 16.04.2019. Abgabe bis 23.04.2019, 10:15 Uhr.
- Blatt 2, Ausgabe: 23.04.2019. Abgabe bis 30.04.2019, 10:15 Uhr.
- Blatt 3, Ausgabe: 26.04.2019. Abgabe bis 07.05.2019, 10:15 Uhr.
- Blatt 4, Ausgabe: 07.05.2019. Abgabe bis 14.05.2019, 10:15 Uhr.
- Blatt 5, Ausgabe: 13.05.2019. Abgabe bis 21.05.2019, 10:15 Uhr.
- Blatt 6, Ausgabe: 21.05.2019. Abgabe bis 28.05.2019, 10:15 Uhr.
- Blatt 7, Ausgabe: 28.05.2019. Abgabe bis 04.06.2019, 10:15 Uhr.
Teil 2:
- Blatt 8, Ausgabe: 11.06.2019. Abgabe bis 18.06.2019, 10:15 Uhr.
- Blatt 9, Ausgabe: 18.06.2019. Aktualisiert: 19.06.2019, 10:40 Uhr. Abgabe bis 26.06.2019, individuelle Abgabe. Templatedateien: Python_v2, Java, aktualisierte Testdateien mit mehr Tests (Version 2).
- Blatt 10, Ausgabe: 25.06.2019. Abgabe bis 02.07.2019, 10:15 Uhr.
- Blatt 11, Ausgabe: 02.07.2019. Abgabe bis 09.07.2019, 10:15 Uhr.
- Blatt 12, Ausgabe: 09.07.2019. Abgabe bis 16.07.2019, 10:15 Uhr.
Tutoriumsaufgaben
- Tutorium 1, besprochen am 23.04.2019 und 24.04.2019.
- Tutorium 2, besprochen am 30.04.2019.
- Tutorium 3, besprochen am 07.05.2019 und 08.05.2019.
- Tutorium 4, besprochen am 14.05.2019 und 15.05.2019.
- (Keine globalen neuen Tutoriumsaufgaben für Tutorium 5 und 6.)
- Tutorium 7, besprochen am 04.06.2019 und 05.06.2019.
- Tutorium 8, besprochen am 11.06.2019 und 12.06.2019.
- (Keine globalen neuen Tutoriumsaufgaben für Tutorium 9.)
- Tutorium 10, besprochen am 25.06.2019 und 26.06.2019.
- (Keine globalen neuen Tutoriumsaufgaben für Tutorium 11.)
- Tutorium 12, besprochen am 09.07.2019 und 10.07.2019.
Skript
Die Vorlesung orientiert sich am Skript von Prof. Dr. Schnitger.Thema
Ein zentrales Problem der Informatik ist der Entwurf von ressourcenschonenden Algorithmen. In der Veranstaltung werden fundamentale Fragestellungen im Entwurf und in der Analyse effizienter sequentieller Algorithmen und Datenstrukturen besprochen. Eine Auswahl der folgenden Themengebiete wird behandelt:- Entwurfsmethoden für randomisierte Algorithmen wie etwa Stichproben, Fingerprinting und Random Walks.
- Entwurf und Analyse von Online-Algorithmen mit kleinem Wettbewerbsfaktor.
- Algorithmische Lösung wichtiger Probleme, z.B. Matching, Flüsse in Netzwerken, lineare Programmierung, String Matching oder algorithmische Probleme der Zahlentheorie.
- Methoden des Algorithm Engineering.
Empfohlene Literatur
- [H] Hromkovic. Design and Analysis of Randomized Algorithms, Springer, 2005.
- [MM] Moore, Mertens. The Nature of Computation, Oxford Univ. Press, 2013
- [MU] Mitzenmacher, Upfal. Randomized Algorithms and Probabilistic Analysis, Cambridge Univ. Press, 2005.
- [MR] Motwani, Raghavan. Randomized Algorithms, Cambridge Univ. Press, 1995.
- [BE] Borodin, El-Yaniv. Online Computation and Competitive Analysis, Cambridge Univ. Press, 1995.