UE Algorithmen 2 - Uebung 3

Übungen zu Algorithmen und Datenstrukturen 2 WS 98/99

3. Übung - abzugeben am 27. 10. 1998 in Ihrer Übungsgruppe

3.a.1 Theorie

Leiten Sie die Adressierungsformel für ein nicht-zentriertes Array mit Dimension 4 aus der allgemeinen Adressierungsformel her.

3.a.2 Theorie

Erklärung Sie an Hand von Beispielen/Zeichungen etc., welche Werte in einem Dope-Vektor abgespeichert werden.

3.b Programm

Schreiben Sie ein Programm gemäß folgender Interface Definition:

DEFINITION OF MODULE Matrix;
  CONST DIM*=....; (* Dimension hier zentral festgelegt *)
  TYPE  Index*=ARRAY DIM OF INTEGER;
        Element*=INTEGER;

  PROCEDURE Init*(loBnd,upBnd:Index; VAR err:BOOLEAN);
  PROCEDURE CleanUp*();
  PROCEDURE Get*(inx:Index; VAR ele:Element);
  PROCEDURE Put*(inx:Index; ele:Element);
  PROCEDURE Find*(VAR outx:Index; VAR found:BOOLEAN; ele:Element);
END Matrix.

Anmerkungen:

Besprechung der geforderten Funktionen erfolgt in der Übung
Sicherheitsabfragen nicht vergessen
Adressierung intern mittels Dope-Vektor, zeilenweise Adressierung
Testtreiber soll jeweils einen vollständigen Test für die angelegte Matrix ausführen
Versuchen Sie, die Matrixadressierung und das Suchen in der Matrix (Find) möglichst effizient zu implementieren.

3.c Programm

Überlegen Sie sich eine Lösung zur speicherplatzeffizienten Verwaltung eines großen mehrdimensionalen Arrays, dessen Basiselemente vom Typ BOOLEAN sind.
Tip: Überlegen Sie für die Komprimierung den Einsatz von SET, damit ein boolscher Wert auch wirklich nur 1 Bit benötigt.

DEFINITION OF MODULE BinMat;
  CONST DIM*=5;
  TYPE Index*=ARRAY DIM OF LONGINT;

  PROCEDURE Init*(loBnd,upBnd:Index; VAR err:BOOLEAN);
  PROCEDURE CleanUp*();
  PROCEDURE Get*(inx:Index):BOOLEAN;
  PROCEDURE Put*(inx:Index; ele:BOOLEAN);
END BinMat.

3.d.1 Diskussion

Überlegen Sie, wie Sie mit (älteren) Compilern auf PCs, die nur Arrays von maximal 64 KB adressieren können, auch größere Arrays selber verwalten können.

3.d.2 Diskussion

Überlegen Sie, wie die Adressierungsformel für Dreiecksmatrizen der angegebenen Form zu gestalten ist, damit die maximale Ausdehnung der Matrix nicht mit in die Adressierungsformel eingeht.

 +--------> j
 | ******
 |  *****
 |   ****
 |    ***
 |     **
 V      *
 i

Frage: Was bedeutet diese Forderung für die Erweiterbarkeit der Matrix?

Last modified: hoermanseder@fim.uni-linz.ac.at 98-10-19