Inhalt des Dokuments
zur Navigation
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
| 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: | 4 |
| 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: |
|
| 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.
Vorlesungsfolien
- 01. netalg13-intro PDF, 3 MB
- 02. netalg13 topology PDF, 2 MB
- 03. netalg13 leader election PDF, 505 KB
- 04. netalg13 consensus PDF, 656 KB
- 05. netalg13 tree algorithms PDF, 981 KB
- 06. netalg13 coloring PDF, 571 KB
- 07. netalg13 MIS PDF, 620 KB
- 08. netalg13 Sorting PDF, 600 KB
- 09. netalg13 Counting PDF, 595 KB
- 10. netalg13 Self stabilization PDF, 844 KB
- 11. netalg13 Synchronization PDF, 434 KB
Vorlesungsskript
- Lecture Notes - Network Algorithms PDF, 635 KB
Übungsblätter
- 01. NA-Ex1 PDF, 177 KB
- 02. NA-Ex2 PDF, 207 KB
- 03. NA-Ex3 PDF, 136 KB
- 04. NA-Ex4 PDF, 169 KB
- 05. NA-Ex5 PDF, 149 KB
- 06. NA-EX6 PDF, 133 KB
- 07. NA-EX7 PDF, 177 KB
- 08. NA-Ex8 PDF, 148 KB
- 09. NA-Ex9 PDF, 144 KB
- 10. NA-Ex10 PDF, 162 KB
- 11. NA-Ex11 PDF, 205 KB
- 12. NA-Ex12 PDF, 123 KB
- 13. NA-Ex13 PDF, 97 KB
- 14. NA-Ex14 PDF, 102 KB
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