inf405 - Algorithmische Graphentheorie (Vollständige Modulbeschreibung)

inf405 - Algorithmische Graphentheorie (Vollständige Modulbeschreibung)

Originalfassung Englisch PDF Download
Modulbezeichnung Algorithmische Graphentheorie
Modulkürzel inf405
Kreditpunkte 6.0 KP
Workload 180 h
Einrichtungsverzeichnis Department für Informatik
Verwendbarkeit des Moduls
  • Master of Education (Gymnasium) Informatik (Master of Education) > Wahlpflichtmodule (Theoretische Informatik)
  • Zwei-Fächer-Bachelor Informatik (Bachelor) > Wahlpflicht Theoretische Informatik (30 KP)
Zuständige Personen
  • Lehrenden, Die im Modul (Modulverantwortung)
  • Lehrenden, Die im Modul (Prüfungsberechtigt)
Teilnahmevoraussetzungen
Kompetenzziele
Graphen sind die in der Informatik am häufigsten verwendete Abstraktion. Jedes System, welches aus diskreten Zuständen oder Objekten und Beziehungen zwischen diesen besteht, kann als Graph modelliert werden. Viele Anwendungen erfordern effiziente Algorithmen zur Verarbeitung von Graphen (Turau, 1996).
In diesem Modul werden neben einschlägigen Ergebnissen der Graphentheorie vor allem algorithmische Lösungen typischer Probleme vorgestellt. Die Algorithmen werden im Hinblick auf Effizienz und Anwendbarkeit diskutiert und auch implementiert. Ein wichtiger Aspekt dieses Moduls ist es, verschiedene Herangehensweisen an Probleme zu sehen und unterschiedliche Lösungsstrategien kennenzulernen.

Fachkompetenzen
Die Studierenden:
  • benennen grundlegende Begriffe der Graphentheorie und Optimierung und erläutern sie an Beispielen
  • benennen algorithmische Lösungen typischer Probleme mit Hilfe von Graphen
  • erkennen Situationen, in denen Graphen-Algorithmen angewandt werden können
  • diskutieren Algorithmen bzgl. ihrer Effizienz und Anwendbarkeit
  • implementieren Graphen-Algorithmen
  • kennen Beweisstrategien und können diese wiedergeben


Methodenkompetenzen
Die Studierenden:
  • erweitern ihr Wissen über Algorithmen und deren Komplexität
  • entwickeln ihre Fähigkeiten der Programmierung
  • erweitern ihr Spektrum an Methoden der mathematischen Modellierung


Sozialkompetenzen
Die Studierenden:
  • verwenden die Sprache der Mathematik, um in Gruppen mit unterschiedlichem Vorwissen über Problemstellungen zu diskutieren
  • präsentieren ihre Ideen verständlich
  • erweitern und verbessern eigene Ideen durch die Vorschläge ihrer Kommilitonen


Selbstkompetenzen
Die Studierenden:
  • reflektieren ihr Wissen über Algorithmen und deren Komplexität
  • entwickeln zu gegebenen Problemstellungen geeignete Lösungsansätze
  • hinterfragen Lösungsansätze kritisch
Modulinhalte
  • Bäume
  • Suchverfahren in Graphen
  • Färbung von Graphen
  • Flüsse in Netzwerken
  • Anwendungen von Netzwerkalgorithmen
  • Kürzeste Wege
  • Approximative Algorithmen
Literaturempfehlungen
Jungnickel, Dieter: Graphs, Networks and Algorithms. Springer, Berlin, Heidelberg, 4th edition, 2013. Als E-Book im BIS verfügbar.
Eine ausführliche Literaturliste ist im Skript zur Vorlesung zu finden.
Links
Unterrichtssprache Deutsch
Dauer in Semestern 1 Semester
Angebotsrhythmus Modul jährlich
Aufnahmekapazität Modul unbegrenzt
Modulart je nach Studiengang Pflicht oder Wahlpflicht
Modullevel AS (Akzentsetzung / Accentuation)
Lehr-/Lernform V+Ü
Vorkenntnisse Grundveranstaltungen Mathematik und Informatik
Lehrveranstaltungsform Kommentar SWS Angebotsrhythmus Workload Präsenz
Vorlesung 3 SoSe 42
Übung 1 SoSe 14
Präsenzzeit Modul insgesamt 56 h
Prüfung Prüfungszeiten Prüfungsform
Gesamtmodul
Am Ende der Vorlesungszeit
Klausur