TU BRAUNSCHWEIG
| Carl-Friedrich-Gauß-Fakultät | Informatik
Informatikzentrum

Verteilte Algorithmen

Semester Sommersemester 2012 [ Andere Semester: Sommer 14 · Sommer 10 · Sommer 08 ]
Modulnr. INF-ALG-16
Veranst.Nr. INF-ALG-011, INF-ALG-012
Studieng. Master Informatik, Master Informations-Systemtechnik, Master Wirtschaftsinformatik
IBR Gruppe(n) ALG (Prof. Fekete)
Art Vorlesung/Übung
Dozent
Photo Dr. Alexander Kröller
Ehemaliger Juniorprofessor
Assistent
Photo Dr. Alexander Kröller
Ehemaliger Juniorprofessor
LP 5
SWS 2+1
Ort & Zeit zweijährlich ab SoSe 2008

Vorlesung: Mittwoch, 09:45 - 11:15, Raum IZ 358
Übung: Dienstag, 09:45 - 11:15, Raum IZ 358
Kleine Übung: wird noch festgelegt.


Beginn

Die erste Vorlesung findet am 11.04.2012 statt.
Die erste Übung findet am 24.04.2012 17.04.2012 statt.

Voraussetzungen

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

Scheinerwerb

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

Inhalt

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.
Literatur/Links
  • 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.

Termine nach der Exkursionswoche

Di 8:00 IZ305 Di 9:45 IZ358 Mi 9:45 IZ358
5.6. kl.Ü. 5.6. VL
12.6. VL
19.6. kl.Ü.
26.6. gr.Ü. 27.6. VL
3.7. kl.Ü.
10.7. VL 11.7. VL
17.7. kl.Ü. 17.7. gr.Ü. 18.7. VL

Hausaufgaben und praktische Übungen

Dieses Jahr werden wir erstmalig sowohl theoretische als auch praktische Aufgaben auf den Übungsblättern anbieten, die wahlweise bearbeitet werden können. Das heisst, die Teilnehmer können sich selber entscheiden, auf welcher "Seite" sie sich eher versuchen wollen.

In den praktischen Übungen werden wir grundlegende Algorithmen in der Wiselib implementieren, einer Algorithmenbibliothek für Netze eingebetteter Systeme.

  • Hausaufgabenblatt Nr. 1: PDF, Code.
  • Hausaufgabenblatt Nr. 2: PDF.
  • Hausaufgabenblatt Nr. 3: PDF.
  • Hausaufgabenblatt Nr. 4: PDF.
  • Hausaufgabenblatt Nr. 5: PDF.

aktualisiert am 01.07.2012, 16:20 von Dr. Christiane Schmidt
printemailtop