direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Network Algorithms (Vorlesung, WS 2013/14)

Diese Vorlesung vermittelt Techniken zum Entwurf und zur Analyse von effizienten Netzwerkalgorithmen. Solche Algorithmen bilden eine wichtige Grundlage vieler verteilter Systeme: von Multicore Computern über Internet Netzwerke bis hin zu Online Social Networks. Jede Lektion dieser Vorlesung wird sich mit einem in sich abgeschlossenen Problem (z.B. Load Balancing, Medium Access, Symmetry Breaking) und Thema (z.B. Randomisierung, Dezentralisierung,Dereferenzierung) befassen.

Aktuelles

  • Erste Vorlesung: Mittwoch 16.10.2013, 13:00 - 15:00 Uhr, Raum MAR 0.007
  • Bitte gebt die Lösungen zum ersten Übungsblatt bis Mittwoch 13 Uhr entweder bei ISIS oder direkt vor der Vorlesung bei Stefan ab.

    Für offene Fragen bzgl. ISIS, den Hausaufgaben oder dem Übungsbetrieb
    steht Arne Ludwig als Ansprechpartner bereit.

Überblick

Informationen
Dozent/innen:
Stefan Schmid
Ansprechpartner:
Arne Ludwig (contact, tutorial management)
Srivatsan Ravi
Veranstaltungstyp:
Vorlesung mit Übung (VL+UE)
Gebiet:
Master Computer Science (focus: Communication Systems (KS), Master Computer Engineering (focus: Technical Applications) Master Computer Engineering (StO/PO 2012): Studienschwerpunkt Netze (Networks; Elektrotechnik, Technische Informatik oder Informatik).
Module:
Die Vorlesung mit Übung ist das Modul MINF-KT-NA.W12.
SWS:

Leistungspunkte (LP):
6
Zeit:
Mittwochs, 13–15 Uhr wöchentlich
Erster Termin:
Vorlesung: 16.10.2013
Raum:
MAR 0.007
Übung:
Mittwochs, 15–17 Uhr wöchentlich
Veranstaltungsnr.:
0432 L 815
Hörerkreis:
Master-Studierende und Diplom-Studierende
Voraussetzungen:
 

  • BINF-GL - MPGI1 Algorithmische und funktionale Lösung diskreter Probleme

  • BINF-GL - MPGI2 Algorithmen und Datenstrukturen im imperativen Stil

    englische Sprache

 
Prüfung:
Schriftlich. Es werden 50% der Punkte in den Hausaufgaben benötigt um zur Klausur zugelassen zu sein.
Weitere Informationen:
s. ISIS

Themen

Übersicht möglicher Themen:

  • Models for networks and distributed systems
  • Robust and efficient network design: self-stabilization and self-optimization
  • Decentralization: Why and how? And complexity measures
  • Randomization: Why and how? Basic tools
  • Algorithms: Local algorithms, random algorithms, online algorithms, dynamic programming
  • Network Algorithms for leader election, coloring, maximal independent sets, Medium Access
  • Resource Allocation and embedding (e.g., energy, bandwidth, CPU)
  • Flow & congestion control, routing
  • Social networks: An algorithmic perspective

Organisation

ISIS

Falls du an unserer Vorlesung teilnehmen willst, trag dich bitte auf der zugehörigen ISIS-Webseite ein, um wichtige Informationen und Ankündigungen zu bekommen.

Sprache

Die Vorlesungen und die Übungen werden auf Englisch gehalten.

Übungen

Zum Bestehen der Übungen sind mind. 50% der maximal erreichbaren Punkte notwendig.

Prüfung

Details zur Prüfung werden noch bekannt gegeben und in Vorlesung und Übung angekündigt.

Vorlesungsskript

Übungsblätter

Allgemeine Literaturhinweise

  • David Peleg: Distributed Computing – A Locality-Sensitive Approach, SIAM 2000.

  • Michael Mitzenmacher and Eli Upfal, Probability and Computing, Cambridge University Press, 2005
  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms, MIT press, 2009
  • Hagit Attiya and Jennifer Welch, Distributed Computing Fundamentals, Simulations, and Advanced Topics, John Wiley and Sons, Inc. 2005
  • Maurice Herlihy and Nir Shavit, The Art of Multiprocessor Programming, Morgan Kaufmann, 2012

Zusatzinformationen / Extras

Direktzugang

Schnellnavigation zur Seite über Nummerneingabe

Network Algorithms
Integrierte LV (VL mit UE)

Dozent: Stefan Schmid

Zeitraum:
14.10.2013 bis 15.02.2014

Mi 13:00 - 17:00 Uhr

Ort: MAR 0.007

ISIS