PTI01960 – Graphenalgorithmen

Modul
Graphenalgorithmen
Graph Algorithms
Modulnummer
PTI01960
Version: 1
Fakultät
Physikalische Technik / Informatik
Niveau
Bachelor
Dauer
1 Semester
Turnus
Sommersemester
Modulverantwortliche/-r

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

Dozent/-in(nen)

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

Lehrsprache(n)

Deutsch
in "Graphenalgorithmen"

ECTS-Credits

5.00 Credits

Workload

150 Stunden

Lehrveranstaltungen

3.00 SWS (2.00 SWS Vorlesung | 1.00 SWS Praktikum)

Selbststudienzeit

105.00 Stunden
45.00 Stunden Vorbereitung Lehrveranstaltung - Graphenalgorithmen
60.00 Stunden Selbststudium - Graphenalgorithmen

Prüfungsvorleistung(en)
Keine
Prüfungsleistung(en)

mündliche Prüfungsleistung
Modulprüfung | Prüfungsdauer: 30 min | Wichtung: 100%
in "Graphenalgorithmen"

Medienform
Keine Angabe
Lehrinhalte/Gliederung
  • 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
Qualifikationsziele

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.

Besondere Zulassungsvoraussetzung

keine

Empfohlene Voraussetzungen

Grundkenntnisse aus der Graphen- und Komplexitätstheorie

Fortsetzungsmöglichkeiten
Keine Angabe
Literatur
  • 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)
Hinweise
Keine Angabe