Perkalian Matriks

Soal 5 Olimpiade Sains Mahasiswa 2007, Yogyakarta.

Deskripsi Soal :

Diberikan sebuah perkalian matriks, P=A*B*C*D, dengan ordo/ ukuan masing-masing A(20X50), B(50X100), C(100X10), dan D(10X30). Ada beberapa cara melakukan perkalian matriks ini, dan tiap cara mempunyai jumlah operasi perkalian yang berbeda, antara lain :

1) P=(A*B)*C*D => (20*50*100)+(20*100*10)+(20*10*30) = 126000 perkalian

2) P=A*((B*C)*D) => (50*100*10)+(50*10*30)+(20*50*30) = 95000 perkalian

3) P=A*(B*C)*D => (50*100*10)+(20*50*10)+(20*10*30) = 66000 perkalian

Ternyata jumlah operasi perkalian terkecil yang mungkin terjadi adalah 66000 perkalian, yaitu dengan P=A*(B*C)*D. Buatlah program yang menerima input 2 baris. Baris pertama adalah jumlah matriks(N) dan baris kedua berisi N+1 bilangan asli yang menyatakan ukuran matriks pada perkalian. Program harus meng-outputkan jumlah opersi perkalian terkecildari perkalian matriks tersebut.

Contoh Input 1 :

4

20 50 100 10 30

 

Contoh Output 1 :

66000

 

Contoh Input 2 :

3

1 4 7 5

 

Contoh Output 2 :

63

 

Solusi :

Dalam perkalian dua matriks A(mxn) dan B(nxo) akan menghasilkan matriks baru C dengan ukuran (mxo). Sedangkan jumlah operasi perkaliannya adalah (m*n*o).

Awalnya saya berpikir untuk mengalikan 2 matriks A(mxn) dan B(nxo) dengan nilai n terbesar, sehingga nilai n hilang dan tidak dipakai lagi dalam perkalian matriks berikutnya(greedy). Tapi ternyata algoritma itu tidak menghasilkan nilai minimum untuk contoh input ke-2. Jadi saya beralih ke DP, meskipun kompleksitasnya lumayan besar, sekitar O((n+1)^3/2).

 

Formula DPnya kira-kira seperti ini :

Untuk data ukuran matriks i sampai j, nilai awal min[i,j] adalah ∞.

Kemudian untuk k= i+1 sampai j-1,

tmp:=min[i,k]+min[k,j]+(data[i]*data[k]*data[k])

            jika tmp<min[i,j], maka min[i,j]=tmp

 

Tenti saja kita harus mencari nilai min[i,k] dan min [k,j] terlabih dahulu. Dengan kata lain, formula DP diatas harus dilakukan pada selisih i dan j yang terkecil terlebih dahulu. Kita definisikan bahwa min[i,i+1]:=0 (karena merupakan data satu matriks saja) dan min[i,i+2]=data[i]*data[i+1]*data[i+2] (karena hanya mencakup 2 matriks saja, yaitu matriks A(data[i]xdata[i+1]) dan matriks B(data[i+1],data[i+2]))

Kira-kira kode Pascalnya seperti ini :

 

var data:array[1..100] of integer;

    min:array[1..100,1..100] of longint;

    k,i,j,n,selisih:integer;

    tmp:longint;

 

begin

  readln(n);

  n:=n+1;

  for i:=1 to n do

    read(data[i]);

 

  for selisih:=2 to n-1 do

    for i:=1 to n-selisih do

      begin

        j:=i+selisih;

        min[i,j]:=high(longint);

        for k:=i+1 to j-1 do

          begin

            tmp:=min[i,k]+min[k,j]+(data[i]*data[k]*data[j]);

            if tmp<min[i,j] then

              min[i,j]:=tmp;

          end;

      end;

 

  writeln(min[1,n]);

end.

20 thoughts on “Perkalian Matriks

  1. Dwika mengatakan:

    Ons… Masih pegang programming ya???
    manteppp…
    haha…. gw dah cupu super neh di sini… hahaha…

  2. ghostyoen mengatakan:

    itu semua kan program untuk matriks yang elemennya filed.Seandainya elemen matriksnya atas ring komutatif gmn ?
    Thank jawabannya nt. Ghostyoen.wordpress.com

  3. Riza mengatakan:

    Waduh mbak, ring komutatif itu yang kayak gimana ya?
    Saya belum dapet matematika diskrit , jadi belum paham.
    Maklum, baru kelar semester 1.

    Misalnya elemen matriksnya atas ring komutatif, apa sifat2 perkalian matriksnya tetap atau berubah?

  4. a-vip mengatakan:

    bagus anak muda,,, terus semangat.. jgn berhenti sampai disini..
    jangan meniru jalan abang mu yang satu ini (g pernah megang coding, skrg jadi bingung)

    masi banyak hal baru yg bisa kmu dapat..
    keep your dream ahead..

  5. arie mengatakan:

    wuuuuaaaah…………………………
    kalian ngomongin apa sich…..?
    kok aku ga mudeng………

  6. mita mengatakan:

    w masih bingung ni,…
    ko susah bgt ya programnya,
    w masih tingkat 2 sih
    boleh ga ka jelasin programnya secara deteil
    biar lebih ngerti

  7. ALDIE mengatakan:

    knp nh msh ga lengkap ttg matriks ny pdhl ku mo cari bhn to skripsi nh….

    tolong carikan matriks yg lengkap ya…

    lam to pecinta matematika all…

  8. garnieri mengatakan:

    hm.. mirip sama soal uas PAA tahun 2007 yha..
    cukup membantu untuk belajar buat ujian nih, thanks yak🙂

  9. dheva mengatakan:

    mo tanya kalo menghitung matriks berpangkat itu ada berapa cara? terus apa aja

  10. ananta mengatakan:

    waduh……pusing nech cerita matriks alnya law cerita matematika pusing nech
    kasih tw dunk gimana matriks itu sesungguhnya.
    balazzzzzz

  11. christian mengatakan:

    kalo dalam bahasa C source code nya gimana..hehehe…
    mohon bantuan dalam penyelesaian Tugas akhir.mneyelesaikan perkalian matriks dimensi besar…
    trima kasih sebelumnya…

  12. nobita mengatakan:

    haduh… thx you….

    mantep….

  13. nobita mengatakan:

    ajarin donk c++

  14. wah.. bingung… gak ngerti sama sekali…..😀

  15. Arni mengatakan:

    Bingung…

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s