Modulhandbuch BaTIN2012_Graphentheorie


Verantwortlich: Prof. Dr. Randerath

Modul

Anerkennbare Lehrveranstaltung (LV)

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.

Topic-Revision: r7 - 01 Dec 2017, 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