TU BRAUNSCHWEIG
Informatikzentrum

Verteilte Algorithmen

SemesterSummer 2010 · Sommer 08
Module #INF-ALG-06
Event #INF-ALG-011, INF-ALG-012
ProgrammesMaster Informatik, Master Informations-Systemtechnik, Master Wirtschaftsinformatik
IBR Group(s)ALG (Prof. Fekete)
TypeVorlesung/Übung
LecturerDr. Alexander Kröller
AssistantDr. Christiane Schmidt
Credits4
Hours2+1
Time & Place zweijährlich ab SoSe 2008

Lecture: Wednesday, 09:45 - 11:45, Room SN 23.1
Exercises: Monday, 16:45 - 18:15, Room 161 .
(Exercises: 19.04., 03.05., 17.05., 07.06., 21.06., 05.07. (12.07.))


Start

The first lecture will take place: April 07, 2010.
The first tutorial will take place: April 19, 2010.

Prerequisites

Grundkenntnisse aus Algorithmen und Datenstrukturen.
Bei einigen Themen sind Kenntnisse auf Netzwerkalgorithmen und Computational Geometry vorteilhaft, werden aber nicht vorausgesetzt (und jeweils in der VL eingeführt).

Certificates

Erfolgreiche Bearbeitung der Hausaufgaben und erfolgreiche Teilnahme an der mündlichen Prüfung.

Content

In dieser Vorlesung werden theoretische und algorithmische Grundlagen verteilter Systeme diskutiert. Dafür betrachten wir Problemstellungen, bei denen beispielsweise die Knoten eines Netzwerks gemeinsam ein algorithmisches Problem lösen sollen, indem sie miteinander kommunizieren und lokale Berechnungen ausführen. Die Fragen sind der Art "Wie schnell kann dieses Problem gelöst werden?", "Wieviel Kommunikation ist dafür notwendig?", "Welche Charakteristika muss ein Netz haben, um dieses Problem überhaupt lösen zu können?".

Das vorläufige Programm ist das folgende; das kann bei Interesse (oder Desinteresse) an bestimmten Themen auch angepasst werden.

  1. Modelle, Schranken, Komplexitäten, Berechenbarkeit.
  2. Grundlegende Netzwerkalgorithmen und -strukturen, Kommunikationsparadigmen.
  3. Lokale und selbstabilisierende Algorithmen.
  4. Asynchrone vs. synchrone Netzwerke.
  5. Geometrische und drahtlose Netzwerke.
References
  • Nancy Lynch: Distributed Algorithms. Morgan Kaufmann Publishers.
  • David Peleg: Distributed Computing - A Locality-Sensitive Approach. SIAM.
  • Dorothea Wagner und Roger Wattenhofer: Algorithms for Sensor and Ad Hoc Networks, Advanced Lectures. Springer Verlag.

Hausaufgaben

  • Hausaufgabenblatt Nr. 1: [PDF]
  • Hausaufgabenblatt Nr. 2: [PDF]
  • Hausaufgabenblatt Nr. 3: [PDF]
  • Hausaufgabenblatt Nr. 4: [PDF]
  • Hausaufgabenblatt Nr. 5: [PDF]
    Eine kleine [Hilfe für Aufgabe 1] (verwende ein Blatt pro Iteration).
  • Hausaufgabenblatt Nr. 6: [PDF]
last changed 2010-07-05, 11:41 Dr. Alexander Kröller Printable version
hoch zum Seitenanfang