Materialien zum Praktikum

Algorithm Engineering

++Aktuell++
Die Scheine sind ausgestellt und können ab 11.8.2005 bei Frau Beck in Raum D219 abgeholt werden.

Auf dieser Seite werden alle wichtigen Mitteilungen im Zusammenhang mit dem Praktikum Algorithm Engineering von Christian Bachmaier gesammelt.

Neues

29.06.2005 Um vergleichbare Ergebnisse zu den LEDA-Algorithmen zu erhalten, muss der Release-Modus des Compilers verwendet werden, d.h. beim gcc müssen zum compilieren die Parameter "-O -Wall" statt den zum Entwickeln und Debuggen sinnvollen "-g -D_DEBUG -Wall" verwendet werden. Mit "-O3 -Wall" erhält man noch besser optimierten Code. Die im Pool installierte LEDA-Version ist allerdings nur mit "-O" (entspricht "-O1") erstellt worden. Wer das Makefile aus dem Beispielprogramm verwendet, muss nur die erste Zeile beginnend mit CXXFLAGS aus- und die zweite einkommentieren (und zwecks Fairness das Optimierungslevel von 3 auf 1 setzen). Die Laufzeiten der Programme werden damit erheblich reduziert! Nichtsdestotrotz müssen aber "Laufzeitbremsen" wie z.B. unnötige Graphdurchläufe aus dem Code entfernt werden.

21.06.2005 Bei der st-Nummerierung steht jetzt im Algorithmus jeweils explizit welche Orientierung gemeint ist. Dieser Sachverhalt war zuvor leider missverständlich formuliert.

21.06.2005 In der Testphase soll die lineare Laufzeit aller implementiernter Algorithmen verifiziert werden. Ein geeignetes Diagramm im Testbericht soll die tatsächlichen Laufzeiten wiederspiegeln. Zusätzlich soll ein Laufzeitvergleich zu den entsprechenden LEDA-Algorithmen gemacht werden. Tipp: Bei Eindeutigkeit kann man die Ergebnisse der LEDA-Algorithmen mit den eigenen Vergleichen. Alle Testfälle aus dem Pflichtenheft sollen fehlerfrei laufen und dokumentiert werden.

24.05.2005 Jedem Team wird dringend angeraten (soweit nicht schon geschehen) cvs zu verwenden. Eine Kurzanleitug findet sich hier. Als Unix-Gruppe, die das Repository besitzt, bietet sich palg_S05 an.

24.05.2005 Die Dienstagstermine während der Implementierungsphase werden jeweils zur Besprechung/Begutachtung des jeweilig aktuellen C++ Codes benutzt.

24.05.2005 Alle abgegebenen Implementierungen/Milestones müssen lauffähig sein, d.h. mit einem kleinen Testprogramm versehen sein und ein funktionierendes Makefile enthalten bzw. ein funktionierendes Eclipse CDT Projekt sein.

20.05.2005 Beim DFS-Algorithmus im Pseudocode wurde ein Fehler korrigiert. Vielen Dank an Lars Volkhard und Martin Mader für den Hinweis.

09.05.2005 Ein Beispiel zum Überladen von Operatoren ist online.

19.04.2005 Auf vielfachen Wunsch findet ab dem 26.4.2005 die Dienstagsveranstaltung jeweils eine Viertelstunde früher, also von 16:00 - 17:30 Uhr statt.

19.04.2005 Die LEDA Version läßt sich nun auch unter Windows ohne Fehlermeldung kompilieren. Vielen Dank an Matthias Broghammer für den Hinweis!

12.04.2005 Jedes Team bestimmt für jede der fünf Phasen einen Phasenverantwortlichen, der die Phase koordiniert und den dazugehörigen Kolloquiumsvortrag hält. Das soll nicht heissen, der Phasenverantwortliche macht die ganze Arbeit!

12.04.2005 Die Anmeldung mit dem Accounttool ist Pflicht. Alle die das bis jetzt nicht gemacht haben, bitte sofort nachholen.

12.04.2005 Die Folien der Einführungsveranstaltung sind online, auch die mit den konsolidierten Versionen der Algorithmen in Pseudocode!

29.03.2005 Der Download eines kleinen Testprogramms für LEDA wurde freigeschaltet.

Alle persönlichen Nachrichten werden an die jeweilige $USER@inf.uni-konstanz.de Mailadresse verschickt. Bitte stellen Sie sicher, dass diese Adresse auch funktioniert und regelmäßig auf neue Nachrichten kontrolliert wird.

02.03.2005 Ein Beispiel für die Erstellung STL-konformer Iteratoren ist verfügbar.

21.02.2005 Eclipse incl. CDT und LEDA sind im CIP-Pool unter /net/lin_local/palg_S05/ zur Benutzung installiert. Die Zugehörigkeit zur Unix-Gruppe palg_S05 ist dazu erforderlich! Benutzen Sie bitte dazu das Accounttool.

Am 12.04.2005 um 16-18 Uhr findet im Raum E201 die Einführungsveranstaltung zum Praktikum statt.

Am 18.02.2005 um 8:20 Uhr findet im Raum D301 eine Informationsveranstaltung zum Praktikum statt.

Termine

Datum Termine max. Umfang

12.04.2005
Einführungsveranstaltung

15.04.2005
Abgabe: Vorläufiges Pflichtenheft 10 Seiten

19.04.2005
Technische Einführung

22.04.2005
Abgabe: Endgültiges Pflichtenheft 10 Seiten

26.04.2005
Kolloquium Pflichtenheft

29.04.2005
Abgabe: Vorläufiger Entwurf 15 Seiten

06.05.2005
Abgabe: Endgültiger Entwurf 15 Seiten

10.05.2005
Kolloquium Entwurf

13.05.2005
Abgabe: Klassenspezifikation 25 Seiten

17.05.2005
Kolloquium Klassenspezifikation

20.05.2005
Abgabe: Implementierung Milestone 1

03.06.2005
Abgabe: Implementierung Milestone 2

17.06.2005
Abgabe: Vorläufige Implementierung 5.000 Zeilen

01.07.2005
Abgabe: Testbericht 10 Seiten

05.07.2005
Kolloquium Systemabnahme und Test

08.07.2005
Abgabe: Endgültige Implementierung

12.07.2005
Abschluss-Präsentation

Alle Dienstagstermine sind Veranstaltungen mit Anwesenheitspflicht im Raum E201.

In einem Kolloquium hat der jeweilige Phasenverantwortliche 15 Minuten Zeit, etwas über die jeweilige abgeschlossene Phase/Abgabe zu erzählen. Dazu stehen Beamer, Overhead-Projektor und die Tafel zur Verfügung. Die restilichen 15 Minuten (ein Team hat einen Slot von 30 Minuten) werden zur Diskussion darüber genutzt, wobei hier natürlich das ganze Team und nicht nur der Vortragende angesprochen ist.

Alle Abgaben sind jeweils Freitags bis spätestens 12:00 Uhr Mittags per E-Mail im pdf-Format an Christian Bachmaier zu schicken.

Abweichungen nur nach Absprache.

Materialien (nur intern oder mit Passwort zugreifbar)

Lasten

Methoden der Netzwerkanalyse, Vorlesungs-Skript SS 2003 von Ulrik Brandes (pdf)

Ulrik Brandes, Eager st-Ordering, Proc. 10th Europ. Symp. Algorithms (ESA '02), LNCS 2461, pp. 247-256, Springer-Verlag, 2002 (pdf)

Algorithmen in Pseudocode (pdf)

In der Einführungsveranstaltung verwendete Folien (pdf)

LEDA 4.4.1 (im CIP-Pool unter /net/lin_local/palg_S05/LEDA installiert)

Testprogramm für LEDA mit Projektdateien für make auf der shell, Eclipse CDT und Visual Studio .NET 2003

C++ Codefragment das die Erstellung von Iteratoren, wie sie in der STL verwendet werden, zeigt.

C++ Codefragment das aufzeigt, wie man den ++-Operator, sowohl für die Verwendung als Präfix als auch als Postfix überlädt.

C++ Codefragment das aufzeigt, wie man adjacente Kanten bei gerichtiteten und ungerichteten Graphen durchlaufen kann.

Literatur

Bjarne Stroustroup, Die C++ Programmiersprache, 4. Auflage, Addison-Wesley, 2004, ISBN 3-8273-1660-X, Koala Signatur kid 251:c05/u04a (im Semesterapparat)

Timothy Budd, Data structures in C++ using the standard template library, Addison-Wesley, 1998, ISBN 0-201-30879-7, Koala Signatur kid 248/b92a (im Semesterapparat)

SGI, Standard Template Programmer's Guide, http://www.sgi.com/tech/stl/

David R. Musser, Atul Saini, STL tutorial and reference guide, 5. Auflage, 1996, ISBN 0-201-63398-1, Koala Signatur kid 248/m98

Brian W. Kernighan, Dennis M. Ritchie, Programmieren in C, 2. Ausgabe, Hanser, 1990, ISBN 3-446-15497-3, Koala Signatur V 98/509 (im Semesterapparat)

LEDA 4.4.1, The LEDA User Manual, http://www.algorithmic-solutions.com/leda_manual/MANUAL.html

Dokumentationen zu LEDA, http://www.algorithmic-solutions.com/downloads.htm#doku

Kurt Mehlhorn, Stefan Näher, LEDA A Platform for Combinatorial and Geometric Computing, Cambridge Univ. Press, 1999, ISBN 0-521-56329-1, Koala Signatur kid 248/m24, http://www.mpi-sb.mpg.de/~mehlhorn/LEDAbook.html

UML Resource Center, http://www-306.ibm.com/software/rational/uml/

Erich Gamma, Design patterns, 26. Auflage, Addison-Wesley, 2003 ISBN 0-201-63361-2, Koala Signatur kid 240.60/g15(26)

(zu) umfangreiche Musterdokumente

Pflichtenheft

Entwurf

Spezifikation

Testbericht

Tools

Integrierte Entwicklungsumgebung Eclipse (im CIP-Pool mit /net/lin_local/palg_S05/eclipse/start aufrufen)

C++ Plugin für Eclipse CDT (installiert)

UML Editor Dia (im CIP-Pool mit dia aufrufen)

UML Editor Borland Together, kann auch Codegerüst erstellen

Omondo UML-Plugin für Eclipse Eclipse UML Free (hauptsächlich für Java)

Versionskontrolle CVS (installiert), Dokumentation, Mini-Einführung

C++ Compiler GCC 3.3.3 (installiert), Dokumentation unter Linux mit 'man g++'

Build-Tool GNU Make (installiert), Dokumentation

Netwide Assembler für Windows nasm, wird nur Übersetzung von LEDA unter Windows benötigt. (Die Datei nasm.exe muss in nasmw.exe umbenannt werden und sich im Pfad befinden.)

Teameinteilung

Team 1

Matthias Broghammer (broghamm)

Marina Herbst (herbst)

Milda Jasiunaite (milda)

Martin Mader (mader)

Lars Volkhardt (volkhard)

Team 2

Kathrin Bächle (baechle)

Urs Günthör (guenthoe)

Thomas Hermann (hermann)

Natalie Indlekofer (indlekof)

Bobo Nick (nick)

Team 3

Leif Döring (doering)

Miriam Errico (errico)

Gerhard Haffelt (haffelt)

Patrick Hirt (hirt)

Hanna Kungl (kungl)

	29.06.2005 Um vergleichbare Ergebnisse zu den LEDA-Algorithmen zu erhalten, muss der Release-Modus des Compilers verwendet werden, d.h. beim gcc müssen zum compilieren die Parameter "-O -Wall" statt den zum Entwickeln und Debuggen sinnvollen "-g -D_DEBUG -Wall" verwendet werden. Mit "-O3 -Wall" erhält man noch besser optimierten Code. Die im Pool installierte LEDA-Version ist allerdings nur mit "-O" (entspricht "-O1") erstellt worden. Wer das Makefile aus dem Beispielprogramm verwendet, muss nur die erste Zeile beginnend mit CXXFLAGS aus- und die zweite einkommentieren (und zwecks Fairness das Optimierungslevel von 3 auf 1 setzen). Die Laufzeiten der Programme werden damit erheblich reduziert! Nichtsdestotrotz müssen aber "Laufzeitbremsen" wie z.B. unnötige Graphdurchläufe aus dem Code entfernt werden.
	21.06.2005 Bei der st-Nummerierung steht jetzt im Algorithmus jeweils explizit welche Orientierung gemeint ist. Dieser Sachverhalt war zuvor leider missverständlich formuliert.
	21.06.2005 In der Testphase soll die lineare Laufzeit aller implementiernter Algorithmen verifiziert werden. Ein geeignetes Diagramm im Testbericht soll die tatsächlichen Laufzeiten wiederspiegeln. Zusätzlich soll ein Laufzeitvergleich zu den entsprechenden LEDA-Algorithmen gemacht werden. Tipp: Bei Eindeutigkeit kann man die Ergebnisse der LEDA-Algorithmen mit den eigenen Vergleichen. Alle Testfälle aus dem Pflichtenheft sollen fehlerfrei laufen und dokumentiert werden.
	24.05.2005 Jedem Team wird dringend angeraten (soweit nicht schon geschehen) cvs zu verwenden. Eine Kurzanleitug findet sich hier. Als Unix-Gruppe, die das Repository besitzt, bietet sich palg_S05 an.
	24.05.2005 Die Dienstagstermine während der Implementierungsphase werden jeweils zur Besprechung/Begutachtung des jeweilig aktuellen C++ Codes benutzt.
	24.05.2005 Alle abgegebenen Implementierungen/Milestones müssen lauffähig sein, d.h. mit einem kleinen Testprogramm versehen sein und ein funktionierendes Makefile enthalten bzw. ein funktionierendes Eclipse CDT Projekt sein.
	20.05.2005 Beim DFS-Algorithmus im Pseudocode wurde ein Fehler korrigiert. Vielen Dank an Lars Volkhard und Martin Mader für den Hinweis.
	09.05.2005 Ein Beispiel zum Überladen von Operatoren ist online.
	19.04.2005 Auf vielfachen Wunsch findet ab dem 26.4.2005 die Dienstagsveranstaltung jeweils eine Viertelstunde früher, also von 16:00 - 17:30 Uhr statt.
	19.04.2005 Die LEDA Version läßt sich nun auch unter Windows ohne Fehlermeldung kompilieren. Vielen Dank an Matthias Broghammer für den Hinweis!
	12.04.2005 Jedes Team bestimmt für jede der fünf Phasen einen Phasenverantwortlichen, der die Phase koordiniert und den dazugehörigen Kolloquiumsvortrag hält. Das soll nicht heissen, der Phasenverantwortliche macht die ganze Arbeit!
	12.04.2005 Die Anmeldung mit dem Accounttool ist Pflicht. Alle die das bis jetzt nicht gemacht haben, bitte sofort nachholen.
	12.04.2005 Die Folien der Einführungsveranstaltung sind online, auch die mit den konsolidierten Versionen der Algorithmen in Pseudocode!
	29.03.2005 Der Download eines kleinen Testprogramms für LEDA wurde freigeschaltet.
	Alle persönlichen Nachrichten werden an die jeweilige `$USER`@inf.uni-konstanz.de Mailadresse verschickt. Bitte stellen Sie sicher, dass diese Adresse auch funktioniert und regelmäßig auf neue Nachrichten kontrolliert wird.
	02.03.2005 Ein Beispiel für die Erstellung STL-konformer Iteratoren ist verfügbar.
	21.02.2005 Eclipse incl. CDT und LEDA sind im CIP-Pool unter `/net/lin_local/palg_S05/` zur Benutzung installiert. Die Zugehörigkeit zur Unix-Gruppe `palg_S05` ist dazu erforderlich! Benutzen Sie bitte dazu das Accounttool.
	Am 12.04.2005 um 16-18 Uhr findet im Raum E201 die Einführungsveranstaltung zum Praktikum statt.
	Am 18.02.2005 um 8:20 Uhr findet im Raum D301 eine Informationsveranstaltung zum Praktikum statt.

	Lasten
	Methoden der Netzwerkanalyse, Vorlesungs-Skript SS 2003 von Ulrik Brandes (pdf)
	Ulrik Brandes, Eager st-Ordering, Proc. 10th Europ. Symp. Algorithms (ESA '02), LNCS 2461, pp. 247-256, Springer-Verlag, 2002 (pdf)
	Algorithmen in Pseudocode (pdf)
	In der Einführungsveranstaltung verwendete Folien (pdf)
	LEDA 4.4.1 (im CIP-Pool unter `/net/lin_local/palg_S05/LEDA` installiert)
	Testprogramm für LEDA mit Projektdateien für make auf der shell, Eclipse CDT und Visual Studio .NET 2003
	C++ Codefragment das die Erstellung von Iteratoren, wie sie in der STL verwendet werden, zeigt.
	C++ Codefragment das aufzeigt, wie man den ++-Operator, sowohl für die Verwendung als Präfix als auch als Postfix überlädt.
	C++ Codefragment das aufzeigt, wie man adjacente Kanten bei gerichtiteten und ungerichteten Graphen durchlaufen kann.

	Bjarne Stroustroup, Die C++ Programmiersprache, 4. Auflage, Addison-Wesley, 2004, ISBN 3-8273-1660-X, Koala Signatur kid 251:c05/u04a (im Semesterapparat)
	Timothy Budd, Data structures in C++ using the standard template library, Addison-Wesley, 1998, ISBN 0-201-30879-7, Koala Signatur kid 248/b92a (im Semesterapparat)
	SGI, Standard Template Programmer's Guide, http://www.sgi.com/tech/stl/
	David R. Musser, Atul Saini, STL tutorial and reference guide, 5. Auflage, 1996, ISBN 0-201-63398-1, Koala Signatur kid 248/m98
	Brian W. Kernighan, Dennis M. Ritchie, Programmieren in C, 2. Ausgabe, Hanser, 1990, ISBN 3-446-15497-3, Koala Signatur V 98/509 (im Semesterapparat)
	LEDA 4.4.1, The LEDA User Manual, http://www.algorithmic-solutions.com/leda_manual/MANUAL.html
	Dokumentationen zu LEDA, http://www.algorithmic-solutions.com/downloads.htm#doku
	Kurt Mehlhorn, Stefan Näher, LEDA A Platform for Combinatorial and Geometric Computing, Cambridge Univ. Press, 1999, ISBN 0-521-56329-1, Koala Signatur kid 248/m24, http://www.mpi-sb.mpg.de/~mehlhorn/LEDAbook.html
	UML Resource Center, http://www-306.ibm.com/software/rational/uml/
	Erich Gamma, Design patterns, 26. Auflage, Addison-Wesley, 2003 ISBN 0-201-63361-2, Koala Signatur kid 240.60/g15(26)

	Integrierte Entwicklungsumgebung Eclipse (im CIP-Pool mit `/net/lin_local/palg_S05/eclipse/start` aufrufen)
	C++ Plugin für Eclipse CDT (installiert)
	UML Editor Dia (im CIP-Pool mit `dia` aufrufen)
	UML Editor Borland Together, kann auch Codegerüst erstellen
	Omondo UML-Plugin für Eclipse Eclipse UML Free (hauptsächlich für Java)
	Versionskontrolle CVS (installiert), Dokumentation, Mini-Einführung
	C++ Compiler GCC 3.3.3 (installiert), Dokumentation unter Linux mit 'man g++'
	Build-Tool GNU Make (installiert), Dokumentation
	Netwide Assembler für Windows nasm, wird nur Übersetzung von LEDA unter Windows benötigt. (Die Datei nasm.exe muss in nasmw.exe umbenannt werden und sich im Pfad befinden.)