Ausgewählte Kapitel der Algorithmik (Wintersemester 2011/12)

Die Vorlesung Ausgewählte Kapitel der Algorithmik wird im Wintersemester 2011/12 von Prof. Dr. Jan Vahrenhold angeboten. Die Übungen sind in den Vorlesungbetrieb integriert.

Das Vorlesungsverzeichnis enthält die Belegnummer und offiziellen Kommentare zur Vorlesung.

• Vorlesung/Übung: Montag/Dienstag, 10:15-11:45 Uhr (keine Pause).
• Ort: Raum 304, OH-14.
• Beginn: Montag, 10. Oktober 2011, 10:15 Uhr.

• Diplomstudiengang “Informatik” (DPO'01), Schwerpunktgebiet 4 (Algorithmen, Komplexität und formale Modelle).
• Masterstudiengang “Informatik” (MPO'07), Forschungebiet D (Algorithmen und Komplexität), Modul INF-MSc-603.

Bitte beachten Sie, dass die nachfolgenden Informationen noch vorläufig sind und ggfs. in der ersten Vorlesungswoche aktualisiert werden können.

• (07.02.2012) Die Folien stehen ab sofort auch in einer vollständigen Fassung mit animierten Graphiken zur Verfügung.
• (07.02.2012) Die im Laufe des Semesters bekannt gewordenen Korrekturen (s.u.) sind in die Folien eingearbeitet.
• (20.11.2011) Die Folien stehen ab sofort auch in einer animierten Fassung zur Verfügung (nur Graphik-Animationen).
• (14.11.2011) Link zur WWW-Präsenz des Fourth Annual SIGMOD Programming Contest (TU Dresden).
• (14.11.2011) Link zur WWW-Präsenz der Parallel Programming Workshops and Programming Language Courses 2012 (HLRS, Universität Stuttgart).
• (18.10.2011) Die Kriterien für den Erwerb von Studienleistungen bzw. Leistungsnachweisen sind konkretisiert worden (s.u.).
• (18.10.2011) Wie in der Vorlesung besprochen, fallen die Vorlesung bzw. Übung am 25.10./31.10.2011 wegen einer Dienstreise aus. Am 24.10.2011 findet die erste Übung statt; über den 31.10.2011 wird ein umfangreicheres Übungsblatt ausgegeben.
• (25.09.2011) Die Vorlesung beginnt am Montag, 10.10.2011, die erste Übung findet am Dienstag, 18.10.2011, Montag, 24.10.2011, statt.

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 in den Vorlesungbetrieb integrierten Ü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 in der Vorlesung vorgestellten Folien werden hier im Laufe des Semesters veröffentlicht. Das für den Zugriff auf die Folien notwendige Passwort wird in der Vorlesung bekannt gegeben.

• Übersicht (1 Folie/Seite / 2 Folien/Seite / 8 Folien/Seite / schwarz-weiß, 2 Folien/Seite / schwarz-weiß, 8 Folien/Seite, Stand: 09.10.2011)
• Kapitel 1: Elementare I/O-effiziente Bausteine (1 Folie/Seite / nur animierte Folien / 2 Folien/Seite / 8 Folien/Seite / schwarz-weiß, 2 Folien/Seite / schwarz-weiß, 8 Folien/Seite, Stand: 25.02.2012)
• Kapitel 2: Elementare I/O-effiziente Baumstrukturen (1 Folie/Seite / nur animierte Folien / 2 Folien/Seite / 8 Folien/Seite / schwarz-weiß, 2 Folien/Seite / schwarz-weiß, 8 Folien/Seite, Stand: 25.02.2012)
• Kapitel 3: Elementare I/O-effiziente Graph-Algorithmen (1 Folie/Seite / nur animierte Folien / 2 Folien/Seite / 8 Folien/Seite / schwarz-weiß, 2 Folien/Seite / schwarz-weiß, 8 Folien/Seite, Stand: 25.02.2012)
• Kapitel 4: Fallstudie “TerraCost” (1 Folie/Seite / nur animierte Folien / 2 Folien/Seite / 8 Folien/Seite / schwarz-weiß, 2 Folien/Seite / schwarz-weiß, 8 Folien/Seite, Stand: 25.02.2012)
• Kapitel 5: I/O-effizientes Distribution-Sweeping (1 Folie/Seite / nur animierte Folien / 2 Folien/Seite / 8 Folien/Seite / schwarz-weiß, 2 Folien/Seite / schwarz-weiß, 8 Folien/Seite, Stand: 25.02.2012)
• Kapitel 6: Cache-Oblivious Algorithmen (1 Folie/Seite / nur animierte Folien / 2 Folien/Seite / 8 Folien/Seite / schwarz-weiß, 2 Folien/Seite / schwarz-weiß, 8 Folien/Seite, Stand: 25.02.2012)
• Kapitel 7: In-Place Algorithmen (1 Folie/Seite / nur animierte Folien / 2 Folien/Seite / 8 Folien/Seite / schwarz-weiß, 2 Folien/Seite / schwarz-weiß, 8 Folien/Seite, Stand: 25.02.2012)

An dieser Stelle werden Errata und/oder Nachträge veröffentlicht. Bitte beachten Sie, dass die oben bereit gestellten Foliensätze im Regelfall nicht entsprechend aktualisiert werden.

• (25.02.2012) Es wurden mehrere Kommentare und Korrekturen (Dank an G. Geck und M. Nimbs) eingefügt. Zudem wurden einige Tippfehler korrigiert. Alle Foliensätze sind entsprechend aktualisiert.
  • Folie 1.18: Im Kommentar zu Zeile 12 muss es “p₀” statt “s₀” heißen.
  • Folie 1.30: Ist nach dem Löschen eines Elements der Block b leer, so wird er ebenfalls gelöscht.
  • Folie 2.16: Im vierten Punkt muss es “deg(r)” statt “deg(v)” heißen (analog: Folie 2.17).
  • Folie 2.59: Vor der logarithmischen oberen Schranke muss der Faktor “1/B” ergänzt werden.
  • Folie 5.29: Die (nicht definierte) Variable N muss durch “|V|” ersetzt werden.
  • Folie 6.14: Im vorletzten Aufzählungspunkt muss es “N^{(2/3)^i}” statt “(N^(2/3))ⁱ ” heißen.
  • Folie 6.31: Im dritten Aufzählungspunkt (Unterpunkt 1) muss es “p_i^{X^(3/2)}” statt “p_i^X” heißen.
  • Folie 6.33: Die Fallunterscheidung wurde präzisiert.
  • Folie 7.9: Die Aussage in Lemma 7.6 bezieht sich auf die Realisierung eines Stapels.
  • Folie 7.16: Der Funktionsparameter i muss i' heißen.
• (16.01.2012) Folie 6.13: Der additive Term in der Rekursionsgleichung muss “N^1/3” statt “N” sowie “N'^1/3” statt “N'” sein.
• (16.01.2012) Folie 6.8: Der Nenner des Bruchs muss “log₂ B” statt “log₂ N” sein.
• (06.12.2011) Eine (ausführlichere) Beschreibung des Unterschieds zwischen delete und delete [] ist hier zu finden.
• (29.11.2011) Folie 3.4: Unter Punkt 2 muss es “K := deg^-(v) ∈ O(M)” statt “K ∈ O(M)” heissen.
• (15.11.2011) Folie 2.28: Der ausführliche Beweis zu Korollar 2.9 ist hier zu finden.
• (15.11.2011) Folie 2.36: Bei der Definition von m_j bzw. m_c muss jeweils die Kardinalität der angegebenen Menge (nicht: die Menge selbst) verwendet werden.
• (14.11.2011) Folie 2.33: Im letzten Punkt des Beweises zu Lemma 2.14 muss das Wort “maximal” ersatzlos gestrichen werden.
• (13.11.2011) Die Folien zu Kapitel 2 wurden vervollständigt.

Die Übungen finden in die Vorlesung integriert statt (s.o.).

• Blatt 1 (.pdf), Abgabe bis zum 21.10.2011, Besprechung am 24.10.2011. Dieses Blatt enthält auch eine Sicherheitsbelehrung des Dekanats.
• Blatt 2 (.pdf), Abgabe bis zum 03.11.2011, Besprechung am 08.11.2011.
• Blatt 3 (.pdf), Abgabe bis zum 17.11.2011, Besprechung am 22.11.2011.
• Blatt 4 (.pdf), Abgabe bis zum 01.12.2011, Besprechung am 06.12.2011.
• Blatt 5 (.pdf), Abgabe bis zum 08.12.2011, Besprechung am 13.12.2011.
• Blatt 6 (.pdf), Abgabe bis zum 15.12.2011, Besprechung am 20.12.2011.
• Blatt 7 (.pdf), Abgabe bis zum 19.01.2012, Besprechung am 24.01.2012.
• Blatt 8 (.pdf), Abgabe bis zum 26.01.2012, Besprechung am 31.01.2012.

• Aus gegebenem Anlass wurde eine Aufgabe zur privaten Vererbung zu Blatt 5 hinzu genommen. Bitte melden Sie sich, wenn Sie diese Aufgabe vorstellen wollen.
• Beispiellösungen zu Blatt 2 (Aufgaben 7/8) von T. Schäfer, Ph. Lewe und S. Langkamp (.tar.bz2)
• Konventionen zur Programmierung (G. Geck/M. Nimbs, ergänzt um Kommentare aus der Übung vom 24.10.2011) (.pdf)
• Rudimentäre Implementierung einer Schnittstelle für Blockzugriffe (.zip, korrigiert am 04.11.2011)
• Vorlesungsskript zum Thema “Abstrakte Datentypen” (.pdf)

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

• Ulrich Meyer, Peter Sanders, and Jop Sibeyn, editors, Algorithms for Memory Hierarchies, volume 2625 of Lecture Notes in Computer Science. Springer, Berlin, 2003.

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

• Scott Meyers, Effektiv C++ programmieren: 55 Möglichkeiten, Ihre Programme und Entwürfe zu verbessern, Addison-Wesley, 2011.
• Scott Meyers, 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.

• Studierende nach DPO'01: Eine Fachprüfung kann in Form einer mündlichen Prüfung im Umfang von 30 min. Dauer abgelegt werden.
• Studierende nach MPO'07: Der Modulabschluss kann in Form einer mündlichen Prüfung im Umfang von 30 min. Dauer erreicht werden. Notwendige Voraussetzung ist eine Studienleistung (s.u.).
• Studierende nach anderen Prüfungsordnungen: Bitte halten Sie mit mir Rücksprache.

• Studierende nach DPO'01: Für die erfolgreiche Teilnahme an der Vorlesung und an den Übungen wird ein Leistungsnachweis ausgestellt. Die Kriterien entsprechen denen der Studienleistung nach MPO'07 (s.u.).
• Studierende nach MPO'07: Für den Erwerb einer Studienleistung ist die Bearbeitung von 50% der Theorieaufgaben und die erfolgreiche Bearbeitung von 50% der Praxisaufgaben notwendig. Die Abgaben können in Gruppen von bis zu drei Personen erfolgen, wobei jede Person in der Lage sein muss, jede bearbeitete Aufgabe in der Übung vorzustellen.