Softwarepraktikum "C++/LEDA"
Dozent: Daniel Schmitt
Praktikum im Bachelor-Studiengang und im Diplom-Grundstudium über 4 SWS
Inhalt
Implementierung von Graph- und geometrischen Algorithmen in C++ unter Verwendung der LEDA-Klassenbibliothek und der C++-Standardbibliothek.
Vorkenntnisse
- Kenntnisse aus Informatik I (Objektorientierte/Prozedurale Programmierung)
- Kenntnisse aus der Vorlesung "Algorithmen und Datenstrukturen (Info II)" sind empfehlenswert. (Datenstrukturen, Suchalgorithmen, Graphalgorithmen)
Zeit und Ort
Donnerstags 8:30 - 11:30 in CIP Pool H523
Termine
Die erste Veranstaltung findet am 25.10 statt.
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 Elmente aus C++ und Leda naeher bringen und die Uebungen besprechen.
In der zweiten Haelfte des Semesters werden Sie in Gruppen ein Projekt aus dem Bereich der Geometrie weitgehend selbstaendig loesen.
Scheinvergabe
Zur Teilnahme am Projekt benoetigen Sie mindestens 50% der Punkte aus den Uebung, bei maximal einer 0 Punkte Wertung.
Ein Schein erhalten Sie nach Abgabe Ihres Projekts inklusive Ausarbeitung und erfolgreicher Vorstellung Ihres Projekts in einem kurzen Vortrag am Ende des Semesters.
Projekte
- Visualisierung des Schnitts Convexer Polygone: pdf
- Visualisierung des Quickhull Algorithmus in 2D: pdf
- Visualisierung des allgemeinen Quickhull Algorithmus in 2D: pdf
- Visualisierung Point Location mit der Streifenmethode: pdf
Online Referenzen
- Leda Reference: http://www.algorithmic-solutions.info/leda_manual/manual.html
- LEDA Tutorial: www.leda-tutorial.org/en/unofficial/
- LEDA Book: www.mpi-inf.mpg.de/~mehlhorn/LEDAbook.html
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