Resource-efficient Algorithms - Single View

Durch die Notwendigkeit, sehr große Datenmengen zu speichern und zu analysieren, hat die Modellierung von Systemen mit hierarchischem Speicher (von Registern bis hin zu Tertiärspeichermedien) in der jüngeren Vergangenheit sowohl aus theoretischer als auch aus praktischer Sicht eine verstärkte Aufmerksamkeit erfahren. In dieser Vorlesung werden grundlegende und fortgeschrittene Techniken für den Entwurf ressourceneffizienter Algorithmen vorgestellt, wobei ein Schwerpunkt auf Algorithmen liegt, die in effizienter Weise Cache- und Sekundärspeicherzugriffe handhaben. Ebenfalls thematisiert werden speichereffiziente Algorithmen. Ausgehend von elementaren Problemstellungen wird sich die Vorlesung insbesondere Verfahren zur Verarbeitung niedrig-dimensionaler Datenmengen widmen. Die Übungen werden sich sowohl mit den theoretischen Grundlagen als auch Details der effizienten praktischen Realisierung beschäftigen; hier werden elementare Kenntnisse in der Programmiersprache C++ vorausgesetzt.

Die Vorlesung basiert in Teilen auf dem nachfolgend angegebenen (englischsprachigen) Buch:

• Meyer, Ulrich; Sanders, Peter; Sibeyn, Jop (Hrsg.). Algorithms for Memory Hierarchies, Lecture Notes in Computer Science 2625. Springer, Berlin, 2003.

Teile der Übungen werden auf der Basis der beiden folgenden Bücher organisiert:

• Meyers, Scott. Effektiv C++ programmieren: 55 Möglichkeiten, Ihre Programme und Entwürfe zu verbessern, Addison-Wesley, 2011.
• Meyers, Scott. Mehr Effektiv C++ programmieren: 35 neue Wege zur Verbesserung Ihrer Programme und Entwürfe, Addison-Wesley, 1997.

Für den erfolgreichen Besuch der Vorlesung ist es nicht zwingend notwendig, die o.a. (sehr guten) Bücher zu erwerben; es werden nur einzelne Kapitel hieraus behandelt.

Weitere Literaturhinweise werden zu den einzelnen Vorlesungskapiteln separat angegeben.

Die Vorlesung findet jeden Dienstag (14-16 Uhr) sowie (i.d.R.) jeden zweiten Freitag (10-12 Uhr) statt. In der Regel findet in jeder zweiten Woche eine zweistündige Übung (Freitag, 10-12 Uhr) statt.

Die Veranstaltung ist nicht(!) zu der (fast gleichnamigen) Veranstaltung "Effiziente Algorithmen" äquivalent, kann also nicht anstelle dieser angerechnet werden.

Die Modulprüfung wird in Form einer 25-minütigen mündlichen Prüfung durchgeführt. Die Termine werden im Laufe des Semester mit den Teilnehmern abgestimmt.

Für die Zulassung zur Modulprüfung ist das Erbringen einer Studienleistung im Rahmen der vorlesungsbegleitenden Übungen notwendig. Die genauen Anforderungen werden zu Beginn der Vorlesungszeit bekannt gegeben.