Universität Wien
Achtung! Das Lehrangebot ist noch nicht vollständig und wird bis Semesterbeginn laufend ergänzt.

040968 UK Graph Algorithms and Network Flows (MA) (2022S)

4.00 ECTS (2.00 SWS), SPL 4 - Wirtschaftswissenschaften
Prüfungsimmanente Lehrveranstaltung
Moodle

An/Abmeldung

Hinweis: Ihr Anmeldezeitpunkt innerhalb der Frist hat keine Auswirkungen auf die Platzvergabe (kein "first come, first served").

Details

max. 50 Teilnehmer*innen
Sprache: Englisch

Lehrende

Termine (iCal) - nächster Termin ist mit N markiert

  • Mittwoch 02.03. 13:15 - 14:45 Hörsaal 8 Oskar-Morgenstern-Platz 1 1.Stock
  • Mittwoch 09.03. 13:15 - 14:45 Hörsaal 8 Oskar-Morgenstern-Platz 1 1.Stock
  • Mittwoch 16.03. 13:15 - 14:45 Hörsaal 8 Oskar-Morgenstern-Platz 1 1.Stock
  • Mittwoch 23.03. 13:15 - 14:45 Hörsaal 8 Oskar-Morgenstern-Platz 1 1.Stock
  • Mittwoch 30.03. 13:15 - 14:45 Hörsaal 8 Oskar-Morgenstern-Platz 1 1.Stock
  • Mittwoch 06.04. 13:15 - 14:45 Hörsaal 8 Oskar-Morgenstern-Platz 1 1.Stock
  • Mittwoch 27.04. 13:15 - 14:45 Hörsaal 8 Oskar-Morgenstern-Platz 1 1.Stock
  • Mittwoch 04.05. 13:15 - 14:45 Hörsaal 8 Oskar-Morgenstern-Platz 1 1.Stock
  • Mittwoch 11.05. 13:15 - 14:45 Hörsaal 8 Oskar-Morgenstern-Platz 1 1.Stock
  • Mittwoch 18.05. 13:15 - 14:45 Hörsaal 8 Oskar-Morgenstern-Platz 1 1.Stock
  • Mittwoch 25.05. 13:15 - 14:45 Hörsaal 8 Oskar-Morgenstern-Platz 1 1.Stock
  • Mittwoch 01.06. 13:15 - 14:45 Hörsaal 8 Oskar-Morgenstern-Platz 1 1.Stock
  • Mittwoch 08.06. 13:15 - 14:45 Hörsaal 8 Oskar-Morgenstern-Platz 1 1.Stock
  • Mittwoch 15.06. 13:15 - 14:45 Hörsaal 8 Oskar-Morgenstern-Platz 1 1.Stock
  • Mittwoch 22.06. 13:15 - 14:45 Hörsaal 8 Oskar-Morgenstern-Platz 1 1.Stock
  • Mittwoch 29.06. 13:15 - 14:45 Hörsaal 8 Oskar-Morgenstern-Platz 1 1.Stock

Information

Ziele, Inhalte und Methode der Lehrveranstaltung

Grundlagen der Graphentheorie. Rekapitulieren von linearer Programmierung und Branch-and-bound methoden.

Zuordnungsprobleme, kürzeste Wege, Maximale Flüsse, Spannende Bäume, Zusammenhangskomponenten, längste Pfade und Netzplantechnik.

Charakteristische Maßzahlen eines Graphen. wie Durchmesser, Zentralität, Kantengewichte, etc.

Komplexität von graphentheortischen Algorithmen.

Anwendungen in der Routenplanung, Netzwerk design, Netzplantechnik, systemisches Risiko und soziale Netzwwerke.
social networks

Applications Networks are apparent in our daily lives. Typical examples are: electrical and power networks, data networks, traffic networks (streets, rails, airline routes), manufacturing and distribution networks, and (online) social networks.
Graphs are used to model these networks in an abstract way and allow to efficiently solve problems on networks by using standardized graph algorithms.
In detail we discuss:
- matchings (stable marriage problem)
- computational complexity
- graph connectivity and search algorithms
- maximum flows
- shortest paths
Furthermore, we consider tools and algorithms for (social) network analysis:
- community detection
- partitioning and clustering
- strong and weak ties
- positive and negative relationships

The goals of this course are to:
- understand the fundamental concepts of networks
- understand basic graph algorithms
- be able to apply algorithms to network based problems
- be able to analyze networks based on different measures

The methods for knowledge transfer and gain are:
- lectures
- joint discussions of exercises and according solutions
- practical implementation of algorithms

Art der Leistungskontrolle und erlaubte Hilfsmittel

Schriftliches Lösen von Übungsbeispielen (hochladen auf Moodle) und abschliessende müdliche Prüfung.

Mindestanforderungen und Beurteilungsmaßstab

Mindestens 60% richtig gelöste Aufgaben + müdliche Abschlussprüfung

Prüfungsstoff

Was vorgetragen wurde. Ein Skriptum wird zur Verfügung gestellt.

Literatur

- T.H. Cormen, C.E. Leiserson, R.L. Rivest, Introduction to Algorithms, MIT Press, 1990
- D. Jungnickel: Graphen, Netzwerke und Algorithmen, BI Wissenschaftsverlag, 3. Auflage, 1994
- J. Bang-Jensen, G. Gutin: Digraphs: Theory, Algorithms and Applications, Springer, 2001
- R.K. Ahuja, T.L. Magnanti, J.B. Orlin, Network Flows: Theory, Algorithms, and Applications, Prentice Hall, 1993
- D. Easley, J. Kleinberg, Networks, Crowds, and Markets: Reasoning About a Highly Connected World, Cambridge University Press, 2010
- E. Tardos, J. Kleinberg, Algorithm Design, Addison Wesley, 2005

Zuordnung im Vorlesungsverzeichnis

Letzte Änderung: Do 03.03.2022 16:08