Modulhandbuch BaTIN2012_Graphentheorie

---

Verantwortlich: Prof. Dr. Randerath

Modul

Anerkennbare Lehrveranstaltung (LV)

• F07 GRT

Organisation

Bezeichnung Lang BaTIN2012_Graphentheorie MID BaTIN2012_GRT MPID WPA

Zuordnung Studiengang BaTIN2012 Studienrichtung H Wissensgebiete WIN

Einordnung ins Curriculum Fachsemester 6 Wahl WPM5-Wahlkatalog BIN

Version erstellt 2013-05-29 VID 1 gültig ab SS 2013 gültig bis

Zeugnistext

de

Graphentheorie

en

Graph Theory

Unterrichtssprache

Deutsch

Modulprüfung

Form der Modulprüfung
sMP	100% (mündliche Prüfung)

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

Aufwand [h]: 150

---

Prüfungselemente

Vorlesung / Übung

Form Kompetenznachweis
bÜA	Präsenzübung und Selbstlernaufgaben

Beitrag zum Modulergebnis
bÜA	unbenotet

Spezifische Lernziele

Lerninhalte(Kenntnisse)

• Grundlagen der Kombinatorik und Asymptotische  Analyse (PFK.1, PFK.2,PFK.3)
• Grundlagen der Graphentheorie (PFK.1, PFK.2,PFK.3)
• Traversierung in Graphen und das Problem des kürzesten Weges (PFK.1,PFK.2,PFK.3)
• Matchings und Flüsse (PFK.1,PFK.2,PFK.3)
• Färbungen (PFK.1,PFK.2,PFK.3)

Fertigkeiten

• Die Studierenden beherrschen grundlegende Kenntnisse über Graphen und Algorithmen (PFK.1, PFK.2, PSK.3)
• Sie sind in der Lage Verfahren und Konzepte der Graphentheorie zur Beschreibung und algorithmischen Lösung von Problemstellungender Informatik, der Technik und des täglichen Lebens anzuwenden. (PFK.1, PFK.2, PSK.3)

Exemplarische inhaltliche Operationalisierung

Die Anwendung graphentheoretischer Verfahren und Konzepte zur Beschreibung und algorithmischen Lösung von Problemstellungen der Informatik kann am Beispiel des vergleichsbasierten Sortierens von Schlüsselwerten - einem  Kernproblem der Informatik - veranschaulicht werden. Die Bestimmung eines Hamiltonweges in einem Turnier, d.h. einem vollständigen Graphen mit einer Orientierung, modelliert  ebenfalls das Sortierproblem. Der klassische graphentheoretische Algorithmus von Redei zur Lösung des  Hamiltonweg-Problems aus dem Jahr 1934 entspricht dem InsertionSort Verfahren. Zur Verankerung wird der optimale  MergeSort-Algorithmus in ein graphentheoretisches Verfahren zur Lösung des Hamiltonweg-Problems in Turnieren übersetzt.

Praktikum

Form Kompetenznachweis
bSZ	Präsenzübung

Beitrag zum Modulergebnis
bSZ	unbenotet, Voraussetzung für die mündliche Prüfung

Spezifische Lernziele

Lerninhalte(Kenntnisse)

• Grundlagen: Graphentheorie mit Maple (PFK.3)
• Ausgewählte Graphenalgorithmen mit Maple (PFK.5,PFK.6)

Fertigkeiten

• Die Studierende sind in der Lage einfache graphentheoretische Probleme mit Maple zu lösen (PFK.5, PFK.6)

Exemplarische inhaltliche Operationalisierung

Die Lösung  einfacher graphentheoretischer Probleme im Kontext des Computer-Algebra-Systems MAPLE kann z. B. für das Problem der Tiefensuche angewendet werden. Das aus der Vorlesung bekannte Prinzip der Tiefensuche soll verwendet und in  Maple  implementiert werden um den Ausgang eines im MAPLE-Kontext zufällig erzeugten Irrgartens zu finden.