Universität Wien FIND

Bedingt durch die COVID-19-Pandemie können kurzfristige Änderungen bei Lehrveranstaltungen und Prüfungen (z.B. Absage von Vor-Ort-Lehre und Umstellung auf Online-Prüfungen) erforderlich sein. Melden Sie sich für Lehrveranstaltungen/Prüfungen über u:space an, informieren Sie sich über den aktuellen Stand auf u:find und auf der Lernplattform moodle. ACHTUNG: Lehrveranstaltungen, bei denen zumindest eine Einheit vor Ort stattfindet, werden in u:find momentan mit "vor Ort" gekennzeichnet.

Regelungen zum Lehrbetrieb vor Ort inkl. Eintrittstests finden Sie unter https://studieren.univie.ac.at/info.

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

4.00 ECTS (2.00 SWS), SPL 4 - Wirtschaftswissenschaften
Prüfungsimmanente Lehrveranstaltung
DIGITAL
Di 18.05. 13:15-14:45 Digital

An/Abmeldung

Details

max. 30 Teilnehmer*innen
Sprache: Englisch

Lehrende

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

Dienstag 02.03. 13:15 - 14:45 Digital
Dienstag 09.03. 13:15 - 14:45 Digital
Dienstag 16.03. 13:15 - 14:45 Digital
Dienstag 23.03. 13:15 - 14:45 Digital
Dienstag 13.04. 13:15 - 14:45 Digital
Dienstag 20.04. 13:15 - 14:45 Digital
Dienstag 27.04. 13:15 - 14:45 Digital
Dienstag 04.05. 13:15 - 14:45 Digital
Dienstag 11.05. 13:15 - 14:45 Digital
Dienstag 01.06. 13:15 - 14:45 Digital
Dienstag 08.06. 13:15 - 14:45 Digital
Dienstag 15.06. 13:15 - 14:45 Digital
Dienstag 22.06. 13:15 - 14:45 Digital
Dienstag 29.06. 13:15 - 14:45 Digital

Information

Ziele, Inhalte und Methode der Lehrveranstaltung

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

Students collect points with the following actions:
- homework exercises: students prepare solutions to given exercises and upload them in Moodle (max. 20 points)
- programming exercise: students implement a selected algorithm (max. 30 points)
- online or written exam (max. 50 points)

Mindestanforderungen und Beurteilungsmaßstab

- Attendance at the lecture / exercise units is NOT required, except for the FIRST lecture on March 2.
- The grade is determined by the total number of points collected:
1: 89 - 100
2: 76 - 88
3: 63 - 75
4: 50 - 62
5: 0 - 49
- There is NO minimal required number of points for each action.

Prüfungsstoff

For the final exam you have to know:
- the contents of the lecture slides
- the solutions to the homework exercises

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: Mi 21.04.2021 11:25