Fakultät für Informatik - Technische Universität München Lehrstuhl für Effiziente Algorithmen

Netzwerk-Algorithmen (WS 05/06)

• Dozent:
  Prof. Dr. Christian Scheideler

• Ankündigungen:
  
  
• Bereich:
  4 SWS Vorlesung im Bereich Informatik III (Theoretische Informatik)
  Vertiefende Vorlesung im Gebiet Algorithmen

• Zeit und Ort:
  Montag 08:30-10:00 Uhr, MW 1801
  Freitag 08:30-10:00 Uhr, MI HS 1
  
  Die erste Vorlesung findet am Montag, 17. Oktober, statt.

• Schein:
  Einen Übungsschein erhält, wer erfolgreich an den Prüfungen unten teilnimmt.

• Prüfungen:
  Mittelklausur: Freitag, 2.12.2005, 8:30-10:00
  Softwareprojekt: Präsentation in der Woche vom 13.-17.02.06

• Hörerkreis:
  Studierende im Hauptstudium der Informatik
  Studierende mit Nebenfach Informatik

• Voraussetzungen:
  Stoff des Informatik Grundstudiums

• Empfehlenswert für:
  Erweiterte Kenntnisse im Bereich Algorithmen

• Inhalt:
  Die Vorlesung wird sich mit den folgenden Themen beschäftigen:
  • Modelle für verteilte Algorithmen und Datenstrukturen
  • Netzwerktheorie
  • Routing und Scheduling
  • Hashing und Caching
  • Das kontinuierlich-diskrete Prinzip
  • Zentral gesteuerte logische Netzwerke
  • Dezentrale logische Netzwerke
  • Anycasting und multicasting
  • Suchen und sortieren
  • Selbst-stabilisierende logische Netzwerke
  • Selbst-erhaltende logische Netzwerke
  • Logische Netzwerke für drahtlose Netze
  • Logische Netzwerke für Configware

• Weiterführende bzw. verwandte Vorlesungen:
  Eine weiterführende Vorlesung ist geplant.

• Skript:
  
  • Kapitel 1: Introduction (in postscript und pdf)
  • Kapitel 2: Network Theory (in postscript und pdf)
  • Kapitel 3: Routing (in postscript und pdf)
  • Kapitel 4: Scheduling (in postscript und pdf)
  • Kapitel 5: Distributed data management I - Hashing (in postscript und pdf)
  • Kapitel 6: Distributed data management II - Caching (in postscript und pdf)
  • Kapitel 7: Supervised Overlay Networks I (in postscript und pdf)
  • Kapitel 8: Supervised Overlay Networks II (in postscript und pdf)
  • Kapitel 9: Decentralized Overlay Networks (in postscript und pdf)
  • Kapitel 10: Locality-aware Overlay Networks (in postscript und pdf)
  • Kapitel 11: Group Management (in postscript und pdf)
  • Kapitel 12: Overlay Networks for Heterogeneous Peers (in postscript und pdf)
  • Kapitel 13: Wireless Overlay Networks I (in postscript und pdf)
  • Kapitel 14: Wireless Overlay Networks II (in postscript und pdf)

• Programme:
  Programme werden in C++ geschrieben, aufbauend auf der Subjects Umgebung die unten heruntergeladen werden kann.
  • Subjects Umgebung (Version 1.1)
  • Ein Hello World Beispiel.
  • Ein Ping-Pong Beispiel.

• Übungsblätter:
  
  • Übungsblatt 1 (in postscript and pdf, Abgabe 28. Okt.)
  • Übungsblatt 2 (in postscript and pdf, Abgabe 4. Nov.)
  • Übungsblatt 3 (in postscript and pdf, Abgabe 18. Nov.)
  • Übungsblatt 4 (in postscript and pdf, Abgabe 25. Nov.)
  • Übungsblatt 5 (in postscript and pdf, Abgabe 2. Dez.)
  • Übungsblatt 6 (in postscript and pdf, Abgabe 23. Dez.)
  • Übungsblatt 7 (in postscript and pdf, Abgabe 20. Jan.)
  • Übungsblatt 8 (in postscript and pdf, Abgabe 27. Jan.)
  • Übungsblatt 9 (in postscript and pdf, Abgabe 3. Feb.)
  • Übungsblatt 10 (in postscript and pdf, Abgabe 10. Feb.)

• Lösungen:
  
  • Lösungen zu den Problemen in Übungsblättern 1 bis 5:
  • Frühere Mittelklausuren zur Vorbereitung auf diese Mittelklausur:
    2002 (in ps and pdf) 2003 (in ps and pdf) 2004 (in ps and pdf)

• Literatur:
  Die Vorlesung basiert auf neuesten Konferenzpublikationen. Literaturangaben befinden sich im Vorlesungsskript.

• Sprechstunde:
  siehe hier