PTI01960 – Graph Algorithms

Module
Graph Algorithms
Graphenalgorithmen
Module number
PTI01960
Version: 1
Faculty
Physikalische Technik / Informatik
Level
Bachelor
Duration
1 Semester
Semester
Summer semester
Module supervisor

Prof. Dr. Maren Hinrichs
Maren.Hinrichs(at)fh-zwickau.de

Lecturer(s)

Prof. Dr. Maren Hinrichs
Maren.Hinrichs(at)fh-zwickau.de

Course language(s)

German
in "Graphenalgorithmen"

ECTS credits

5.00 credits

Workload

150 hours

Courses

3.00 SCH (2.00 SCH Vorlesung | 1.00 SCH Internship)

Self-study time

105.00 hours
45.00 hours Examination preparation - Graphenalgorithmen
60.00 hours Self-study - Graphenalgorithmen

Pre-examination(s)
None
Examination(s)

mündliche Prüfungsleistung
Module examination | Examination time: 30 min | Weighting: 100%
in "Graphenalgorithmen"

Media type
No information
Instruction content/structure
  • Graphenalgorithmen und deren Komplexität - Komplexitätsklassen (P, NP)
  • Beispiele harter Probleme (z.B. Tour-, Färbe- oder Matchingprobleme)
  • Approximative Lösungsmethoden und spezielle Lösungsansätze für schwere Probleme
Qualification objectives

Die Studierenden kennen wichtige Methoden, Algorithmen und Ergebnisse der Graphentheorie und der Komplexitätstheorie. Dabei liegt der Schwerpunkt auf anwendungsnahen harten Problemen. Die Studierenden lernen Lösungsansätze kennen, die sich in der Praxis bewährt haben.

Special admission requirements

keine

Recommended prerequisites

Grundkenntnisse aus der Graphen- und Komplexitätstheorie

Continuation options
No information
Literature
  • Nitzsche, M. : Graphen für Einsteiger (Vieweg & Teubner)
  • Krumke, S.O.; Noltemeier, H.: Graphentheoretische Konzepte und Algorithmen (Springer Vieweg)
  • Garey, M.R.;  Johnson, D.S.: Computers and Intractability (Freeman & Co, New York)
  • Uwe Schöning: Theoretische Informatik – kurz gefasst (Spekrum)
Notes
No information