Inhalt des Dokuments
zur Navigation
Network Algorithms (Vorlesung, WS 2017/18)
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 18.10.2017, 14:00 - 16:00 Uhr, Raum MAR 4.064
- Bitte gebt die Lösungen zum ersten Übungsblatt bis Mittwoch 14 Uhr entweder bei ISIS oder direkt vor der Vorlesung bei Georgios ab.
Für offene Fragen bzgl. ISIS, den Hausaufgaben oder dem Übungsbetrieb steht Damien Foucard als Ansprechpartner bereit.
Überblick
| Dozent/innen: | Georgios Smaragdakis |
| Ansprechpartner: | Damien Foucard (contact, tutorial management) |
| 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: | 4 |
| Leistungspunkte (LP): | 6 |
| Zeit: | Mittwochs, 14–16 Uhr wöchentlich |
| Erster Termin: | Vorlesung: 18.10.2017 |
| Raum: | MAR 4.064 |
| Übung: | Donnerstags, 14–16 Uhr wöchentlich |
| Veranstaltungsnr.: | 0432 L 815 |
| Hörerkreis: | Master-Studierende und Diplom-Studierende |
| Voraussetzungen: |
|
| 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
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.
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