Übungsaufgaben
Wintersemester 2006/07
Serie 7
Abgabe bis 7. Feb. 2007
 

Addieren Sie die letzte Ziffer der Immatrikulationsnummern der zwei Mitglieder Ihrer Programmiergruppe. Die Einerstelle des Ergebnisses bestimmt die Aufgabe, die Sie umsetzen sollen.

Aufgabenteil A:
Die einzulesenden Daten können in der main-Methode fest bereitgestellt werden oder von einen File eingelesen werden (3 extra Punkte).
Realisieren Sie die geforderte Aufgabe in einer Methode.
Statistische Auswertungen über die Anzahl von Operationen (Vergleiche, Vertauschungen,...) müssen von der Methode geliefert werden.
Eine Zeitmessung innerhalb Ihrer Methode mittels Methoden aus java.lang.System belegt die benötigte Zeit.

0 und 9

Berechnung eines Formelterms mittels zweier Stacks
Ausgehend von einem vollständig geklammerten Formelterm, der die vier Grundrechenarten angewendet auf integer-Zahlen enthält, werden von links nach rechts ein Operanden- und ein Operatorenstack gefüllt. Beim Erreichen einer schließenden Klammer werden vom Operandenstack der zweite Operand, von Operatorenstack der Operator und vom Operandenstack der erste Operand der Operation entnommen, verknüpft und das Ergebnis (i.A. vom Typ double) auf den Operandenstack zurückgeschrieben. Dann wird in der Abarbeitung fortgesetzt.
Realisieren Sie die Formelabarbeitung unter Nutzung von Modifikationen, der in der Vorlesung angegebenen Stack-Realisierung Stack.java.

1 und 8

Bubble-Sort
Ein String (Feld von char) wird in folgender Art und Weise sortiert: Das erste Feldelement wird mit dem Nächsten solange vertauscht, wie es größer als dieses ist. Ist es kleiner, wird mit dem nächsten Element in gleicher Weise verfahren, bis das Ende der Liste erreicht ist. Danach wird mit dem jetzigen ersten Element von Neuem begonnen bis keine Vertauschungen mehr vorgenommen werden müssen. Realisieren Sie diesen Vertauschungsalgorithmus so, dass Sie wenn möglich nicht immer beim Ersten anfangen und nicht immer bis zum letzten Feldelement testen.
Geben Sie die Anzahl der verschiedenen, gefundenen Feldelemente aus. Vergleichen Sie Ihr Ergebnis dem von Arrays.sort.

2 und 7

Mergesort (Sortieren durch Mischen)
Ein String (Feld von char) wird in folgender Art und Weise sortiert: Das Feld wird in der Mitte geteilt, die Teilketten sortiert und die sortierten Teilketten durch Vergleich der jeweils kleinsten Elementes wieder zusammengeführt. Die Sortierung der Teilketten geschieht nach den gleichen Muster (also rekursiv) bis eine Listenlänge von eins erreicht ist.
Geben Sie die Anzahl der verschiedenen, gefundenen Feldelemente aus. Vergleichen Sie Ihr Ergebnis dem von Arrays.sort.

3 und 6

Quick-Sort
Ein String (Feld von char) wird in folgender Art und Weise sortiert: Das erste Feldelement wird als Pivotelement benutzt. Das Feld wird in Elemente, die kleiner gleich dem Pivotelement und größer dem Pivotelement sind, unterteilt. Beide Teillisten werden sortiert und wieder zusammengefügt (Liste mit kleineren Elementen, dann Liste mit größeren Elementen). Die Teillisten werden in der gleichen Art und Weise (also rekursiv) sortiert.
Geben Sie die Anzahl der verschiedenen, gefundenen Feldelemente aus. Vergleichen Sie Ihr Ergebnis dem von Arrays.sort.

4 und 5

Suchen und Ersetzen
Daten sind ein String (Feld von char). Ersetzen Sie gleichzeitig mehrere Zeichen in diesem String durch andere Zeichenketten. Beachten Sie dabei, dass eventuell Zeichen zu ersetzen sind, die auf dem benutzten Computer nicht darstellbar sind.

Bewertung: 7 Punkte + 3 Punkte

Aufgabenteil B:
Erstellen Sie eine ausführliche Beschreibung mittels Latex. Erläutern Sie darin die Arbeitsweise (Theorie), Implementierung und Nutzung der Methode. Geben Sie Beispiele an und  werten Sie Ihre Beobachtungen aus (Eingangsdaten, Ergebnisse, Aufwand, Grenzen).

Bewertung: 7 Punkte

 

Beachten Sie folgende Punkte:

1. Kommentieren Sie Ihr Programm und auch das Latex-File (Authoren, Aufgabenserie).
2. Legen Sie Ihren Latextext als .tex-File und .pdf-File in Ihrem P-WRI-Ordner ab.
3. Beachten Sie, dass die Forderungen an das Java-File weiterhin gelten.
4. Legen Sie die geforderen Files termingerecht und entsprechend den Vorgaben (siehe WRI-Homepage) ab.