Modulhandbuch MaTIN2012_Kombinatorische Optimierung und Graphenalgorithmen

---

Verantwortlich: Prof. Dr. Randerath

Modul

Anerkennbare Lehrveranstaltung (LV)

• F07 KOGA

Organisation

Bezeichnung Lang MaTIN2012_Kombinatorische Optimierung und Graphenalgorithmen MID MaTIN2012_KOGA MPID G

Zuordnung Studiengang MaTIN2012 Studienrichtung G Wissensgebiete G_VGMT

Einordnung ins Curriculum Fachsemester 2 Wahlpflicht G gültig ab WS 2013/14

Version erstellt 2013-07-03 VID 1 gültig ab WS 2013/14 gültig bis

Zeugnistext

de

Kombinatorische Optimierung und Graphenalgorithmen

en

Combinatorial Optimization and Graph Algorithms

Unterrichtssprache

Deutsch

Modulprüfung

Form der Modulprüfung
sK	Regelfall (bei geringer Prüfungsanzahl: sMP)

Beiträge ECTS-CP aus Wissensgebieten
G_VGMT	5
Summe	5

Aufwand [h]: 150

---

Prüfungselemente

Vorlesung / Übung

Form Kompetenznachweis
bÜA	Präsenz- und Selbstlernaufgaben

Beitrag zum Modulergebnis
bÜA	unbenotet

Spezifische Lernziele

Lerninhalte(Kenntnisse)

• KOGA-Grundlagen (PFK.2)
• Minimale aufspannende Bäume (PFK.2 PFK.4)
• Lineare Programme (PFK.4)
• Gewichtete Matchings und das Chinesische Briefträgerproblem (PFK.2, PFK.4)
• Flüsse in Netzwerken (PFK.4)
• Spezielle Diskrete und Kombinatorische Optimierungsprobleme (PFK.2)

Fertigkeiten

• Die Studierenden sind in der Lage Verfahren und Konzepte der Graphentheorie und der Kombinatorischen Optimierung zur Beschreibung und algorithmischen Lösung von Problemstellungen der Informatik, der Technik und des täglichen Lebens anzuwenden. (PFK.3,PFK.7)
• Sie haben die Fertigkeit Verfahren und Konzepte der Graphentheorie und der Kombinatorischen Optimierung zur Beschreibung und algorithmischen Lösung von Problemstellungen der Informatik, der Technik und des täglichen Lebens anzupassen. (PFK_2, PFK.5,PFK_6)
• Sie können algorithmische Denk- und Arbeitweisen wie Komplexität von Problemklassen, Effizienz von Algorithmen und Approximation, die sie induktiv an Optimierungsaufgaben in Netzwerken und gewichteten Graphen erlernt haben, anwenden. (PFK_3,PFK.4,PFK.5,PSK.3)

Exemplarische inhaltliche Operationalisierung

Anwendung algorithmischer Denk- und Arbeitsweisen: Am Beispiel des Kruskal-Algorithmus zur Bestimmung minimal aufspannender Bäume in gewichteten Graphen wird ein Greedy-Verfahren vorgestellt, welches eine optimale Lösung garantiert. Die Analyse der algorithmischen Lösung dieses Optimierungsproblems führt zur Einführung matroider Strukturen. Hierdurch wird es möglich zu analysieren, wann Greedy-Verfahren Optimierungsprobleme lösen.