kuliah ke-2

27
Kuliah Ke-2 Matriks Jarang dan Pengalamatan Matriks (Bab 2) Informatics Engineering Department TRUNOJOYO UNIVERSITY

Upload: zlata

Post on 22-Feb-2016

62 views

Category:

Documents


0 download

DESCRIPTION

Kuliah Ke-2. Matriks Jarang dan Pengalamatan Matriks (Bab 2) Informatics Engineering Department TRUNOJOYO UNIVERSITY. PENGALAMATAN. Array / Larik. LOK(LA[K]) = Awal(LA) + W(K - LB) Contoh: Misalkan Awal (Jual) = 100 dan W= 4, maka LOK (JUAL[1990]) = 100 LOK (JUAL[1991]) = 104 - PowerPoint PPT Presentation

TRANSCRIPT

Page 1: Kuliah Ke-2

Kuliah Ke-2Matriks Jarang dan Pengalamatan Matriks (Bab 2)

Informatics Engineering DepartmentTRUNOJOYO UNIVERSITY

Page 2: Kuliah Ke-2

PENGALAMATANArray / LarikArray / Larik

LOK(LA[K]) = Awal(LA) + W(K - LB)  Contoh:Misalkan Awal (Jual) = 100 dan W= 4, maka LOK (JUAL[1990]) = 100LOK (JUAL[1991]) = 104LOK (JUAL[1992]) = 108 Berapa lokasi JUAL[2000] ? untuk mendapat lokasi tersebut  LOK(LA[K]) = Awal(LA) + W(K - LB)

= 100 + 4 * (2000 – 1990)= 140

Page 3: Kuliah Ke-2

PENGALAMATANArray / LarikArray / Larik

Lokasi Memori Array

Awal - 100Awal - 100 Jual(1990)

104104 Jual(1991)

108108 Jual(1992)

112112 Jual(1993)

116116 Jual(1994)

112112 Jual(1995)

124124 Jual(1996)

128128 Jual(1997)

132132 Jual(1998)

136136 Jual(1999)

140140 Jual(2000)

Page 4: Kuliah Ke-2

Struktur Data :Struktur Data : Matriks MatriksDefinisi•struktur data yang mengacu pada sekumpulan elemen yang diakses melalui indeks •Array dua dimensi, yang memiliki indeks baris dan kolom

1 8 0 3 6 9

2 4 0 8 7 0

1

Ar ra y B dua di me ns i (ma tr ik s ) :- j uml a h ba ri s 2 , k ol om 3- d a ta 1 8 , 0 3 , 6 9 , 2 4 , 08 , 7 0 .

2

1 2 3

Page 5: Kuliah Ke-2

Proses Matriks1. Elemen Matriks diproses Baris demi

Baris2. Elemen Matriks diproses Baris demi

Baris

1 8 0 3 6 9

2 4 0 8 7 0

1

Ar ra y B dua di me ns i (ma tr ik s ) :- j uml a h ba ri s 2 , k ol om 3- d a ta 1 8 , 0 3 , 6 9 , 2 4 , 08 , 7 0 .

2

1 2 3

Page 6: Kuliah Ke-2

PROSES MATRIKSMatriksMatriks

1 8 0 3 6 9

2 4 0 8 7 0

1

Ar ra y B dua di me ns i (ma tr ik s ) :- j uml a h ba ri s 2 , k ol om 3- d a ta 1 8 , 0 3 , 6 9 , 2 4 , 08 , 7 0 .

2

1 2 3

18 3 69

24 8 70

Page 7: Kuliah Ke-2

PROSES MATRIKSMatriksMatriks

1 8 0 3 6 9

2 4 0 8 7 0

1

Ar ra y B dua di me ns i (ma tr ik s ) :- j uml a h ba ri s 2 , k ol om 3- d a ta 1 8 , 0 3 , 6 9 , 2 4 , 08 , 7 0 .

2

1 2 3

18 3 69

24 8 70

Page 8: Kuliah Ke-2

INISIALISASIMatriksMatriks

1 8 0 3 6 9

2 4 0 8 7 0

1

Ar ra y B dua di me ns i (ma tr ik s ) :- j uml a h ba ri s 2 , k ol om 3- d a ta 1 8 , 0 3 , 6 9 , 2 4 , 08 , 7 0 .

2

1 2 3

For Baris = 1 to 2 do For Kolom = 1 to 3 do A(Baris, Kolom) = 0A(Baris, Kolom) = 0 EndforEndfor

0 0 00 0 0

Page 9: Kuliah Ke-2

Isi dengan 1,2,3,4,5,6MatriksMatriks

1 8 0 3 6 9

2 4 0 8 7 0

1

Ar ra y B dua di me ns i (ma tr ik s ) :- j uml a h ba ri s 2 , k ol om 3- d a ta 1 8 , 0 3 , 6 9 , 2 4 , 08 , 7 0 .

2

1 2 3

Indeks = 1For Baris = 1 to 2 do For Kolom = 1 to 3 do A(Baris, Kolom) = IndeksA(Baris, Kolom) = Indeks

Indeks = Indeks + 1Indeks = Indeks + 1 EndforEndfor

1 2 34 5 6

Page 10: Kuliah Ke-2

Isi dengan 1,3,5,7,9,11MatriksMatriks

1 8 0 3 6 9

2 4 0 8 7 0

1

Ar ra y B dua di me ns i (ma tr ik s ) :- j uml a h ba ri s 2 , k ol om 3- d a ta 1 8 , 0 3 , 6 9 , 2 4 , 08 , 7 0 .

2

1 2 3

Indeks = ???For Baris = 1 to 2 do For Kolom = 1 to 3 do A(Baris, Kolom) = ???A(Baris, Kolom) = ???

Indeks = ???Indeks = ??? EndforEndfor

1 3 57 9 13

Page 11: Kuliah Ke-2

1 8 0 3 6 9

2 4 0 8 7 0

1

Ar ra y B dua di me ns i (ma tr ik s ) :- j uml a h ba ri s 2 , k ol om 3- d a ta 1 8 , 0 3 , 6 9 , 2 4 , 08 , 7 0 .

2

1 2 3

18 3 69

24 8 70

Menjumlahkan setiap barisMatriksMatriksFor Baris = 1 to 2 do

TotalBaris = 0 For Kolom = 1 to 3 do

TotalBaris = TotalBaris + A[Baris,Kolom]

Endfor Print Total BarisEndfor

90

102

Page 12: Kuliah Ke-2

1 8 0 3 6 9

2 4 0 8 7 0

1

Ar ra y B dua di me ns i (ma tr ik s ) :- j uml a h ba ri s 2 , k ol om 3- d a ta 1 8 , 0 3 , 6 9 , 2 4 , 08 , 7 0 .

2

1 2 3

18 3 69

24 8 70

Menjumlahkan C = A + BDua buah MatriksDua buah Matriks

For Baris = 1 to 2 do For Kolom = 1 to 3 do

C[Baris,Kolom] =A[Baris,Kolom]+ B[Baris,Kolom]

Endfor Endfor

1 8 0 3 6 9

2 4 0 8 7 0

1

Ar ra y B dua di me ns i (ma tr ik s ) :- j uml a h ba ri s 2 , k ol om 3- d a ta 1 8 , 0 3 , 6 9 , 2 4 , 08 , 7 0 .

2

1 2 3

1 2 3

4 5 6

Page 13: Kuliah Ke-2

1 8 0 3 6 9

2 4 0 8 7 0

1

Ar ra y B dua di me ns i (ma tr ik s ) :- j uml a h ba ri s 2 , k ol om 3- d a ta 1 8 , 0 3 , 6 9 , 2 4 , 08 , 7 0 .

2

1 2 3

18 3 69

24 8 70

MengalikanMatriksMatriks

For Baris = 1 to 2 do For Kolom = 1 to 3 do C[Baris, Kolom] = 0 For K = 1 to P do C[Baris,Kolom] =C[Baris,Kolom]+ A[Baris,K] + B[K,Kolom] Endfor Endfor Endfor

Page 14: Kuliah Ke-2

Kita lanjutkan Kita lanjutkan untuk yang satu ini …..untuk yang satu ini …..

Page 15: Kuliah Ke-2

Matriks JarangSparse Matrix

matriks yang elemennya banyak bernilai o (nol).

Idenya : bgm mengkonversinya supaya lebih hemat memori

Page 16: Kuliah Ke-2

Contoh Matriks JarangSparse Matrix

Matriks Segitiga Matriks Tridiagonal

Page 17: Kuliah Ke-2

Konversi Matriks JarangSparse Matrix

9 data menjadi 6 data

Page 18: Kuliah Ke-2

Konversi Matriks JarangSparse Matrix

16 data menjadi 10 data

Page 19: Kuliah Ke-2

Ubah Matriks Segitiga jadi ArraySparse Matrix

Program Ubah_Matrik_Segitiga_jadi_ArrayKAMUS Baris, Kolom : integer A : array [1..3, 1..3] of integer S : array [1..6] of integer ALGORITMA JLH 0 For Baris 1 to 3 do For Kolom 1 to Baris 3 do JLH JLH + 1 S[JLH] A[Baris, Kolom] Endfor Endfor

Page 20: Kuliah Ke-2

Lokasi Elemen Matriks Segitiga Sparse Matrix

Lokasi pada array :

L = Baris ( Baris – 1 )

________________ + Kolom

2

Page 21: Kuliah Ke-2

18 3 69

24 8 70

Pengalamatan MatriksOrderingOrdering

90

102

1 2 3

1 A[1,1] A[1,2] A[1,3]

2 A[2,1] A[2,2] A[2,3]

A[1,1], A[1,2], A[1,3], A[2,1], A[2,2],A[2,3]…... jika row major

A[1,1], A[2,1], A[1,2], A[2,2], A[1,3],A[2,3]….. jika column major

Page 22: Kuliah Ke-2

Pengalamatan MatriksRow OrderingRow Ordering

A[1,1], A[1,2], A[1,3], A[2,1], A[2,2],A[2,3]…... jika row major

A[1,1], A[2,1], A[1,2], A[2,2], A[2,2],A[2,3]….. jika column major

X[1,1] Baris ke –1X[1,2] Baris ke –1X[1,3] Baris ke –1X[2,1] Baris ke-2X[2,2] Baris ke-2X[2,3] Baris ke-2

Page 23: Kuliah Ke-2

Pengalamatan MatriksColumn OrderingColumn Ordering

A[1,1], A[1,2], A[1,3], A[2,1], A[2,2],A[2,3]…... jika row major

A[1,1], A[2,1], A[1,2], A[2,2], A[2,2],A[2,3]….. jika column major

X[1,1] Kolom ke –1X[2,1] Kolom ke –1X[1,2] Kolom ke –2X[2,2] Kolom ke –2X[1,3] Kolom ke –3X[2,3] Kolom ke –3

Page 24: Kuliah Ke-2

Cari Alamat Elemen MatriksRow OrderingRow Ordering

1 2 3 4 5 61 400 404 408 412 416 4202 424 428 …3 448 ???4 … ???5

6

7

8 ???

Page 25: Kuliah Ke-2

Pengalamatan MatriksOrderingOrdering

Mencari lokasi memori pada Row-major order

Lokasi (A[B,K] = Base(A) + w [ N ( B-1) + (K-1) ]

Mencari lokasi memori pada Column-major order

Lokasi (A[B,K] = Base(A) + w [ M ( B-1) + (K-1) ]

Base (a): lokasi awal di memori (alamat A[1,1])

W: jumlah word/byte utk menyimpan 1 elemen

M: jumlah baris pada matriks A

N: jumlah kolom pada matriks A

Page 26: Kuliah Ke-2

Cari Alamat Elemen MatriksColumn OrderingColumn Ordering

1 2 3 4 5 61 400 ???2 4043 408 ???4 412 ???5

6

7

8 ???

Page 27: Kuliah Ke-2

Cari Alamat Elemen Matriks

1 2 3 4 5 61 ???2 4003

4

5 5086

7

8 ???