Praktikum Algorithmische Anwendungen

Wintersemester 2003/04

Praktikum 4

 

Gruppe AI A1
Michael Boiman 11027800 ai320
M. Serhat Çinar 11030409 ai440
Mustafa Ekit 11027589 ai336

 

Index

  • Projekt 4: Matrix-Kettenmultiplikation als Beispiel für dynamisches Programmieren
  • Aufgabe 1: Matrix-Kettenmultiplikation step by step
  • Aufgabe 2: Implementierung
  • Dateien und Javadoc
  •  


    Projekt 4: Matrix-Kettenmultiplikation als Beispiel für dynamisches Programmieren     top

    Zuerst wurde erneut eine Aufteilung der Aufgaben erstellt:
    Michael Boiman: Implementierung der Methode matrix-chain-order
    Mustafa Ekit: Implementierung & Dokumentation der Methode print-optimal-parens, Dokumentation Aufgabe 1
    M. Serhat Cinar: Erstellung der GUI, Dokumentation Laufzeit, Projektmanagement

    Als nächstes wurde gemeinsam das Interface IChainMultiplicationOptimizer.java definiert.

    MSC

     


    Aufgabe 1: Matrix-Kettenmultiplikation step by step     top

    "Gegeben ist die Matrix-Kette <A1, A2, A3, A4> mit dem Dimensions-Vektor p = (p0, p1, p2, p3, p4) = (5, 3, 4, 2, 20)."

    a) Schreiben Sie alle Klammerungen der Matrix-Kette <A1, A2, A3, A4> auf, und prüfen Sie die Anzahl der Klammerungen durch Evaluation der Rekursionsgleichung (11) (siehe Skript Folie 3.2/12)

    Mögliche Klammerungen:

    ((A1*A2)*A3)*A4
    (A1*(A2*A3))*A4
    A1*((A2*A3)*A4)
    A1*(A2*(A3*A4))
    (A1*A2)*(A3*A4)
    
    Berechnung nach der Rekursionsgleichung zur Berechnung der verschiedenen möglichen Klammerungen.
    P(4) = SUM[k=1 to 3]( P(k) * P(4-k) ) = P(1) * P(3) + P(2) * P(2) + P(3) * P(1)
    P(3) = SUM[k=1 to 2]( P(k) * P(3-k) ) = P(1) * P(2) + P(2) * P(1)
    P(2) = SUM[k=1 to 1]( P(k) * P(2-k) ) = P(1) * P(1)
    P(1) = 1
     =>
    P(2) = 1 * 1 = 1
    P(3) = 1 + 1 = 2
    P(4) = 2 + 1 + 2 = 5
    
    Es existieren nach der Rekursionsgliechung 5 mögliche Klammerungen.

    b) Markieren Sie in jeder Klammerung den Splittpunkt der letzten Multiplikation.

    ((A1*A2)*A3)*A4
                ^
    (A1*(A2*A3))*A4
                ^
    A1*((A2*A3)*A4)
      ^
    A1*(A2*(A3*A4))
      ^
    (A1*A2)*(A3*A4)
           ^
    

    c) Berechnen Sie nach der Rekursionsgleichung (12) (siehe Skript Folie 3.2 / 23) die Tabelle m[i, j] für die Matrixkette und den Dimensionsvektor p = (p0, p1, p2, p3, p4) = (5, 3, 4, 2, 20). Schreiben Sie jeden Schritt genau auf, und markieren Sie den jeweils ausgewählten min-Wert, der dann in die Tabelle eingetragen wird.

    m[1, 1] = 0
    m[2, 2] = 0
    m[3, 3] = 0
    m[4, 4] = 0
    m[1, 2] = [k=1]: m[1, 1] + m[2, 2] + 5 * 3 * 4 = 60
              min(60) = 60
    m[2, 3] = [k=2]: m[2, 2] + m[3, 3] + 3 * 4 * 2 = 24
              min(24) = 24
    m[3, 4] = [k=3]: m[3, 3] + m[3, 4] + 4 * 2 * 20 = 160
              min(160) = 160
    m[1, 3] = [k=1]: m[1, 1] + m[2, 3] + 5 * 3 * 2 = 54
              [k=2]: m[1, 2] + m[3, 3] + 5 * 4 * 2 = 100
              min(54, 100) = 54
    m[2, 4] = [k=2]: m[2, 2] + m[3, 4] + 3 * 4 * 20 = 400
              [k=3]: m[2, 3] + m[4, 4] + 3 * 2 * 20 = 144
              min(400, 144) = 144
    m[1, 4] = [k=1]: m[1, 1] + m[2, 4] + 5 * 3 * 20 = 444
              [k=2]: m[1, 2] + m[3, 4] + 5 * 4 * 20 = 620
              [k=3]: m[1, 3] + m[4, 4] + 5 * 2 * 20 = 254
              min(444, 620, 254) = 254
    
    M i  j  1   2   3   4   (minimale Kosten pro Schritt)
      1     0   60  54  254
      2         0   24  144
      3             0   160
      4                 0
    

    Mit jedem wert der m-Tabelle hat man auch den zugehörigen k-wert des Splittpunktes gefunden. Tragen Sie den k-Wert in die Tablle s[i,j] ein.

    S i  j  1   2   3   4   (k Werte für minimale Kosten)
      1         1   1   3
      2             2   3
      3                 3
      4
    

    Damit wäre die optimale Klammerung (A1*(A2*A3))*A4.

    Erklären Sie, warum die Tabelle s nur oberhalb der Nordwest-Südost Diagonale sinnvolle Werte enthält.

    In und unterhalb der Diagonale stehen keine Werte, da an diesen Positionen keine Splittpunkte stehen können:
    Der Wert an der Position s[1, 2] = 1 bedeutet, dass ein Splittpunkt zwischen A1 und A2 verläuft. Entsprechend bedeutet der Wert s[1, 3] = 1 bedeutet, dass ein Splittpunkt zwischen A1, A2 und A3 nach der ersten Matrix verläuft, also A1 ^ A2 * A3. Es ist daher nicht möglich, dass ein Splittpunkt z.B. zwischen A1 und A1 besteht (also keine Werte für die Diagonale, wie z.B. s[1, 1]). Ausserdem ist die Reihenfolge der Matritzen festgelegt, nämlich A1, A2, A3, ... Ein Splittpunkt s[4, 1] würde bedeuten, dass die Matrix A4 vor der Matrix A1 steht.

    d) Führen Sie einen Trace des Algorithmus Print-Optimal-Parens(s, 1, 4) durch und schreiben Sie die optimale Klammerung auf (siehe Skript Folie 3.2 / 44).

    Welcher Zusammenhang besteht zwischen den beim Trace von Print-Optimal-Parens(s, 1, 4) verwendeten s-Werten (als Parameter für i und j) und der Berechnung der Werte in der m-Tabelle. Genaue Erklärung.

    Die S-Werte geben dasjenige k (Splitposition) an, das die minimalen Kosten in Form von Multiplikationen liefert.

     ME

     


    Aufgabe 2: Implementierung     top

    Die Methode "Matrix-Chain-Order" füllt die Tabellen M und S.

    /**
     * Calculates the optimal matrix multiplication order.
     * @see IChainMultiplicationOptimizer#matrixChainOrder(int[])
     */
    public void matrixChainOrder(int[] dimensions) {
    	dim = dimensions;
    	int matrices = getMaticesCount(); 
    	
    	m = new int[matrices+1][matrices+1];
    	s = new int[matrices+1][matrices+1];
    	
    	int j, q;
    
    	for (int i = 1; i <= matrices; i++)
    		m [i][i] = 0;
    			
    	for (int l = 2; l <= matrices; l++){
    		for (int i = 1; i <= matrices-l+1; i++){
    			j = i+l-1;
    			m[i][j] = -1;
    			for (int k = i; k <= j-1; k++){
    				q = m[i][k]+m[k+1][j]+dim[i-1]*dim[k]*dim[j];
    				if (m[i][j] == -1 || q < m[i][j]){
    					m[i][j] = q;
    					s[i][j] = k;
    				}
    			}
    		}
    	}
    	
    	notifyListeners(IChainMultiplicationOptimizer.NOTIFY_FINISHED);
    }
    

    MB

    Die Methode "print-optimal-parens" erzeugt eine Stringdarstellung der optimalen Klammerung:

    /**
     * Returns a string representation of the optimal parenthesis.
     * @see IChainMultiplicationOptimizer#getOptimalParentheses()
     */
    public String getOptimalParentheses() {
    	return getOptimalParentheses(1, getMaticesCount());
    }
    
    private String getOptimalParentheses(int i, int j) {
    	if (i==j) return "A"+i;
    	return  "("+
    			getOptimalParentheses(i, s[i][j])+
    			getOptimalParentheses(s[i][j]+1, j)+
    			")";
    }
    

    ME

    Die GUI besteht aus zwei JTable Objekten sowie diversen Ein- und Ausgabefeldern. Die Klasse, welche die oben genannten Methoden implementiert, benachrichtigt nach dem Füllen der M und S Tabelle die View (Observer), damit diese aktualisiert wird (Observer-Muster).

    MSC

    Welche asymptotische Laufzeit hat der Algorithmus Matrix-Chain-Order(p) ?

    n sei die Anzahl der Matritzen.
    Die M-Tabelle ist eine n x n Matrix, die zur Hälfte zu füllen ist. Die Ermittlung eines m[i, j]-Wertes geschieht in konstanter Zeit, da auf vorher berechnete Werte zugegriffen wird und lediglich drei Multiplikationen (pi-1*pk*pj) hinzukommen. Die Bestimmung eines S-Wertes wird durch Vergleichen von maximal n-Werten berechnet.
    Ein Blick in den Code verrät uns ebenfalls eine Annäherung an die Laufzeit:

    for (int l = 2; l <= matrices; l++){
    	for (int i = 1; i <= matrices-l+1; i++){
    		j = i+l-1;
    		m[i][j] = -1;
    		for (int k = i; k <= j-1; k++){
    			q = m[i][k]+m[k+1][j]+dim[i-1]*dim[k]*dim[j];
    			if (m[i][j] == -1 || q < m[i][j]){
    				m[i][j] = q;
    				s[i][j] = k;
    			}
    		}
    	}
    }
    
    Die beiden äusseren Schleifen l und k haben eine worst-case Laufzeit von O(n2).

    MSC

     


    Dateien und Javadoc     top

    Javadoc online
    Online Applet
    Alle Dateien als Rar-Archiv