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
Letzte Änderung:
Hanjo Täubig
am 04.10.2005