Modulhandbuch MaTIN2012_Kombinatorische Optimierung und Graphenalgorithmen


Verantwortlich: Prof. Dr. Randerath

Modul

Anerkennbare Lehrveranstaltung (LV)

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.

Topic-Revision: r6 - 19 Jul 2018, GeneratedContent
 
Diese Seite läuft auf FoswikiDas Urheberrecht © liegt bei den mitwirkenden Autoren. Alle Inhalte dieser Kollaborations-Plattform sind Eigentum der Autoren.
Ideen, Anfragen oder Probleme bezüglich Foswiki? Feedback senden