Objektorientierte Programmierung
LVA 185.162, VL 2.0, 2007 W

8. Übungsaufgabe

Themen:

Generizität, nebenläufige Programmierung

Termine:

Ausgabe: 13.12.2007
reguläre Abgabe: 10.01.2008, 12:45 Uhr
nachträgliche Abgabe: 17.01.2008, 12:45 Uhr

Abgabeverzeichnis:

Aufgabe8

Programmaufruf:

java Test

Grundlage:

Skriptum bis Seite 131 und die Seiten 139 bis 145

Aufgabe

Welche Aufgabe zu lösen ist:

Eine häufig genutzte Datenstruktur zum Speichern und Auffinden von Daten ist ein binärer Suchbaum. Dabei werden in den Knoten des Baums der Schlüssel und die Daten gespeichert. Daten mit kleinerem Schlüssel werden im linken Teilbaum, Daten mit größerem Schlüssel im rechten Teilbaum gespeichert. Schlüssel können beliebige Datentypen sein, die einen Vergleich unterstützen, wie z.B. ganze Zahlen oder Zeichenketten.
        7
      /   \
     4     8
   /   \     \
  2     5     11

Definieren Sie ein Interface KeyType, das die Methoden less and equal unterstützt.

Entwickeln Sie eine generische Klasse BinTree für einen binäreren Suchbaum mit einem Schlüssel eines Untertyps von KeyType, die in einem Knoten den Schlüssel und (nicht als Teil des Schlüssels) einen Zähler speichert. Die Klasse BinTree bzw. die Knoten müssen den gleichzeitigen Zugriff mehrerer Threads sicher ermöglichen. Methoden für folgende Aufgaben werden benötigt:

Die Klasse Test soll die wichtigsten Normal- und Grenzfälle (nicht interaktiv) überprüfen und die Ergebnisse in allgemein verständlicher Form in der Standardausgabe darstellen. Bitte achten Sie darauf, dass der Test nach kurzer Zeit terminiert. Zumindest die folgenden Überprüfungen sind durchzuführen:

  1. Testen Sie die Klasse BinTree mit mindestens zwei selbstdefinierten Klassen, die ganze Zahlen und Zeichenketten (Strings) darstellen.
  2. Testen Sie die Klasse BinTree mit vier Threads, die Knoten in den Baum einfügen, und gleichzeitig zwei Threads, die Knoten vom Baum entfernen. Jeder Thread soll zumindest 10.000 Einfüge- oder Löschoperationen mit 100 unterschiedlichen Schlüsseln durchführen. Geben Sie für jeden Einfügethread getrennt aus, wie viele Einfügeoperationen ausgeführt wurden und wie oft dabei nur der Zähler erhöht wurde. Geben Sie für jeden Löschthread getrennt aus, wie viele Löschoperationen ausgeführt wurden, wie oft dabei Knoten nicht im Baum enthalten waren und wie oft nur der Zähler erniedrigt wurde.

Wie die Aufgabe zu lösen ist:

Der Schwerpunkt dieser Aufgabe liegt auf korrekter nebenläufiger Programmerierung und der richtigen Verwendung von Synchronisation. Überlegen Sie sich genau, wie und wo Sie Synchronisation verwenden. Halten Sie die Granularität der Synchronisation möglichst klein und achten Sie auf eine effiziente Ausführung. Teilen Sie die Funktionalität für die Zählung der Ereignisse für die Testausgabe sinnvoll auf die einzelnen Klassen auf. Achten Sie weiters auf die richtige Verwendung von gebundener Generizität. Testen Sie Ihre Lösung bitte rechtzeitig auf der g0, da es im Zusammenhang mit Nebenläufigkeit große Unterschiede zwischen den einzelnen Plattformen geben kann.

Hinweise zur Beurteilung:

Der Schwerpunkt bei der Beurteilung liegt auf korrekter nebenläufiger Programmerierung und der richtigen Verwendung von Synchronisation. Kräftige Punkteabzüge gibt es für

Punkteabzüge gibt es, wie bereits üblich, auch für unnötigen (oder unnötig komplexen) Code, mangelhafte Zusicherungen und falsche Sichtbarkeit.

Was im Hinblick auf die Abgabe zu beachten ist:

Schreiben Sie Ihre Lösung in das bereits existierende Verzeichnis Gruppe/Aufgabe8. Das Programm soll von diesem Verzeichnis aus durch java Test aufrufbar sein. Schreiben Sie (abgesehen von geschachtelten Klassen) nicht mehr als eine Klasse in jede Datei. Das Verzeichnis soll zu den Abgabezeitpunkten alle .java-Dateien enthalten, die Sie für Ihre Lösung benötigen. Bitte entfernen Sie alle .java-Dateien, die nicht zur Abgabe gehören. Dateien mit anderen Endungen werden bei der Beurteilung nicht berücksichtigt. Verzichten Sie auf die Verwendung von Verzeichnissen innerhalb von Gruppe/Aufgabe8.
Complang
Puntigam
   Kontakt
   Research
   Lehre
      OOP
      Typsysteme
      EP2
      FOOP
      Prog.spr.
      frühere Lehre
         LVAs 2017 W
         LVAs 2017 S
         LVAs 2016 W
         LVAs 2016 S
         LVAs 2015 W
         LVAs 2015 S
         LVAs 2014 W
         LVAs 2014 S
         LVAs 2013 W
         LVAs 2013 S
         LVAs 2012 W
         LVAs 2012 S
         LVAs 2011 W
         LVAs 2011 S
         LVAs 2010 W
         LVAs 2010 S
         LVAs 2009 W
         LVAs 2009 S
         LVAs 2008 W
         LVAs 2008 S
         LVAs 2007 W
            OOP
               Laborübung
               1. Aufgabe
               2. Aufgabe
               3. Aufgabe
               4. Aufgabe
               5. Aufgabe
               6. Aufgabe
               7. Aufgabe
               8. Aufgabe
            Typsysteme
            Seminar
         LVAs 2007 S
         LVAs 2006 W
         LVAs 2006 S
         LVAs 2005 W
         LVAs 2005 S
         LVAs 2004 W
         LVAs 2004 S
         LVAs 2003 W
   Links
Sitemap
Kontakt
Schnellzugriff:
Laborübung
Tutoren
Skriptum
Folien
Aufgaben
vorige Aufgabe
Fakultät für Informatik
Technische Universität Wien
Anfang | HTML 4.01 | Datenschutzerklärung | letzte Änderung: 2007-12-13 (Puntigam)