CoMa

Computerorientierte Mathematik

TU logo

Inhalt
.

Institut
 .  Vorlesungen
 .  .  CoMa
 .  .  .  ehemalige Zyklen
 .  .  .  .  CoMaII SS02
 .  .  .  .  .  Literatur
 .  .  .  .  .  Programmierregeln
 .  .  .  .  .  Mailarchiv
 .  .  .  .  . Programm 1&2
 .  .  .  .  .  Programm 3
 .  .  .  .  .  Programm 7

back zurück

Computerorientierte Mathematik II (WS00/01)
- 1. und 2. Programmieraufgabe -

Version Stand 03. Mai 2002. Änderungen gegenüber älteren Versionen sind rot gekennzeichnet.

Aufgrund des doch sehr grossen Umfangs haben wir uns entschlossen, die ersten beiden Programmieraufgaben etwas umzuformulieren und die Abgabefristen entsprechend zu verlängern.

Der erste Teil (Programm 1) ist bis Montag, den 06.Mai 2002 vorzuführen.
Der zweite Teil (Programm 2) ist bis Montag, den 13.Mai 2002 vorzuführen.


Erster Teil (Programm 1)

Alle, die die bisherige Aufgabe noch nicht abgegeben haben halten sich bitte an die folgende Aufgabe. Alle anderen müssten jedoch für die zweite Aufgabe jedoch einige Schritte des Folgenden nachholen.

Vorbereitungen

Georg hatte bereits einige Emails herumgeschickt mit ein paar Einstellungen, die ihr in eurem Account machen solltet. Hier nochmal die Zusammenfassung:

In Java gibt es das Konzept der Packages, um etwas mehr Klarheit in dem Programmtext zu schaffen. Damit ihr auch etwas davon habt muss aber noch etwas getan werden:

  • legt ein Unterverzeichnis classes in eurem home an: mkdir ~/classes
  • legt ein Unterverzeichnis packages in eurem home an: mkdir ~/packages
  • desweiteren müsst ihr noch eure C-Shell Resourcedatei ändern. Fügt in der Datei .cshrc (den Punkt nicht vergesse!) folgende Zeilen hinten an:

    setenv CLASSPATH /homes/co2/co2-???/classes:.
    alias jikes jikes -classpath /usr/java130/jre/lib/rt.jar:/homes/co2/co2-???/classes:.

    Die drei Fragezeichen ??? sind durch eure Gruppennummer zu ersetzen.

    Die erste Zeile ist für den Javacompiler javac von Sun und die zweite für jikes von IBM, falls ihr an einem AIX Rechner sitzt.

    Wenn ihr euch demnächst anmeldet werden diese Änderungen sofort akitv sein. Wenn ihr sie aber schon jetzt in einem xterm benötigt, so müsst ihr noch

    source ~/.cshrc

    als Befehl in d i e s e m xterm eingeben.
  • Wenn immer ihr ein Package in der nächsten Zeit benötigt, so kopiert ihr es in das Verzeichnis ~/packages/<Packagename>. Also im Falle der CoMa Container Classes in ~/packages/ccc.

    Um das Package zu übersetzen gebt ihr den Befehl

    javac -d ~/classes ~/packages/<Packagename>/*.java

    oder

    jikes -d ~/classes ~/packages/<Packagename>/*.java

    ein. Danach müsste in dem Verzeich ~/classes ein Unterverzeichnis mit dem Packagenamen existieren. In diesem Verzeichnis sollten dann *.class Dateien sein.

    Also wieder im Falle der CoMa Container Classes

    javac -d ~/classes ~/packages/ccc/*.java
  • Jetzt könnt ihr einfach den Import Befehl z.B.

    import ccc.*;

    so benutzen als würdet ihr ein Systempackage einladen wollen.

Packages

Kopiert zunächst die Packages in euren Bereich:

cp -r ~co2-001/packages ~/

und übersetzt diese:

javac -d ~/classes ~/packages/*/*.java ~/packages/*/*/*.java

Wenn ihr wollt, kopiert euch auch die Doku dazu:

cp -r ~co2-001/doc ~/

Oberfläche

Ihr braucht keine eigene Oberfläche schreiben, wir geben Euch eine vor. Kopiert dazu zunächst die Dateien ContainerApplication.java und ContainerUtilities.java in euer Verzeichnis ~/programm1/.

Falls ihr die Version vor dem 03. Mai kopiert habt, kommentiert in der ContainerAppplication bitte zunächst die Zeile 370 aus:

	    iterator = new ConstForwardFilterIterator(iterator, p);
    

In der späteren Version braucht das nicht getan werden, da dort noch mehr Klassen dynamisch (zur Laufzeit) geladen werden.

Auf alle Fälle müsst ihr aber in ContainerUtilities alle ... auskommentieren. Diese Dateien könnt ihr nun schon mal compilieren, das sollte ohne Fehler gehen.

Aufgabe

Nun schreibt ihr Eure Listen-Klasse (plus Iterator), z.B. im selben Verzeichnis. Implementiert dazu die Schnittstellen ccc.DynamicPermutableContainer und ccc.list.UnsortedList. Der Iterator implementiert ccc.Iterator.

Schreibt nun folgende Comparatoren (implements java.utilComparator):

  • java.lang.Integer aufsteigend sortieren.
  • java.lang.Integer absteigend sortieren.
  • java.lang.String aufsteigend sortieren, Gross/Kleinschreibung unterscheiden.
  • java.lang.String absteigend sortieren, Gross/Kleinschreibung unterscheiden.
  • java.lang.String aufsteigend sortieren, Gross/Kleinschreibung nicht unterscheiden.
  • java.lang.String absteigend sortieren, Gross/Kleinschreibung nicht unterscheiden.

Die Comparatoren sollen jeweils eine ClassCastException werfen, wenn die ""ubergebenen Objekte keine Integer- bzw. String-Objekte sind. Ein einfacher StringComparator könnte wie folgt aussehen: StringComparator.java

Nun könnt ihr mit Hilfe der Comparatoren den MergeSort-Algorithmus schreiben. Dieser soll das Interface ccc.util.SortAlgorithm implementieren. Laut diesem Interface bekommt die Methode sort einen Container von Typ ccc.ConstForwardContainer übergeben. Dies wird eurem Algorithmus jedoch nicht reichen. Deshalb müsst ihr den Container zu einemgeeigneten Container hoch-casten. Sollte das jedoch nicht gehen, so werft eine ccc.util.WrongSortTypeException. Das gleiche solltet ihr werfen, wenn der Comparator eine Exception wirft.

Zum einfachen Testen von eurem MergeSort schreibt eine main-Methode, die z.B. eine einzugebene Anzahl von Integer-Zahlen sortiert.

Nun sollt ihr noch BucketSort für Listen von Strings schreiben. Dieser Algorithmus soll auch wieder ccc.util.SortAlgorithm implementieren. Den übergebenen Container castet ihr gleich zu einer Liste.

Ihr werdet sicherlich mit der charAt()-Methode von String arbeiten. Diese Methode liefert ein char zurück, mit dem man rechnen kann wie mit int's. Die Werte reichen dabei von 0 bis 65535(?). Das sind natürlich für unsere Zwecke viel zu viele. Deshalb könnt ihr voraussetzen, in den Strings sollen nur 'a'-'z' und 'A'-'Z' stehen.

Ein Beispiel:

	      String s = "Hallo";
	      char c=s.charAt(0);
	      int i = (int)(c- `A`);    // i hat Wert 7
	      char d = s.charAt(1);
              int j= (int)(d-'a'); // j hat Wert 0
    

Hinweis: es gilt 'A'<'B'='A'+1<...<'Z'='Y'+1<'a'='Z'+??<'b'='a'+1<....
Somit habt ihr nur geeignet 52 Buckets zu verwalten. Wenn ein anderes Zeichen im String ist, werft eine ccc.util.WrongSortTypeException.

ContainerApplication

Wenn ihr nun alles übersetzt habt (javac *.java), dann könnt ihr euren code testen, indem ihr
     java ContainerApplication DoubleLinkedList ccc.array.ConstContainerArray 
          -s MergeSort ccc.util.QuickSort ccc.util.SelectionSort 
          -o StringComparator StringUpperComparator StringBackComparator StringBackUpperComparator
    
(alles in einer Zeile, Namen der Klassen evtl. anpassen) eintippt. All die Klassen, die ihr angebt, werden dann dynamisch eingebunden und sind in der Application verwendbar.

Ihr könnt zusätzlich die Option -e angeben, dann werden evtl. Exceptions auf der Console ausgegeben, was das Debuggen eures Codes erleichtert. Bedenkt, dass alle Exceptions, die auftreten entweder an eurem Programm-Code oder an Inkompatibilitäten der Klassen und Algorithmen liegt.

Zweiter Teil (Programm 2)

Wenn ihr Aufgabe 1 wie oben beschrieben erledigt habt, könnt ihr direkt weiter machen, so wie auf dem Aufgabenblatt.

ContainerUtilities

Wir haben euch für die Klasse ContainerUtilities oben schon ein Gerüst gegeben, dass ihr nur noch auffüllen müsst. Behaltet unbedingt den Namen der Klasse und ihrer Methoden bei, damit die Application weiter funktioniert.

gefilterte Iteratoren

Oftmals ist man nicht daran interessiert, etwas mit allen Elementen eines Containers zu machen, sondern nur mit einigen bestimmten. Um sich die Auswahl der Elemente zu erleichtern, schreibt man dann einen sogenannten FilterIterator, der in geeigneter Weise die Eigenschaften der gesuchten Elemente kennt (ein sogenanntes Prädikat), und dann nur auf solchen Elementen stehen bleibt, die dieses Prädikat erfüllen.

Um sich dabei Arbeit zu sparen, schreibt man einfach eine sogenannte Iterator-Wrapper-Klasse (to wrap = engl. umhüllen), die einen beliebigen Iterator und ein Prädikat erhält. Wenn man nun vorwärts gehen will, so bewegt diese Wrapper-Klasse den eigentlichen Iterator so lange vorwärts, bis er auf einem Element steht, das das Prädikat erfüllt.

Schreibt zunächst eine Klasse UpperCasePredicate oder so, die das Interface ccc.compare.Predicate implementiert, und deren hasProperty-Methode genau dann true zurück liefert, wenn das übergebene Objekt ein String ist und mit einem Grossbuchstaben anfängt. Die equals-Methode soll genau dann true zurückgeben, wenn das übergebene Objekt wieder ein UpperCasePredicate ist. Wenn ihr wollt schreibt noch weitere Prädikate für Strings (alle Buchstaben gross, alle klein, alle Zeichen wirklich Buchstaben, ...).

Schreibt nun eine Klasse ConstForwardFilterIterator als Wrapper-Klasse für beliebeige ConstForwardIteratoren, die ein beliebiges ccc.compare.Predicate verwendet. Achtet genau auf die richtige Funktionsweise des Constructors sowie von clone() isAtEnd() increment() equals() und getData(). Der Konstruktor könnte z.B. so aussehen:

    /**
     * Constructor.
     * Constructs a wrapper for a given Iterator with a given filter.
     */
    ConstForwardFilterIterator (ConstForwardIterator iter, Predicate filt){
	it = iter; 
	filter = filt;
	
	if ((! it.isAtEnd()) && ! filter.hasProperty(it.getData()))
	    increment();
    }
    

Ausserdem soll euer Filteriterator auch das Interface ccc.wrap.IteratorWrapper erfüllen.

Testen

In der älteren Version der Test-Applikation: Entfernt zunächst die oben eingefügten Kommentare aus Zeile 370 in der ContainerApplication. Compiliert sie neu.

Nun könnt ihr die Anwendung wie oben ausführen, gebt aber als zusätzliche Parameter an:

      -i ConstForwardFilterIterator -f UpperCasePredicate
    

Zur Erinnerung

Bekanntlich kann man in einem kurzen Programm (Methode) weniger Fehler machen als in einem langen. Ersetzt nicht einen Fehler durch ständiges hinzufügen von weiten Zeilen durch zehn Fehler.

Vergesst die javadoc-Dokumentierung nicht!

top top
zuletzt bearbeitet: Tue May 28 2002, zuletzt erstellt: Tue Sep 8 2009
Andreas Fest <fest@math.tu-berlin.de>
Validate HTML