Netzwerkalgorithmen (6 LP)Modulbeschreibung #40589 / Version 1
- 6 LP
- Schriftliche Prüfung
- Benotet
- Wintersemester
- Englisch
Diese Modulbeschreibung gilt nicht im aktuellen Semester (WiSe 2026/27).
| Modul / Version | #40589 / #1 |
|---|---|
| Gültigkeit | WS 2013/14 – SS 2019 |
| Verfügbare Sprache(n) | Englisch |
| Leistungspunkte | 6 |
| Modulverantwortliche*r | Feldmann, Anja |
| Benotung | Benotet |
| Prüfungsform | Schriftliche Prüfung |
| Lehrsprache(n) | Englisch |
Zugehörigkeit
| Fakultät | Fakultät IV |
|---|---|
| Institut | Institut für Telekommunikationssysteme |
| Fachgebiet | 34331700 FG Intelligent Networks and Management of Distributed Systems (INET) |
Kontakt
| Sekretariat | Keine Angabe |
|---|---|
| Ansprechpartner*in | Keine Angabe |
| E-Mail-Adresse | Keine Angabe |
| Webseite | Keine Angabe |
Lernergebnisse
Most modern computer systems are inherently distributed and networked: from multi-core computer architectures over wireless sensor systems and datacenters to peer-to-peer systems. Accordingly, network algorithms are needed to design and operate
these computer systems in a scalable and robust way.
The goal of this lecture is to provide the students with tools and techniques to reason about efficient network algorithms. The lecture is problem-oriented and structured into different fundamental princi-ples, such as Randomization,
Decentralization, Indirection, etc. Each lecture will cover a different basic problem (such as Load Balancing, Medium Access, Symmetry Breaking, etc.) and will be self-contained.
By the end of the lecture, the student will be able to develop her/his own network algorithms, and formally prove correctness as well as complexity guarantees (e.g., on the computational or message complexity).
The students will also have a good understanding of when to apply which principle, i.e., where randomization can be useful and where not, or to which extent a distributed system should be decentralized.
The students will also have a good idea of the different natures of today's networks. If time permits, we will also extend our discussion beyond computer networks and have an algorithmic look at social networks.
This module is principally designed to impart:
technical skills: 40x, method skills: 40x, system skills 10x, social skills 10x
these computer systems in a scalable and robust way.
The goal of this lecture is to provide the students with tools and techniques to reason about efficient network algorithms. The lecture is problem-oriented and structured into different fundamental princi-ples, such as Randomization,
Decentralization, Indirection, etc. Each lecture will cover a different basic problem (such as Load Balancing, Medium Access, Symmetry Breaking, etc.) and will be self-contained.
By the end of the lecture, the student will be able to develop her/his own network algorithms, and formally prove correctness as well as complexity guarantees (e.g., on the computational or message complexity).
The students will also have a good understanding of when to apply which principle, i.e., where randomization can be useful and where not, or to which extent a distributed system should be decentralized.
The students will also have a good idea of the different natures of today's networks. If time permits, we will also extend our discussion beyond computer networks and have an algorithmic look at social networks.
This module is principally designed to impart:
technical skills: 40x, method skills: 40x, system skills 10x, social skills 10x
Lehrinhalte
The lectures revolve around fundamental problems and design principles. A tentative outline of the main topics to be covered in the course are
* Network Models and Distributed Systems
* Robust Network Topology Design: Self-Stabilizing and Self-Optimizing Networks
* Decentralization: why and how? 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
* Network Models and Distributed Systems
* Robust Network Topology Design: Self-Stabilizing and Self-Optimizing Networks
* Decentralization: why and how? 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
Modulbestandteile
Pflichtbereich
Die folgenden Veranstaltungen sind für das Modul obligatorisch:
| Lehrveranstaltungen | Art | Nummer | Turnus | Sprache | SWS | VVZ |
|---|---|---|---|---|---|---|
| Network Algorithms | Integrierte Veranstaltung | 0432 L 815 | Wintersemester | – | 4 | ISIS |
Arbeitsaufwand und Leistungspunkte
Network Algorithms (Integrierte Veranstaltung)
| Aufwandbeschreibung | Multiplikator | Stunden | Gesamt |
|---|---|---|---|
| attendance lecture | 15 | 2 h | 30 h |
| attendance tutorial | 15 | 2 h | 30 h |
| preparation and rework of the lecture | 15 | 3 h | 45 h |
| preparation for the exam | 1 | 15 h | 15 h |
| solving exercises | 15 | 4 h | 60 h |
| 180 h | |||
Der Aufwand des Moduls summiert sich zu 180 Stunden. Damit umfasst das Modul 6 Leistungspunkte.
Beschreibung der Lehr- und Lernformen
* Common lecture
* Exercises and/or programming assignments: to be issued weekly; half to be solved individually and half to be solved in groups of 2 (if the class has an odd number of participants then there will be a group of 3); to be graded by the instructor;
solutions to be jointly discussed (by instructor + students) during the tutorials
* English language for both the lecture and the tutorials
* Exercises and/or programming assignments: to be issued weekly; half to be solved individually and half to be solved in groups of 2 (if the class has an odd number of participants then there will be a group of 3); to be graded by the instructor;
solutions to be jointly discussed (by instructor + students) during the tutorials
* English language for both the lecture and the tutorials
Voraussetzungen für die Teilnahme / Prüfung
Wünschenswerte Voraussetzungen für die Teilnahme an den Lehrveranstaltungen:
Desirable - knowledge and qualifications equivalent to:
* BINF-GL - MPGI1 Algorithmische und funktionale Lösung diskreter Probleme
* BINF-GL - MPGI2 Algorithmen und Datenstrukturen im imperativen Stil
* Network Protocols and Architectures
* English language
* BINF-GL - MPGI1 Algorithmische und funktionale Lösung diskreter Probleme
* BINF-GL - MPGI2 Algorithmen und Datenstrukturen im imperativen Stil
* Network Protocols and Architectures
* English language
Verpflichtende Voraussetzungen für die Modulprüfungsanmeldung:
Dieses Modul hat keine Prüfungsvoraussetzungen.
Abschluss des Moduls
| Benotung | Benotet |
|---|---|
| Prüfungsform | Schriftliche Prüfung |
| Sprache | Englisch |
Prüfungsbeschreibung (Abschluss des Moduls)
There is a written exam. In order to register for the exam the students must obtain at least 50% of the points for exercises and/or programming assignments.
Dauer des Moduls
Für Belegung und Abschluss des Moduls ist folgende Semesteranzahl veranschlagt: 1 Semester.
Dieses Modul kann in folgenden Semestern begonnen werden: Wintersemester.
Maximale teilnehmende Personen
Die maximale Teilnehmerzahl beträgt 30.
Anmeldeformalitäten
Registration for the course on ISIS. Registration for the complete module on QISPOS / registration office.
Literaturhinweise, Skripte
Skript in Papierform
nicht verfügbar
Skript in elektronischer Form
verfügbar – http://www.inet.tu-berlin.de/
Empfohlene Literatur
- David Peleg: Distributed Computing - A Locality-Sensitive Approach, SIAM 2000
- Michael Mitzenmacher and Eli Upfal, Probability and Computing, Cambridge University Press, 2005.
Zugeordnete Studiengänge
Dieses Modul findet in keinem Studiengang Verwendung.
Sonstiges
Keine Angabe