Programmierpraktikum Graphenalgorithmen WS03/04


	Programmierpraktikum Graphenalgorithmen WS 03/04

Termine:

Praktikum:
Mo	12:15-13:45	Raum 31/322

Inhalt:

Graphen gehören zu den wichtigsten Modellen der Informatik die zahlreiche praktische Anwendungen haben (z.B. im Verkehrs- und Telekommunikationsbereich, der Produktionsplanung oder allgemein bei vielen kombinatorischen Optimierungsproblemen).

Zunächst sollen die Teilnehmer die an der Universität Augsburg implementierte C++-Graphen-Bibliothek GOBLIN (die z.B. auch Routinen zur graphischen Ausgabe von Graphen bereitstellt) kennenlernen und testen. Danach sollen eigene Algorithmen (z.B. zur Kantenfärbung in bipartiten Graphen, Ameisenalgorithmen für das TSP) in C implementiert werden und in die Bibliothek miteingebunden werden. Die erforderlichen Grundlagen der Programmiersprache C/C++, die Verwendung der Graphen-Library GOBLIN und die relevanten Algorithmen sollen gemeinsam erarbeitet werden, größere Vorkenntnisse werden nicht vorausgesetzt.

Ziele des Praktikums:

vertiefende Kenntnisse in Graphenalgorithmen (insbesondere bzgl. praktischer Umsetzung und effizienter Implementierung)
Erlernen der Programmiersprache C/C++
Arbeiten mit einem größeren Softwarepaket
Arbeiten im Team an einem größeren Softwareprojekt (Qualitätssicherung, Reviews, Programmierrichtlinien, Testen, Fehlersuche, Dokumentation)
Präsentation von Kurzvorträgen

Inhalt der einzelnen Termine:

14.10.
Einführung, Grundlagen von GOBLIN, Verzeichnisstruktur, gobshow, Benutzen der Solver, Random Graph Generatoren

22.10.
Einführung C++, .gob-Format, Klasse abstractBigraph

27.10.
Basisklassen, Kontext (Sten Zeibig)
Makefile (Matthias Siemering)

02.11.
Einführung Zeiger
Iteratoren (Konrad Diwold)

10.11.
Tracing/Logging (Johannes Witt)
Fehlerbehandlung/Exceptions (Christian Fiekers)

17.11.
Datenstrukturen für Graphen (Christiane Zarfl)
Graphische Oberfläche GOBLET (Dennis Egbers)

24.11.
MST (Alexander Scholübbers)
Kürzeste Wege (Johannes Witt)
Knotenfärbungsprobleme (D. Egbers, M.G. Haddad, M. Siemering)
Templates in C++ (Maximus G. Haddad)

01.12.
Allgemeines zum 2.Teil des Praktikums
Routingprobleme (K. Diwold, C.Fiekers, R. Zugic)
Kantenfärbung in bipartiten Graphen: Algorithmus von König, Euler-Splits (Maximus G. Haddad)

15.12.
Matchings (C. Zarfl, S. Zeibig)
Kantenfärbung in bipartiten Graphen: Algorithmus von Schrijver (Alexander Scholübbers)
Ameisenalgorithmen für das TSP (Radomir Zugic)

05.01. Koordination der Implementierungen
12.01. Koordination der Implementierungen
19.01. Koordination der Implementierungen
26.01. Koordination der Tests, Dokumentation
02.02. Abschlussvorträge der Gruppen

Vorkenntnisse:

Grundlagen von Algorithmen und Datenstrukturen (Kenntnisse von Graphenalgorithmen nützlich, aber nicht unbedingt notwendig),
Kenntnisse einer Programmiersprache (Programmierkenntnisse in C/C++ nützlich, aber ebenfalls nicht Voraussetzung).

Teilnehmer:

Teilnehmen können alle interessierten Studenten aus den Studiengängen Mathematik, Angewandte Systemwissenschaft und Cognitive Science. Dieses Praktikum zählt auch als Programmierpraktikum (P4) für den Bachelorstudiengang Mathematik/Informatik. Insbesondere können im Anschluss an das Praktikum Bachelor- oder Diplomarbeiten vergeben werden.

Schein:

Voraussetzung für den Erwerb eines Scheins zur Veranstaltung ist die regelmäßige aktive Teilnahme und eine schriftliche Ausarbeitung (mit Halten eines Kurzvortrags).

Literatur:

GOBLIN-Homepage
U. Breymann (2003): C++, Einführung und professionelle Programmierung, Hanser
R.K. Ahuja, T.L. Magnanti, J.B. Orlin (1993): Network Flows, Prentice Hall
D. Jungnickel (1987): Graphen, Netzwerke und Algorithmen, BI-Verlag
R. Sedgewick (1988): Algorithms, Addison Wesley
V. Turau (1996): Algorithmische Graphentheorie, Addison Wesley
A. Schrijver (1999): Bipartite edge coloring in O(Delta m) time, SIAM J. Comput. 28, No.3, 841-846
Homepage Ameisenalgorithmen für das TSP
M.Dorigo, V. Maniezzo, A. Colorni (1996): The Ant System: Optimization by a Colony of Cooperating Agents, IEEE Transactions on Systems, Man, and Cybernetics-Part B, 26, 29-41
M. Dorigo, L.M. Gambardella (1997): Ant Colonies for the Traveling Salesman Problem, BioSystems 43, 73-81
M. Dorigo G. Di Caro, L. M. Gambardella (1999): Ant Algorithms for Discrete Optimization, Artificial Life, 5, 137-172
T. Stützle, M. Dorigo (1999): ACO Algorithms for the Traveling Salesman Problem, In: K. Miettinen, M. Makela, P. Neittaanmaki, J. Periaux, editors, Evolutionary Algorithms in Engineering and Computer Science, Wiley