Softwarepraktikum C++/LEDA
Dozent: Daniel Schmitt
Praktikum im Bachelor-Studiengang über 4 SWS
Inhalt
Implementierung von Graph- und geometrischen Algorithmen in C++ unter Verwendung der LEDA-Klassenbibliothek und der C++-Standardbibliothek. Vorrausgesetzt werden:
- Kenntnisse aus Programmierung I (Objektorientierte/Prozedurale Programmierung)
- Kenntnisse aus der Vorlesung "Algorithmen und Datenstrukturen" (Datenstrukturen, Sortieralgorithmen, Graphalgorithmen)
Zeit und Ort
Mittwochs 10:00 - 13:00 in CIP Pool H523
Termine
Die erste Veranstaltung findet am 22. April statt.
Die letzte Uebung und die Einteilung zur Projektphase ist am 27. Mai.
Projekttermine: 01.07 Abgabe Code; 08.07 Abgabe Ausarbeitung (Webseite); 15.07 Abgabe Vortragfolien; 22.07 Vortrag;
Ablauf
In der ersten Haelfte des Semesters werden Sie in C++ und die Bibliothek Leda eingefuehrt.
Hierzu gibt es woechentlich donnerstags eine Pflichtveranstaltung in denen wir Ihnen Elemente aus C++ und Leda naeher bringen und die Uebungen besprechen.
In der zweiten Haelfte des Semesters werden Sie in Gruppen ein Projekt aus den Bereichen Geometrie/Graphtheorie weitgehend selbstaendig bearbeiten.
Scheinvergabe
Zur Teilnahme am Projekt benoetigen Sie mindestens 50% der Punkte aus den Uebungen, bei maximal einer 0 Punkte Wertung.
Einen Schein erhalten Sie nach Abgabe Ihres Projekts inklusive Ausarbeitung und erfolgreicher Vorstellung in einem kurzen Vortrag am Ende des Semesters.
Die Gesamtnote setzt sich zu gleichen Teilen aus den Teilnoten auf Code, Ausarbeitung und Vortrag zusammen.
Uebungen
Zur Teilnahme am Projekt benoetigen Sie 50% der moeglichen Punkte aus den Uebungen. Sie duerfen hoechstens einmal 0 Punkte erzielen.
Abgabe der Übungen per Email immer zu dem darauffolgenden Mittwoch bis 10:00 an dschmittinformatik.uni-trierde.
- 1.Uebungsblatt: pdf Abgabe 29.04; Hilfsdateien msort.cpp; qsort.cpp
- 2.Uebungsblatt: pdf Abgabe 06.05; Hilfsdateien inters.cpp; Liste: int_list.htest_list.cpp
- 3.Uebungsblatt: pdf Abgabe 13.05; Hilfsdateien geowin_polygon.cpp;
- 4.Uebungsblatt: pdf Abgabe 20.05;
- 5.Uebungsblatt: pdf Abgabe 27.05; Hilfsdateien geowin_tchs.cpp;
LEDA Download
Auf der Seite von Algorithmic Solutions gibt es eine kleine Leda Version zum Herunterladen.
Online Referenzen
- Leda Reference: http://www.algorithmic-solutions.info/leda_manual/manual.html
- LEDA Tutorial: http://www.leda-tutorial.org/en/unofficial/
Literatur
B. Stroustrup:
Die C++ Programmiersprache, Addison Wesley, ISBN 3-8273-1660-X
K. Mehlhorn, S. Näher:
LEDA - A platform for combinatorial and geometric computing, Cambridge Press, ISBN 0-521-56329-1
T. H. Cormen, C. E. Leiserson, R. L. Rivest:
Introductions to Algorithms, MIT Press, ISBN 0-262-03141-8
N. M. Josuttis:
The C++ Standard Library, Addison Wesley, ISBN 0-201-37926-0
E. Gamma, R. Helm, R. Johnson, J. Vlissides:
Design Patterns - Elements of Reusable Object-Oriented Software, Addison Wesley, ISBN 0-201-63361-2