Text in english

Algorithmische Graphentheorie

Grundlagen der Graphentheorie und Algorithmen auf Graphen

Kurs nur in Deutsch

Semesterwochenstunden:

4

Leistungspunkte:

5

Vorkenntnisse:

Mathematik 1 und 2, insbesondere Kombinatorik, Lineare Algebra und Rekursionsgleichungen

Veranstaltungstyp:

Vorlesung mit Übungen

Semesterturnus:

Winter- bzw. Sommersemester

Arbeitsaufwand:

150 Stunden, davon:
65 Stunden Präsenzzeit,
85 Stunden Vor- und Nachbearbeitung des Lehrstoffs und Prüfungsvorbereitung

Lernziel:

Kenntnis der grundlegenden Begriffe der Graphentheorie sowie der Algorithmen auf Graphen, sowie Übertragung dieser Inhalte auf konkrete Anwendungsbeispiele.
Analyse der Laufzeit bzw. Komplexität, Entwickeln von Problemstellungen als Modell der Graphentheorie. Bewertung von Lösungsverfahren für konkrete Projekte.

Lehrinhalte:

Graphen zählen zu den wichtigsten Modellen der Informatik. Viele Problemstellungen lassen sich graphentheoretisch beschreiben, beispielsweise

  • Ausfallsicherheit von Netzen
  • Suchstrategien
  • Finden von kürzesten Wegen
  • Routenplanung
  • Zuordnungsprobleme
  • Maximale Flüsse in Netzwerken

Nach einer Einführung in die Theorie und Darstellung von Graphen werden die wichtigsten Algorithmen für Graphentheorie vorgestellt, analysiert und bewertet.
Die Methoden werden dann auf konkrete Fragestellungen übertragen.
Begleitend zur Vorlesung werden Übungen angeboten.

Literatur:

  • Christina Büsing, Graphen- und Netzwerkoptimierung, Spektrum 2010
  • Shimon Even, Graph Algorithms, 2nd ed., Cambridge 2012
  • Dieter Jungnickel, Graphs, Networks and Algorithms, 3rd ed., Springer 2007
  • Sven Oliver Krumke, Hartmut Noltemeier: Graphentheoretische Konzepte und Algorithmen, 3. Auflage, Springer 2012
  • Angelika Steger, Diskrete Strukturen 1, Springer Verlag 2007
  • Volker Turau, Algorithmische Graphentheorie, Oldenbourg 2009
  • T. Cormen et al: Introduction to Algorithms, MIT Press, 2009

Leistungsnachweis:

Schriftliche Prüfung (90 min)

Modulverantwortliche/r:

Prof. Dr. Hufnagel





TH Nürnberg
Fakultät Informatik
Webmaster-IN



Root- Zertifikat

© 2019 Fakultät Informatik