To: co2@fb3-s7.math.TU-Berlin.DE
Subject: Anmerkungen zum 2. Uebungsblatt
From: Olaf Jahn <jahno@math.TU-Berlin.DE>
Date: 04 May 1999 13:31:08 +0200

Liebe CoMas, 

da es anscheinend ein paar Schwierigkeiten mit dem zweiten Übungsblatt
und insbesondere der zweiten Programmieraufgabe gibt, hier ein paar
Hinweise:

Zu 5.

In der 5. theoretischen Aufgabe ist es natürlich nicht gestattet, zum
Addieren zweier Matrizen sie (oder eine von beiden) in die
herkömmliche Form als Array von Arrays zu konvertieren. Die
Implementation als dünnbesetzte Matrizen ist doch extra dafür da, um
unnötigen Speicherbedarf zu vermeiden. Dies würde durch "echte"
Matrizen beim Addieren ad absurdum geführt. Für die ganz Hartnäckigen
unter Euch: Was wäre, wenn beide Matrizen nur bei (1, 1) einen Wert
ungleich Null haben und bei (100000, 100000)?  

Wer beim Addieren etwa zeilenweise vorgeht (von unten angefangen ist
eine gute Idee) wird finden, daß es so ähnlich ist wie das Mergen
zweier Listen bei Mergesort.


Zu 6.

In der sechsten Aufgabe beziehen die die
Laufzeitangaben/-forderungen auf den Worst case. Irgendwelche
komplizierten Berechnungen mit Wahrscheinlichkeiten brauchen also
nicht angestellt zu werden. Es ist üblich, immer den Worst case zu
meinen, wenn man nichts Gegenteiliges hinschreibt.


Zur 2. Programmieraufgabe

Für einige von Euch scheint die Vielzahl von Verkettungen und
Referenzen etwas verwirrend zu sein. Ich habe deshalb für einen sehr
einfachen Graph einmal ein komplettes Diagramm aller beteiligten
Klassen/Instanzen gemalt und auf die CoMa-Web-Seite gestellt (die
Klassen- und Variablennamen können bei Euch natürlich unterschiedlich
sein).

Dank der Kapselung der Listenfunktionen in eine eigene Klasse, die man
nur noch benutzen braucht, ist das Programmieren jedoch nicht so
kompliziert wie es das Bild auf den ersten Blick erscheinen läßt.  Wer
eine funktionierende Listenklasse hat, braucht nur noch dafür zu
sorgen, daß die Graphknoten in den richtigen Listen stehen.

Bitte beachtet insbesondere, daß es zwei Typen von "Knoten" gibt.
Einmal Knoten der Liste (ListNodes) und dann Knoten des Graphen
(Nodes), die ersteinmal überhaupt nichts miteinander zu tun haben.
Wichtig ist jedoch, daß Ihr die Knoten des Graphen in Listen speichern
sollt, was bedeutet, daß sie als Object-Referenzen in den ListNodes
der entsprechenden Listen auftauchen.

Jeder Knoten kann also in mehreren Listen stehen:
1. Immer in der "globalen" Knotenliste des Graphen
2. In keiner oder mehreren Adjazenzlisten anderer Knoten.

Obwohl Ihr für beide Typen von Listen die gleiche Listenklasse
verwenden könnt, müssen nur die Knoten der "globalen" Liste jemals
sortiert werden. Für Adjazenzlisten wird die Sortierfunktion der
SortableListWithPointer einfach nicht benutzt.

Viel Spaß wünscht Euch
  Olaf

P.S. Als Ermutigung: Das nächste Aufgabenblatt ist nicht soooo schwer.

-- 
Olaf Jahn                                      jahno@math.tu-berlin.de
                                   http://www.math.tu-berlin.de/~jahno 
                                  PGP public key available on request.