Bölüm anahatları
-
Dieser Kurs vermittelt einen Überlick über verschiedene Themenbereich der Algorithmik anhand einer Auswahl von Materialien zu exakten, geometrischen, randomisierten und Approximationsalgorithmen sowie zu forgeschrittenen Datenstrukturen. Als solcher, dient dieser Kurs als eine Basis für die dazugehörigen Mastervorlesungen. Der Kurs behandelt Verbesserungen von klassichen Algorithmen sowie Ansätze um NP-schwere Probleme anzugehen. Diese Ansätze reichen vom Verständnis "guter" Algorithmen, die solche Probleme exakt lösen, über effiziente Algorithmen, die solche Probleme approximieren, bis hin zu randomisiereten Ansätzen, welche im Erwartungswert gut funktionieren. Im Zuge dessen werden einige interessante Datenstrukturen kennen lernen, welche hierfür ausgenutzt werden können.
Am Ende dieses Kurses sollten Teilnehmer einen grober Überblück über forgeschritteten Themen der Algorithmik und Datenstrukturen haben. Sie sollten in der Lage sein Algorithmen von jedem Typ zu analysieren und zu entwerfen sowie den angemessenen Gebrauch der Datenstrukturen verstehen.
Vorlesungen: Vorlesungen werden als Videos zur Verfügung gestellt
Frage- und Diskussionrunde zur aktuellen Vorlesung jeden Montag, ~ 10:30–11:15 Uhr
Übungen: Montag, 13:00–14:00 Uhr
Dozenten: Jonathan Klawitter (Vorlesungen), Boris Klemz (Vorlesungen), Oksana Firman (Übungen)
Mdl. Prüfung: Haupttermin für mündliche Prüfungen vereinbaren wir gegen Ende der Vorlesungszeit. Ergebnis: 2. und 3. März
Bitte nicht vergessen in WueStudy anzumelden. Die Frist hierfür ist der 31. Januar.
Ein Bonus von 0,3 auf die finale Note wird an Studierende vergeben, die mindestens 50% der Punkte auf Übungsblättern erreichen.Umgfang: 5 ECTS, 2+2 SWS Voraussetzung: Algorithmische Graphentheorie (empfohlen) Zielgruppe:
Master Informatik, Master Mathematik, Master Computational Mathematics
Anmeldung:
Wenn Sie an der Vorlesung teilnehmen möchten, melden Sie sich bitte hier in WueCampus an (oben links auf das blaue Zahnrad klicken und "Mich in diesen Kurs einschreiben" auswählen). Im Verlauf des Semesters wir die Anmeldung in WueStudy für die Prüfung freigeschaltet.
Chat:
Zur Kommunikation während der Präsenzvorlesung-freien Zeit benutzen wir einen Channel im Uni Chat. Diesem könnt ihr über diesen Link beitreten (es kommt vermutlich eine Fehlermeldung, danach die Seite aktualisieren und kurz auf einen anderen Channel wechseln). Falls das nicht klappt, bitte einfach Jonathan kurz eine Nachricht schreiben.
-
Aufgrund des derzeitigen Verbots von Präsenzveranstaltungen werden wir anstatt Vorlesungen zu halten jede Woche pünktlich zum Vorlesungstermin Videos hochladen. (Änderungen der Themen und Reihenfolge möglich.)
-
Jede Woch werden wir zum Vorlesungstermin ein neues Übungsblatt hochladen. Abgabetermin ist der darauffolgende Vorlesungstermin. Das Erlangen von mindestens 50% der Punkte gewährt einen Bonus von einem Notenschritt bei Bestehen der mündlichen Prüfung.
Übungsblätter dürfen zu zweit bearbeitet werden und werden dann in digital Form abgegeben. Sie sollten daher wenn möglich am Computer geschrieben werden. Wir empfehlen die Verwendung von LaTeX und gerne die hierfür bereitgestellte Vorlage. Die Übungsblätter sollten in Englisch verfasst werden.
-
- Introduction to Algorithms (3rd Edition).
Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford. MIT Press and McGraw-Hill, 2009 [1990]. - Parameterized Algorithms.
Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk and Saket Saurabh. Springer, 2015.
https://www.mimuw.edu.pl/~malcin/book/parameterized-algorithms.pdf - Exact Exponential Algorithms.
Fedor V. Fomin and Dieter Kratsch. Springer, 2010.
http://www.ii.uib.no/~fomin/BookEA/BookEA.pdf - Computational Geometry: Algorithms and Applications (3rd edition).
Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars. Springer, 2008.
Web site with pseudocode for all algorithms - Algorithmische Geometrie (2. Auflage). Rolf Klein. Springer, 2005.
- The Design of Approximation Algorithms
David P. Williamson, David B. Shmoys. Cambridge University Press, 2011.
Kostenlose Online-Version
- Approximation Algorithms
Vijay V. Vazirani. Springer, 2003.
-
[Storandt '17] Randomized Algorithms Dosya
- Introduction to Algorithms (3rd Edition).
Impressum | Datenschutzerklärung - WueCampus | Erklärung zur Barrierefreiheit | Bildnachweise
Navigationsleiste - Rechenzentrum: Data center icons created by Eucalyp - Flaticon
Navigationsleiste - Website Support: Consultant icons created by Vitaly Gorbachev - Flaticon
Navigationsleiste - Häufige Fragen: Files and folders icons created by Freepik - Flaticon
Navigationsleiste - Lehre Digital: Training icons created by vectorspoint - Flaticon
Navigationsleiste - Forschung Digital: Research icons created by Eucalyp - Flaticon
Navigationsleiste - Lecture: Video icons created by Freepik - Flaticon
Werbefeld 2 - WueLogin: Login icons created by Freepik - Flaticon
Werbefeld 3 - Upgrade WueCampus 4.4: Update icons created by Freepik - Flaticon