Einführung Algorithmen und Datenstrukturen

exemplarische Lösung der Aufgaben WS 02/03 von Markus Durzinsky. Zurück zur Algodat Hauptseite.

10. Übungsblatt

Aufgabe 46 - Matrix Multiplikation

Das Multiplizieren zweier Matrizen ist eigentlich ganz einfach:

Matrixmultiplikation
Als erstes benötigt man aber eine Klasse zum Speichern der Matrix. Am effektiefsten geschieht dies in einem zweidimensionalen Feld:


class Matrix {

  protected double[][] a;

  public Matrix(int width, int height) {
    this(new double[height][width]);
  }

  public Matrix(double[][] values) {
    a = values;
  }

  public double getValueAt(int x, int y) {
    return a[y][x];  // throws ArrayIndexOutOfBoundsException
  }

  public void setValueAt(int x, int y, double v) {
    a[y][x] = v;
  }

  public int getWidth() {  return a[0].length; }

  public int getHeight() {  return a.length; }

}

Persönlich halte ich nicht viel von statischen Methoden, an die man zwei Instanzen der zu berechnenden Daten übergibt. Solche statischen Methoden sollte man nur verwenden, wenn die Berechnung wirklich nur auf der Klasse basiert und unabhängig von einer Instanz durchgeführt werden kann. Hier also die Instanzmethode nach der anfangs angegebenen Formel. Dabei ist das Ergebnis eine Matrix mit der Höhe der ersten und der Breite der zweiten Matrix. Ist die Breite der ersten nicht gleich der Höhe der zweiten, kann man die Matrizen nicht multiplizieren.


  public Matrix multiply(Matrix m) {
    if (getWidth() != m.getHeight())
      throw new IllegalArgumentException("matrix inner dimension must aggree");
    Matrix x = new Matrix(m.getWidth(), getHeight());
    for (int i = 0;  i < getHeight();  i++)
      for (int j = 0;  j < m.getWidth();  j++) {
        x.a[i][j] = 0.0;
        for (int k = 0;  k < getWidth();  k++)
          x.a[i][j] += a[i][k] * m.a[k][j];
      }
    return x;
  }

Zum testen der Methode sollte man so eine Matrix auch ausgaben können:


  public String toString() {
    String s = "";
    for (int y = 0;  y < getHeight();  y++) {
      s += "[ ";
      for (int x = 0;  x < getWidth();  x++)  s += a[y][x];
      s += "]\n";
    }
    return s;
  }

Als einfaches Beispiel erweitert man die Klasse noch um eine main Methode:


  public static void main(String[] args) {
    Matrix m1 = new Matrix(new double[][]{{1,2},{2,3},{3,4}});
    Matrix m2 = new Matrix(new double[][]{{1,2,3},{2,3,4}});
    System.out.println(m1.multiply(m2));
    System.out.println(m1.multiply(m1));
  }

Wenn alles klappt, erscheint diese Ausgabe auf dem Monitor:


  [ 5.0 8.0 11.0 ]
  [ 8.0 13.0 18.0 ]
  [ 11.0 18.0 25.0 ]

  java.lang.IllegalArgumentException: matrix inner dimension must aggree

Aufgabe 47 - obere Dreiecksmatrix

  1. Als erstes muss eine solche Matrix quadratisch sein. Dann müssen alle Elemente unterhalt der ersten Hauptdiagonale den Wert 0 haben.
    
      public static boolean dreieck(Matrix m) {
        if (m.getWidth() != m.getHeight())  return false;
          for ( int x = 0;  x < m.getWidth() - 1;  x++)
            for ( int y = x + 1;  y < m.getHeight();  y++)
              if (m.getValueAt(x, y) != 0.0)  return false;
        return true;
      }
  2. Als Testrahmen wird die main Methode aus Aufgabe 46 erweitert:
    
      public static void main(String[] args) {
        // ...
        Matrix m3 = new Matrix(new double[][]{{1,2,3},{0,4,5},{0,0,6}});
        System.out.println("m1*m2 ist "+(dreieck(m1.multiply(m2))?"eine":"keine")
          +" Dreiecksmatrix");
        System.out.println("m3 ist "+(dreieck(m3)?"eine":"keine")+" Dreiecksmatrix");
      }
    Die Ausgabe:
    
      m1*m2 ist keine Dreiecksmatrix
      m3 ist eine Dreiecksmatrix

Aufgabe 48 - binäre Bäume

  1. Schwere Aufgabe: wie zeichnet man einen Baum.
    Tree
  2. Da der Baum nicht regulär sein muss, ist der Extremfall eine einfache Liste. Das letzte Element der Liste ist das einzige Blatt im Baum. Die minimale Anzahl von Blättern ist unabhängig von h immer 1.
  3. Der andere Extremfall, der eines vollständig ausgeglichenen Baumes, ist in der Abbildung oben zu sehen. Auf jeder Ebene k befinden sich 2k Knoten. Der Baum hat also bei einer Höhe von h maximal 2h äussere Knoten.
  1. Bei einem vollständig ausgeglichenen und aufgefüllten Baum der Höhe h befinden sich in jeder Ebene k genau 2k Knoten. Insgesamt macht das n = 2h+1 - 1. Umgestellt nach der Höhe: log2(n + 1) - 1 = h. Ist der Baum nicht ausgeglichen wird das n kleiner oder h grösser. Also gilt allgemein log2(n + 1) - 1 <= h.

    Betrachten wir den anderen Extremfall (der Baum ist immer noch nicht regulär): Der leere Baum (mit der Höhe 0 enthält genau einen Knoten, die Wurzel (0 = h = n - 1).Fügt man ganz links einen Knoten ein erhöht sich sowohl die Höhe als auch die Knotenanzahl um eins. Induktiv erhält man die Behauptung h = n - 1. Ist der Baum T nicht ganz so unausgeglichen bekommt man bei gleicher Höge mehr Knoten unter. Also gilt h <= n - 1.

  1. Die Betrachtung bei Punkt e. ergibt die Doppelungleichung log2(n + 1) - 1 <= h <= n - 1.

Aufgabe 49 - binary tree node

In der Aufgabenstellung wurde ja schon alles gesagt:


  class TreeNode {

    private TreeNode left, right;
    private Comparable data;

    public TreeNode(TreeNode l, TreeNode r, Comparable d) {
      left = l;  right = r;  data = d;
    }

    public TreeNode getLeft() { return left; }
    public TreeNode getRight() { return right; }
    public Comparable getData() { return data; }

    public void setLeft(TreeNode l) { left = l; }
    public void setRight(TreeNode r) { right = r; }
    public void setData(Comparable d) { data = d; }

  }

Aufgabe 50 - tree node

Warum nennen wir einen binären Suchbaum nicht einfach genau so? Also hier eine kleine Umbenennung von LinkedBinaryTree nach BinarySearchTree. Die Struktur der Klasse ist diese:


public class BinarySearchTree {
  private BinaryTreeNode root = null;
  public BinarySearchTree() {}
}

Es gibt keinen Grund eine Eigenschaft nicht gleich mit einem Anfangswert zu belegen, weshalb dann der Konstruktor nichts mehr zu tun hat. Man könnte ihn also auch weglassen, weil dann der parameterlose Konstruktor automatisch deklariert wird.

Um nun ein neues Element einzufügen, muss erst einmal die richtige Stelle gefunden werden. Die Suche beginnt bei root, ist das einzufügende Element kleiner, wird links weitergesucht, ist es grösser, geht es rechts weiter. Ist das Element gleich (schon im Baum vorhanden), wird kein neuer Knoten erstellt, sondern dieser Knoten zurückgeliefert. An sonsten wird solange gesucht, bis man bei null angekommen ist. Dann wird ein neuer Knoten erstellt und (je nach grösse des Elements) links oder rechts am vorherigen Knoten eingefügt. Dazu muss natürlich während der Suche auch der Vorgängerknoten (prev) gespeichert werden.

Ein weiterer Spezialfall ist das Einfügen in einen leeren Baum. Dann wird der neue Knoten nicht hinter prev eingehangen, sondern direkt bei root.


  public BinaryTreeNode insertElement(Comparable c) {
    BinaryTreeNode runner = root, prev = root;
    // Suche ein Blatt zum Einfügen
    while (runner != null) {
      int i = c.compareTo(runner.getData());
      prev = runner;
      if (i == 0) {
        // Element schon vorhanden
        return runner;
      }
      runner = (i < 0) ? runner.getLeft() : runner.getRight();
    }
    runner = new BinaryTreeNode(null, null, c);
    // neuen Knoten erstellen
    if (root == null) {
      root = runner;
    } else if (c.compareTo(prev.getData()) < 0) {
      prev.setLeft(runner);
    } else {
      prev.setRight(runner);
    }
    return runner;
  }

Ein kleines Applet zur Funktionsweise von binären Suchbäumen gibt es hier.


Erstellt von Markus Durzinsky, aktualisiert 08. März 2003
Für Fragen, Probleme oder Anregungen stehe ich gerne zur Verfügung