Dr. Sigrid Knust
	Programmierpraktikum Graphenalgorithmen WS 03/04

Termine:

Inhalt:

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 [ppt], Grundlagen von GOBLIN, Verzeichnisstruktur, gobshow, Benutzen der Solver, Random Graph Generatoren
22.10.	Einführung C++ [ppt], .gob-Format, Klasse abstractBigraph
27.10.	Basisklassen, Kontext (Sten Zeibig) Makefile [pdf] (Matthias Siemering)
02.11.	Einführung Zeiger [ppt] Iteratoren [pdf] (Konrad Diwold)
10.11.	Tracing/Logging [ppt] (Johannes Witt) Fehlerbehandlung/Exceptions [doc] (Christian Fiekers)
17.11.	Datenstrukturen für Graphen [pdf] (Christiane Zarfl) Graphische Oberfläche GOBLET [ppt] (Dennis Egbers)
24.11.	MST [ppt] (Alexander Scholübbers) Kürzeste Wege [ppt] (Johannes Witt) Knotenfärbungsprobleme [pdf] (D. Egbers, M.G. Haddad, M. Siemering) Templates in C++ [doc] (Maximus G. Haddad)
01.12.	Allgemeines zum 2.Teil des Praktikums [ppt] Routingprobleme [ppt] (K. Diwold, C.Fiekers, R. Zugic) Kantenfärbung in bipartiten Graphen: Algorithmus von König, Euler-Splits [ppt] [doc] (Maximus G. Haddad)
15.12.	Matchings [pdf] (C. Zarfl, S. Zeibig) Kantenfärbung in bipartiten Graphen: Algorithmus von Schrijver [ppt] (Alexander Scholübbers) Ameisenalgorithmen für das TSP [ppt] (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:

Schein:

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

Material zum Download:

• GOBLIN Version 2.6.2.12   (Entpacken mit gunzip, tar xvf)
• Reference Manual (pdf)
• howtogoblin.pdf
• Fehlerliste (xls)