3. matrix chain multiplication (fajar)
DESCRIPTION
Tugas Analisis & Desain AlgoriitmeTRANSCRIPT
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
)