Prof. Dr. Pape - Labor Algorithmen

• Home
  • Vorlesungen
  • Labore
    • Rechnerübungen Informatik 1
    • XML Rechnerübung
    • Softwarelabor
    • Algorithmen
  • Seminare
  • Studienarbeiten
  • Abschlussarbeiten
  • Projekte

Labor Algorithmen Wintersemester 10

Es sollen Schnittpunkte von Strecken in der Ebene berechnet werden. Zum einen der naive Algorithmus und zum anderen der Bentley-Ottmann-Algorithmus. Implementierung in Java

Es brauchen nur Strecken in allgemeiner Lage berücksichtigt werden: keine parallelen Strecken, Strecken haben maximal einen Schnittpunkt miteinander, keine mehrfachen Schnittpunkte, Endpunkte alle Strecken haben unterschiedliche x- und y-Koordinaten

• 1. Teil, Abgabe bis 18.11., Schnittpunktberechnung zweier Strecken (Line2D) und naiver Algorithmus inklusive JUnit-Tests. Ausarbeitung mit Herleitung der Schnittpunktberechnung und Beschreibung des Bentley-Ottmann-Algorithmus. Entwurf des Bentley-Ottmann-Algorithmus (wie soll x-Ordnung und Oben-Unten-Ordnung mit Java Collection Framework implementiert werden).
• 2. Teil, Abgabe bis letzte Vorlesungswoche, Bentley-Ottmann-Algorithmus, Zeitmessung naiver Algorithmus und Bentey-Ottmann-Algorithmus anhand zwei Szenarien (Szene mit n Strecken und O(n) Schnittpunkten, Gitternetz mit O(n*n) Schnittpunkten). Die JUnit-Tests müssen nahezu 100% des Codes der Algorithmen abdecken.

Labor zu Algorithmen Sommersemester 10

Dieses Labor ist Pflicht im Modul "Algorithmen und Anwendungen" des Masterstudiengangs. Ziel ist die effiziente Implementierung und der Vergleich von Algorithmen. Programmiersprache ist Java (JDK 1.6).

Laboraufgaben

Es sollen balancierte binäre Suchbäume (Rot-Schwarz-Bäume) mit Java im Rahmen des Java Collection Frameworks implementiert und mit der Java Implementierung verglichen werden (bei Java werden auch Rot-Schwarz-Bäume verwendet).

Keine Gruppenarbeit

Die Aufgabe ist ein zwei Teilen, die getrennt abgegeben werden sollen, unterteilt:

1. Normale binäre Suchbäume. Abgabe bis spätestens 20.5. Die Interfaces Iterable, Collection und Set (oder SortedSet) müssen implementiert werden (mit generischen Typen). Die Implementierung muss mit JUnit getestet werden. Versuchen Sie die JUnit Tests auf Ebene der Interfaces Iterable, Collection und Set zu implementieren, um die Tests für den nächsten Teil wiederzuverwenden. Achten Sie auf die teilweise sehr detaillierte Spezifikation der Interfaces. Zusätzlich müssen Sie einen kurze schriftliche Ausarbeitung abgeben, in der Sie Rot-Schwarz-Bäume und deren Funktionsweise erklären..
2. Implementierung eines Rot-Schwarz-Baums. Abgabe bis letzte Vorlesungwoche 1.7. JUnit-Test. Vergleich der Ausführungszeiten mit der Java Implementierung TreeSet (diese verwendet TreeMap, welche Rot-Schwarz-Bäume implementiert). Die Zeiten sollen mit (ganzen) Zahlen (aufsteigende Ordnung) gemessen werden. Die Ausarbeitung muß um die Messunge der Zeiten ergänzt werden (siehe unten für Testfälle zur Zeitmessung)

Bei der Abgabe ist folgendes zu beachten :

• Algorithmen und Datenstrukturen müssen mit JUnit-Tests getestet werden. Die JUnit-Tests müssen alle funktionieren.
• Die Testfälle müssen 100% des Codes ihrer Implementierung abdecken (ausser der Klassen der Präsentationsschicht und Fehlerbehandlung).
(EclEmma verwenden)
• Diese Richtlinien zur Java-Programmierung müssen eingehalten sein.
• Alle öffentlichen Methoden sind mit Javadoc zu dokumentieren. Die Interface-Methoden müssen nur so weit zusätzlich dokumentiert werden, wie es notwendig ist (z.B. Laufzeitverhalten oder ähnliches).
• Der Quelltext muss weitgehend frei von Redundanzen sein
• Ein Beschreibung der Ergebnisse in Papierform ist mit abzugeben. Insbesondere die Zeitmessungen, Erfahrungen und Entwurf. Quelltext schaue ich mir am Bildschirm an.

Zeitmessung

Die Zeit soll schrittweise für wachsende Eingabegrößen (n=10, n=100, ...) für den besten, durchschnittichen und schlimmsten Fall gemessen werden. Da der schlimmste Fall für das Löschen recht schwierig zu ermittlen ist, sollen nur das Suchen und Einfügen untersucht und verglichen werden (contais und add Methode).

Testfälle für die Zeitmessung