3. matrix chain multiplication (fajar)

LOGO

III Perkalian Matriks BerantaiMatrix Chain Multiplication

Pendahuluan

Matrix Chain MultiplicationPerkalian Matriks Berantai

Biaya Komputasi adalah Banyaknya perkalian skalar dari suatu perkalian matriks

Biaya Komputasi =

CONTOH 1

Biaya Komputasi = 12

Banyaknya perkalian skalar dari suatu perkalian matriks

Asosiatif Matriks & Biaya komputasi

=

n = 3

CONTOH 2

TENTUKAN BIAYA KOMPUTASI

Cara memposisikan penyisipan tanda kurung (parenthesized) dapat mengakibatkan Biaya Komputasi yang berbeda

Fungsi Parenthesization

Misalkan P(n) adalah fungsi parenthesization yang didefisikan sebagai jumlah cara memposisikan penyisipan tanda kurung dalam suatu perkalian matriks berantai berukuran n.

Dengan

CONTOH 3

misalkan diberikan 6 buah matriks dengan dimensi seperti pada tabeL berikut :

1. Hitung berapa cara memposisikan penyisipan tanda kurung (perenthesation) !

2. tentukan bagaimana cara perkalian yang memiliki biaya komputasi minimal !

= 42

Optimal

)1()( nCnP [Catalan number]

)2()4

(2

1

12/3

nn

nn

n

n

Dynamic Programming

TAHAP 1 Karakterisasi struktur dari parenthesization yang optimal

; 1 ≤ i ≤ j ≤ n

OPTIMAL

Combine OPTIMALOPTIMAL

Misalkan

TAHAP 2 Definisikan secara rekursif nilai solusi optimal

m[i, j] adalah nilai minimum yang dibutuhkan untuk perhitungan perkalian skalar matriks

TAHAP 3 Hitung nilai solusi optimal

Algoritme Matrix–Chain-Order (MCO)   p0 p1 p2 p3 p4 p5 p6

p 30 35 15 5 10 20 25n = 7-1

p0 p1 p2 p3 p4 p5 p6

30 35 15 5 10 20 25

p0 p1 p2 p3 p4 p5 p6

30 35 15 5 10 20 25

p0 p1 p2 p3 p4 p5 p6

30 35 15 5 10 20 25

p0 p1 p2 p3 p4 p5 p6

30 35 15 5 10 20 25

p0 p1 p2 p3 p4 p5 p6

30 35 15 5 10 20 25

Bottom

Up

Slide 10

Optimal

Bottom

Up

Slide 10

Tahap 4 Konstruksi solusi optimal

Hasil

Kesimpulan

Fungsi Parenthesization menghasilkan

Algoritme Matrix–Chain-Order dalam Dynamic Programming menghasilkan kompleksitas sebesar dengan ruang penyimpanan sebesar

)