Module Import 04IN2016 - Efficient Graph Algorithms

Status: Published
Workload6 ECTS = 180 hrs
Credits, Weight6 ECTS, (n.s.)
Language of Instruction German
Semester (n.s.)
Duration1 Sem.
M/E Elective
Courses
Course No. Type Name MA/EL Workload Credits Contact Hours Selfstudy Group Size
04IN2016-1 Lecture/Exercise Efficient Graph Algorithms (n.s.) 6 ECTS = 180 hrs 6 ECTS 4 hrs/week = 60 hrs 120 hrs 30
Learning Outcomes

Die Studierenden können diskrete Sachverhalte als Graphen modellieren und Problemstellungen auf Graphen spezifizieren. Sie beherrschen den Umgang mit Suchverfahren und deren Anpassung auf konkrete Probleme. Sie kennen die wichtigsten algorithmischen Ansätze und können deren Aufwand bewerten.

Content
  1. Grundlagen (Definitionen, Vorgehensweise der Algorithmik)
  2. Datenstrukturen (Speicherung von Graphen, Programmierinterface (API))
  3. Gerichtete Traversierungsverfahren (Suche, Breitensuche, Tiefensuche, Kahn-Knuth-Verfahren, Dijkstra-Verfahren, A*-Verfahren, Ford-Moore-Verfahren)
  4. Ungerichtete Traversierungsverfahren (ungerichtete Suche, Breitensuche, Tiefensuche, Prim-Dijkstra-Verfahren)
  5. Strukturunabhängige Verfahren (Union-Find-Problem, Kruskal-Verfahren, Warshall-Verfahren, Floyd-Verfahren)
  6. Pfadverfolgungsverfahren (Eulersche Pfade, Hamiltonsche Pfade, Backtracking, Greedy-Verfahren, Branch-and-Bound)
  7. Problemkreis "Flüsse" (Flussmessung, Flussmaximierung, Ford-Fulkerson-Verfahren)
  8. Problemkreis "Zuordnung" (Matching, ungarisches Verfahren)
Teaching Methods

(not specified)

Prerequisites

Grundkenntnisse in Algorithmen und Datenstrukturen

Examination Methods

Klausur

Credit Requirements

(not specified)

References

Andreas Brandstädt. Graphen und Algorithmen. B.G. Teubner, 1994.
Jürgen Ebert. Effiziente Graphenalgorithmen. Akademische Verlagsgesellschaft, 1981.
Robert Sedgewick. Algorithms in Java. Addison-Wesley, 2004.

Volker Turau. Algorithmische Graphentheorie. Addison-Wesley, 1996.

Use of this Module
  1. unmodified as Elective  -    BSc Computer Science 2017  -    Mandatory elective courses Computer Science  -    Efficient Graph Algorithms
  2. unmodified as Elective  -    BSc Computational Visualistics 2017  -    Mandatory elective courses Computer Science  -    Efficient Graph Algorithms
  3. unmodified as Elective  -    BSc Computational Visualistics 2017  -    Mandatory elective courses in Computational Visualistics or computer science  -    Efficient Graph Algorithms
  4. unmodified as Elective  -    MSc Computer Science 2017  -    Mandatory elective courses in mathematics and theoretical computer science  -    Efficient Graph Algorithms
  5. unmodified as Elective  -    MSc Computer Science 2017  -    Mandatory elective courses Computer Science  -    Efficient Graph Algorithms
  6. unmodified as Elective  -    MSc Computational Visualistics 2017  -    Mandatory elective courses Computer Science  -    Efficient Graph Algorithms
  7. unmodified as Elective  -    MSc Computational Visualistics 2017  -    Mandatory elective courses in Computational Visualistics or computer science  -    Efficient Graph Algorithms
  8. unmodified as Elective  -    MSc Computational Visualistics 2017  -    Mandatory elective courses in theoretical computer science and mathematics  -    Efficient Graph Algorithms
  9. unmodified as Elective  -    MSc Computational Visualistics 2017  -    Mandatory elective courses in theoretical computer science and mathematics or natural and social sciences  -    Efficient Graph Algorithms
  10. unmodified as Elective  -    MSc Web Science 2017  -    Mandatory elective courses Computer Science  -    Efficient Graph Algorithms
Responsible / Organizational Unit
Frey, Johannes / Institute for Computer Science
Additional Information

(not specified)

Last change
Apr 24, 2018 by Frey, Johannes
Last Change Module
May 15, 2012 by Frey, Johannes