Sprungmarken

Servicenavigation

       

Hauptnavigation

Bereichsnavigation

Ausgewählte Kapitel der Algorithmik

Basisoperationen für Netzwerke

Sommersemester 2017

Veranstalter:Dr. Matthias Westermann
Termine: Donnerstag16:00-17:30 UhrOH 14 304
Beginn: Donnerstag 20.04.

Inhalt

Bei der Nutzbarkeit von Computernetzwerken spielt die Verfügbarkeit von effizienten Basisoperationen eine gravierende Rolle. Beispiele für solche Basisoperationen sind das Routing von Nachrichten und die Verwaltung von globalen Daten. Die Veranstaltung betrachtet Algorithmen für Basisoperationen und behandelt grundlegende Techniken und Konzepte dieses Gebietes der Algorithmik.

Themen

  • Permutationsrouting auf Gittern
  • Sortiernetzwerke
  • Oblivious Routing
  • Multibutterfly-Netzwerke
  • Simulationen von PRAMs

Stand der Vorlesung

  • 20.04.: Übersicht
  • 27.04.: Modelle, Permutationsrouting auf Gittern: Einführung
  • 04.05.: Permutationsrouting auf Gittern: Färbungen und Matchings
  • 11.05.: Permutationsrouting auf Gittern: Permutationsnetzwerke und deren Simulation
  • 18.05.: Sortiernetzwerke
  • 25.05.: Christi Himmelfahrt
  • 01.06.: Oblivious Routing: Congestion im Worst-Case
  • 08.06.: Oblivious Routing: Congestion im Average-Case, Random-Rank-Protokoll
  • 15.06.: Fronleichnam
  • 22.06.: Oblivious Routing: Random-Rank-Protokoll
  • 29.06.: Oblivious Routing: Valiants Trick, Multibutterfly-Netzwerke: Konzentratoren
  • 06.07.: Multibutterfly-Netzwerke: Routing und Analyse
  • 13.07.: Multibutterfly-Netzwerke: Analyse, Simulationen von PRAMs: Einführung
  • 20.07.: Simulationen von PRAMs: Eine Hashfunktion, mehrere Hashfunktionen
  • 27.07.: Simulationen von PRAMs: Mehrere Hashfunktionen

Übungen

Veranstalter:Dr. Matthias Westermann
Termine:Donnerstag17:30-19:00 UhrOH 14 304
Beginn: Donnerstag 27.04.

In den Übungen werden Aufgaben gemeinsam gelöst und besprochen. Es soll in Gruppen zusammengearbeitet werden.

Die Studienleistung wird durch regelmäßige und aktive Teilnahme an den Übungen erbracht.


Prüfung

Die Veranstaltung wird mündlich geprüft. Prüfungen finden typischerweise in der vorlesungsfreien Zeit alle zwei Wochen jeweils Mittwochs statt.

Die Studienleistung ist Voraussetzung für die Teilnahme an der Prüfung.


Literatur

Auf ergänzende Literatur wird in den Manuskripten verwiesen.