Netzalgorithmen

Das Fach Netzalgorithmen dreht sich um die Frage, Flows in Netzwerken nach verschiedenen Kriterien (Kosten, Headroom, etc.) über ein Netzwerk zu bringen. Behandelt werden dabei u.A.:

• Arbeitsweise von Shortes-Path-Routing
• Mathematische Beschreibung und Lösungsmethoden von diveresen Optimierungsproblemen
• Verschiedene Optimierungsprobleme samt geeigneter Lösungsmethode, z.B.
  • Routing von Flows durch das Netzwerk auf möglichst kurzen Pfaden unter Wahrung von bestehenden Linkkapazitäten
  • Routing von Flows durch das Netzwerk unter Berücksichtigung von Redundanzanforderungen (z.B. Aufteilung auf mind. n Eckendisjunkte Pfade)
  • Dimensionierung von Links, um gewisse Ziele (Transport einer bestimmten Menge an Daten, Einhaltung von Budgets) möglichst „günstig“ zu erzielen
• Analyse von Netzwerken auf Ausfallsicherheit (v.A. Identifikation von sPofs)
• (Strategien zur Erweiterung von Netzwerken zur Verbesserung der Ausfallsicherheit)

Allgemein ist die Vorlesung sehr Mathe-lastig und behandelt hauptsächlich die Erstellung und Lösung verschiedener Optimierungsprobleme. Es wird zudem auch in der Vorlesung gezeigt, dass die Umsetzung der Ergebnisse aus der Optimierung nur schwer auf das in großen Teilen des Internet eingesetzte Shortest-Path-Routing umgesetzt werden kann, was den Eindruck gibt, dass die praktische Relevanz dieses Faches in der Praxis nur bedingt vorhanden ist.

Die Prüfung ist mündlich. Der Termin muss nach Anmeldung der Prüfung per E-Mail an das Sekretariat vom FG Telematik angefragt werden. Details dazu werden rechtzeitig im Laufe des Semesters bekannt gegeben.

Die Prüfung ist eine klassische Schäfer-Prüfung, d.h. man sollte wirklich nichts auf Lücke lernen, da Prof. Schäfer ein Talent dafür hat, genau die Punkte abzufragen, die man nicht so gut kann. In der Prüfung werden verschiedene Kapitel aus der Vorlesung abgefragt. Dabei wird bei einzelnen Themen etwas tiefer eingegangen, sodass auch Details wie mathematische Definition (z.B. „Basislösung“, „lineare Unabhängigkeit“) oder die Komplexitätsklassen mancher Verfahren (welche davon sind NP-vollständig?) bekannt sein sollten.

• WS2023/24

• Mathe by Daniel Jung
  • Simplextableau aufstellen, Simplex-Algorithmus
  • Ablauf Simplex-Verfahren
  • Simplex Endtableau, Optimaltableau