Sortieralgorithmen 

Zum Kapitel Sortieralgorithm habe ich ein Messprogramm geschrieben, welches die Anzahl der Vergleiche und die Anzahl der Datensatzbewegung mißt, die die unterschiedlichen Sortieralgorithmen im Schnitt benötigen um eine gegebene Permutation zu sortieren. Das Programm samt Beschreibung und einiger Messdaten finden Sie hier (englisch).

Lösungen der Übungen 

Hier finden sich einige meiner Lösungen zum Tutorium Einführung in die Informatik 1 (Dr. Jan Vahrenhold, Universität Siegen Wintersemester 2002/03):

Aufgabe 25: Entwerfen und implementieren Sie eine Klasse Bruch zur Darstellung und Verarbeitung von Dezimalbrüchen. Alle numerischen Werte sollen vom Typ int sein.

1. Realisieren Sie Konstruktoren nach folgenden Vorgaben:
   • Der default-Konstruktor soll einen Bruch ergeben, der den Wert 1 repräsentiert.
   • Der Aufruf eines Konstruktors mit einem ganzzahligen Argument x soll einen Bruch ergeben, der den Wert x repräsentiert.
   • Der Aufruf eines Konstruktors mit zwei ganzzahligen Argumenten x und y soll einen Bruch ergeben, der den Wert x/y repräsentiert.
2. Realisieren Sie Methoden zum Zugriff auf die Attribute (welche Attribute hat Ihre Klasse?).
3. Realisieren Sie Methoden zur Addition, Subtraktion, Multiplikation und Division nach der "Schulmethode". Beispiel zur Notation: Die Methode addiere eines Bruchobjektes B1 soll als Argument eine Referenz auf ein weiteres Bruchobjekt B2 erwarten und eine Referenz auf ein neues Bruchobjekt B3 zurückliefern. Das Bruchobjekt B3 soll hierbei den Bruch B1 + B2 repräsentieren.
4. Realisieren Sie eine Methode zum Kürzen eines Bruches. Diese Methode soll das aktuelle Objekt ggfs. so modifizieren, daß Zähler und Nenner teilerfremd sind. Verwenden Sie diese Methode, um sicher zu stellen, dass alle Brüche nach jeder arithmetrischen Operation bzw. nach ihrer Konstruktion gekürzt sind.

Aufgabe 24: Betrachten Sie die folgende Funktionsdefinition:

	                        / y + 1            falls x = y
	f: Z x Z -> Z, (x,y) -> |
	                        \ f(x,f(x-1,y+1))  sonst.
					

Hierbei sei Z die Menge der ganzen Zahlen. Bearbeiten Sie nun die folgenden Aufgaben:

1. Implementieren Sie die Funktion in Java, verwenden Sie hierbei den Datentyp int zur Modellierung der Menge Z.
2. Untersuchen Sie das Terminierungsverhalten der Funktion f in Abhängigkeit von x und y. Gehen Sie hierbei wie folgt vor:
   • Testen Sie (von Hand oder mit Hilfe Ihrer Implementierung), welcher der folgenden Aufrufe terminiert.

     f(1,1), f(1,2), f(2,1), f(1,3), f(3,1), f(4,8), f(8,2), f(9,1)

   • Geben Sie an, welcher Wert im Falle der Terminierung zurück geliefert wird.
   • Stellen Sie anhand dieser Beobachtungen eine Vermutung auf, und versuchen Sie, diese durch geschickte Argumentation zu begründen.

Aufgabe 23: Modifizieren Sie die Methoden der Beispiel-Klasse Rekursion so, daß (wie auf den Folien) die einzelnen Stufen der Rekurstion eingerückt auf dem Bildschirm erscheinen. Kommentieren und testen Sie Ihre Lösung. Aufgabe23.java

Aufgabe 22: Gegeben sei eine Matrix a der Form double[][]. Wenn a eine n*n Matrix ist, extrahieren Sie aus a die obere Dreiecksmatrix d (mit Hauptdiagonalen) und liefern Sie eine Referenz auf d zurück. Aufgabe22.java

Aufgabe 21: Erzeugen Sie mit den beiden Arrays aus Aufgabe 20) eine dritte Matrix c, die komponentenweise das Maximum von a und b speichert. Aufgabe21.java

Aufgabe 20: Gegeben seien zwei Referenzen a und b, die auf Arrays der Form double[][] verweisen. Überprüfen Sie auf zwei Arten, ob beide Arrays gültige n*m Matrizen sind:

• Die Matrix wird durchlaufen, um n und m zu bestimmen
• n und m werden vorgegeben.

Hinweis: Beide Möglichkeiten benötigen eine Methode boolean is_nKreuzm_Matrix(double[][] a, int n, int m) die testet, ob a eine n*m Matrix ist. Aufgabe20.java

Aufgabe 19d: (Herausfordernd:) Lösen Sie die vorige Teilaufgabe erneut, ohne dabei jedoch Arrays oder mehrfache Fallunterscheidungen zur Überprüfung der Parameter zu verwenden! Aufgabe19d.java

Aufgabe 19c: Realisieren Sie die Methode tagImJahr in Java. Überprüfen Sie hierbei, ob alle übergebenen Parameter Sinn ergeben. Wenn mindestens einer der Parameter keinen Sinn ergibt, soll eine Fehlermeldung auf dem Bildschirm ausgegeben werden und anschließend soll der Wert 0 zurück gegeben werden. Aufgabe19c.java

Aufgabe 19b: Realisieren Sie die Methode tagImJahr in Java. Sie dürfen hierbei keine Arrays verwenden. Gehen Sie ferner davon aus, daß alle übergenen Parameter Sinn ergeben. Aufgabe19b.java

Aufgabe 19a: Realisieren Sie die Methode tagImJahr in Java. Sie dürfen hierbei Arrays verwenden. Gehen Sie ferner davon aus, daß alle übergenen Parameter Sinn ergeben. Aufgabe19a.java

Related links

• Vorlesung "Einführung in die Informatik 1"
• sortchk - a sorting algorithm test suite