KULIAH STRUKTUR DATA
MATRIKS
Matriks adalah sekumpulan informasi yang setiap individu elemennya terdefinisi berdasarkan dua buah indeks (yang biasanya dikonotasikan dengan baris dan kolom).
Setiap elemen matriks dapat diakses secara langsung jika kedua indeks diketahui, dan indeksnya harus bertype yang mempunyai keterurutan (suksesor), misalnya integer.
Matriks adalah struktur data dengan memori internal. Struktur ini praktis untuk dipakai tetapi memakan memori! (Matriks integer 100 x 100 memakan 10000 x tempat penyimpanan integer.)
Sering dikatakan bahwa matriks adalah tabel atau array berdimensi 2. Tetapi patut diperhatikan, bahwa pengertian "dimensi 2", "baris dan kolom" adalah dalam pemikiran kita. Pengaturan letak elemen matriks dalam memori komputer selalu tetap sebagai deretan sel "linier". Pengertian 2 dimensi ini hanya untuk mempermudah pemrogram dalam mendesain programnya. Maka matriks adalah salah satu contoh struktur data "lojik".
Contoh : untuk matriks 3x4 sebagai berikut:
Dapat disimpan secara linier dan kontigu dengan dua alternatif sebagai berikut :
a. Per baris
1 2 3 4 5 6 7 8 9 10 1112
b. Per kolom
1 5 9 2 6 10 3 7 11 4 8 12
Banyaknya baris dan banyaknya kolom biasanya disebut sebagai ukuran matriks.
Contoh: matriks berukuran 4 x 5 artinya mempunyai baris sebanyak 4 dan kolom sebanyak 5, sehingga dapat menyimpan 20 elemen. Ada beberapa bahasa pemrograman yang meminta ukuran matriks pada pendefinisiannya, ada yang meminta penomoran minimum dan maksimum dari baris dan kolom. Pada notasi algoritmik yang kita pakai, Cara kedua yang akan dipakai, sebab ukuran matriks dapat dideduksi dari penomorannya.
Matriks adalah struktur data yang "statik", yaitu ukuran maksimum memorinya ditentukan dari awal. Batas indeks baris dan kolom harus terdefinisi dengan pasti saat dideklarasi dan tak dapat diubah-ubah. Seringkali dalam persoalan semacam ini, kita memesan memori secara "berlebihan" untuk alasan terjaminnya memori yang tersedia, dan hanya memakai sebagian saja. Biasanya memori yang dipakai (selanjutnya disebut efektif) adalah yang "kiri atas" seperti ilustrasi sebagai berikut, dimana pada saat deklarasi, memori maksimum yang disediakan adalah 10x10, dan hanya akan dipakai untuk 3X4.
Jika bahasa yang menangani matriks tidak menentukan spesifikasi inisialisasi nilai pada saat memori dialokasi, maka:
1 1 1
2 2 2
3 3 3
4 4 4
1 2 3 4 5 6 7 8 9 10
1
2
3
4
5
6
7
8
9
10
"Linierisasi" per baris akan menghasilkan nilai :
{1,1,1,?,?,?,?,?,?,?},{2,2,2,?,?,?,?,?,?,?},{3,3,3,?,?,?,?,?,?,?},{4,4,4,?,?,?,?,?,?,?},{?,?,?,?,?,?,?,?,?,?},{?,?,?,?,?,?,?,?,?,?},{?,?,?,?,?,?,?,?,?,?},{?,?,?,?,?,?,?,?,?,?},{?,?,?,?,?,?,?,?,?,?},{?,?,?,?,?,?,?,?,?,?}
Sedangkan linierisasi per kolom akan menghasilkan nilai :
{1,2,3,4,?,?,?,?,?,?),{1,2,3,4,?,?,?,?,?,?),{1,2,3,4,?,?,?,?,?,?),{1,2,3,4,?,?,?,?,?,?),{?,?,?,?,?,?,?,?,?,?},{?,?,?,?,?,?,?,?,?,?},{?,?,?,?,?,?,?,?,?,?},{?,?,?,?,?,?,?,?,?,?},{?,?,?,?,?,?,?,?,?,?}, {?,?,?,?,?,?,?,?,?,?}
Akibat dari "linierisasi" yang tergantung kepada bahasa pemrograman tersebut, dan pemakaian memori yang "hanya sebagian" dari keseluruhan memori yang dipesan, maka passing parameter sebuah matriks dapat menimbulkan kesalahan.
Misalnya sebuah fungsi atau prosedur mempunyai parameter formal sebuah matriks dengan dimensi 6x6, dan bahasanya akan mengolah per kolom Jika parameter aktual adalah sebuah matriks berukuran 3x4 dengan nilai
1 2 3 4
5 6 7 8
9 10 11 12
Maka ketika nilai ditampung dalam prosedur berparameter formal matriks 6x6, dengan traversal i dan j untuk iε [1..3], jε[1..4] akan di proses dengan beberapa nilai tak terdefinisi yaitu {1,5,9,10,3,7,8,12,?,?,?,?}, seperti digambarkan sebagai berikut :
1 10 8 ? ? ?
5 3 12 ? ? ?
9 7 ? ? ? ?
2 11 ? ? ? ?
6 4 ? ? ? ?
Maka, sebaiknya jika merancang prosedur atau fungsi yang mempunyai parameter, ukuran parameter formal harus sama dengan parameter aktual.
Beberapa bahasa, misalnya bahasa Fortran, menyediakan fasilitas "adjustable dimension", yaitu ukuran parameter formal matriks belum ditentukan dimensinya, dan baru ditentukan saat parameter aktual diberikan. Fasilitas ini mengurangi kesalahan yang terjadi.
Beberapa contoh matriks dan isinya:
1. MatNamaHari [1..7,1..3] : Nama hari ke 1 s/d 7 dalam 3 bahasa (Indonesia, Inggris, Prancis) :
1 =INDONESIA 2 = INGGRIS 3 = PRANCIS
1 Senin Monday Lundi
2 Selasa Tuesday Mardi
3 Rabu Wednesday Mercredi
4 Kamis Thursday Jeudi
5 Jum'at Friday Vendredi
6 Sabtu Saturday Samedi
7 Minggu Sunday Dimanche
2. A [1..5,1..5] : Matriks bilangan real
1 2 3 4 5
1 12.1 7.0 8.9 0.7 6.6
2 0.0 1.6 2.1 45.9 55.0
3 6.1 8.0 0.0 3.1 21.9
4 9.0 1.0 2.7 22.1 6.2
5 5.0 0.8 0.8 2.0 8.1
3. MatFrek [`A'..'E',1..7] : Matriks frekuensi kemunculan huruf `A' s/d `E' pada hasil pemeriksaan 7 pita karakter
1 2 3 4 5 6 7
`A' 12 71 82 0 62 30 11
`B' 0 1 2 45 5 3 10
`C' 6 8 0 3 21 3 6
`D' 9 1 2 22 6 9 7
`E' 5 0 0 2 8 45 23
4. MatSurvey [1..4,1..7] : Matriks hasil survey pada titik koordinat,. Mat(i,j)adalah hasil pengukuran
1 2 3 4
1 <24,5> <24, 5> <30,5> <25,5>
2 <23,56> <3,6> <40,5> <2,2>
3 <22,73> <7,3> <60,6> <8,3>
4 <21,56> <8,5> <9,8> <7,4>
5 <23,56> <12,50> <3,36> <30,6>
6 <20,0> < 2,56> <5,46> <20,99>
7 <30,0> < 9,0> <15,0> <27,0>
5. MatSat [1..4,1..4] : Matriks satuan
1 2 3 4
1 1 0 0 0
2 0 1 0 0
3 0 0 1 0
4 0 0 0 1
6. MatSym [1..6,1..6] : Matriks simetris
1 2 3 4 5 6
1 1 0 10 0 4 33
2 0 12 0 0 3 4
3 10 0 11 0 4 3
4 0 0 0 1 0 2
5 4 3 4 0 8 1
6 33 4 3 2 1 0
Contoh Pemakaian matriks:
- matriks banyak digunakan dalam komputasi numerik untuk representasi dalam finite element
- seperti penggunaan matriks dalam matematika. Perhitungan "biasa" terhadap matriks : penjumlahan, perkalian dua matriks, menentukan determinan,
menginvers sebuah matriks, memeriksa apakah sebuah matriks : simetris, matriks satuan. Hanya saja dalam algoritma, semua "perhitungan" itu menjadi tidak primitif, harus diprogram
- dalam perhitungan ilmiah di mana suatu sistem diwakili oleh matriks (elemen hingga dalam teknik sipil dan mesin)
- dalam persoalan pemrograman linier dan operational research.
- dalam persoalan algoritmik : untuk menyimpan informasi yang cirinya ditentukan oleh 2 komponen (yang nantinya diterjemahkan dalam baris dan kolom) dan diakses langsung.
Contoh : merepresentasi "cell" pada sebuah spreadsheet, merepresentasi "ruangan" pada sebuah gedung bertingkat,...
Notasi algoritmik dari matriks :
NamaMatriks (indeks1,indeks2)
Domain :
- Domain matriks sesuai dengan pendefinisian indeks
- Domain isi matriks sesuai dengan jenis matriks
Konstanta :
- Konstanta untuk seluruh matriks tidak terdefinisi,
- Konstanta hanya terdefinisi jika indeks dari matriks terdefinisi
IMPLEMENTASI Fisik 1 :
Karena sering dipakai, type primitif yang namanya matrix sudah dianggap ada, seperti halnya type dasar array. Hanya saja kalau type array ditentukan oleh satu indeks, maka type matrix mampu menangani 2 indeks, yang diinterpretasikan oleh pemrogram seperti baris dan kolom.
Contoh (lihat Gambar): Perhatikanlah "semantik" dari setiap pendefinisian berikut :
MatFrek : matrix ['A'..'E',1..7] of integer
Sebuah matriks yang merepresentasi frekuensi huruf 'A' s/d 'E', untuk 7 buah teks. Maka MatFrek(i,j) berarti Frekuensi huruf ke-i untuk teks ke-j
A: matrix [1..5,1..5] of real
Sebuah matriks seperti dalam matematika biasa
NamaHari: matrix [1..7,1..3] of string
Untuk matriks nama hari pada contoh-1 yang merepresentasi nama-nama ke 7 (tujuh) buah hari ([1..7]) dalam 3 (tiga) bahasa ([1..3]). Maka NamaHari[i,j] berarti Hari ke-i dalam bahasa ke-j
Untuk matriks yang merepresentasi hasil survey pada setiap titik koordinat pengamatan. Koordinat yang diukur adalah (1,1) s/d (4,7).dengan definisi
type Data :
MatSurvey: matrix [1..4,1..7] of Data
Maka, MatSurvey(i,j) berarti hasil Data pengukuran temperatur dan kecepatan angin pada grid kartesian (i,j)
Cara mengacu : melalui indeks
MatHari(i,j) , jika i dan j terdefinisi
TabNamaHari(1,7)
MatSurvey(3,5) untuk mengacu satu data survey
MatSurvey(3,5).Temp untuk mengacu data temperatur
IMPLEMENTASI Fisik 2 : Struktur fisik adalah tabel dari tabel (array of array)
Type dasar yang namanya matrix tidak ada, maka dibentuk dari type array. Maka matriks adalah array dari array.
MatFrek : array ['A'..'E'] of array [1..7] of integer
Sebuah matriks yang merepresentasi frekuensi huruf 'A' s/d 'E', untuk 7 buah teks. Maka MatFrek(i,j) berarti Frekuensi huruf ke-i untuk teks ke-j ditulis sebagai :
MatFrek(i,j)
A: array [1..5] of array [1..5] of integer
Sebuah matriks seperti dalam matematika ditulis sebagai :
A(i,j)
NamaHari: array [1..7] of array [1..3] of string
Sebuah matriks yang merepresentasi nama-nama ke 7 hari ([1..7]) dalam tiga bahasa ([1..3]), maka NamaHari(i,j) berarti Hari ke-i dalam bahasa ke-j ditulis sebagai :
NamaHari (i,j)
DataGeo : type
MatSurvey: array [1..4] of array [1..7] of DataGeo
Sebuah matriks yang merepresentasi hasil survey pada setiap titik koordinat pengamatan. Koordinat yang diukur adalah (1,1) s/d (7,4). Maka, MatSurvey(i,j) berarti hasil Data pengukuran temperatur dan kecepatan angin pada grid kartesian (i,j) ditulis sebagai MatSurvey(i,j)
Sedangkan untuk mengacu kepada data kecepatan angin : Matsurvey(i,j).Temp
Beberapa catatan mengenai matriks :
• Struktur matriks adalah struktur internal yang statis dan kontigu
• Alokasi memori sebuah matriks berukuran N x M selalu dilakukan sekaligus. Dari ruang memori berukuran N x M tsb, mungkin hanya "sebagian" yang dipakai.
IL/4_Adtmatri.doc/ADT MATRIKS 06/16/03 9:24 AM
Purchase@SoftInterface.com
Karena itu ada pengertian :
• Definisi ruang memori seluruh matriks
• Memori yang secara efektif dipakai oleh sebuah matriks tertentu
• Nilai yang disimpan dalam sebuah matriks dapat disimpan di dalam ruang memori dipesan.
• Matriks dapat menimbulkan persoalan dalam passing parameter. Karena itu sebaiknya parameter aktual dan parameter formal sama ukuran memorinya.
Perluasan dari matriks dua "dimensi" :
• Beberapa bahasa memungkinkan deklarasi variabel dengan lebih dari dua "dimensi" yaitu "indeks". Tidak disarankan untuk merancang struktur data internal dengan dimensi lebih dari 3!
• Pelajarilah fasilitas dari bahasa Pascal dan C untuk deklarasi, inisialisasi dan memproses matriks berdimensi 3 atau lebih amati perbedaannya jika ada.
ADT MATRIKS Dalam Bahasa Algoritmik
{ Definisi ABSTRACT DATA TYPE MATRIKS }
{ ************ HUBUNGAN DENGAN ADT LAIN ******************}
{ Tidak ada}
{ Alokasi elemen matriks selalu dilakukan sekaligus }
{ Definisi TYPE MATRIKS dengan indeks integer}
{ Ukuran minimum dan maksimum baris dan kolom }
type indeks : integer { indeks baris, kolom }
constant BrsMin : indeks =1
constant BrsMax : indeks =100
constant KolMin : indeks =1
constant KolMax : indeks =100
type el_type : integer
type MATRIKS :
< Mem : matrix(BrsMin..BrsMax,KolMin..KolMax) of el_type NbrsEff : integer {banyaknya/ukuran baris yg terdefinisi } NkolEff : integer {banyaknya/ukuran kolom yg terdefinisi } >
{ Invarian ADT : Matriks "kosong" : NbrsEff=0 dan NkolEff=0}
{ NbrsEff ≥ 1 dan NkolEff ≥ 1 }
{ Memori matriks yang dipakai selalu di "ujung kiri atas" }
{ ********************** Definisi METHOD **********************}
{ DEFINISI PROTOTIP PRIMITIF }
{ ** Konstruktor membentuk MATRIKS *}
procedure MakeMAT (NB:integer NK:integer)
{Membentuk sebuah MATRIKS "kosong" berukuran NB x NK di "ujung kiri" memori }
{ I.S. NB dan NK adalah valid untuk memori matriks yang dibuat }
{F.S. sebuah matriks sesuai dengan def di atas terbentuk }
{ ** Selektor "DUNIA MATRIKS ****}
function IdxBrsMin → indeks
{ Mengirimkan indeks Baris minimum Matriks apapun}
function IdxKolMin → indeks
{ Mengirimkan indeks Kolom minimum Matriks apapun }
function IdxBrsMax → indeks
{ Mengirimkan indeks Baris maksimum Matriks apapun }
function IdxKolMax → indeks
{ Mengirimkan indeks Kolom maksimum Matriks apapun }
function IsIdxValid (i,j: indeks) → boolean
{ Mengirimkan true jika I,j adalah indeks yang valid}
{ Untuk sebuah matriks M yang terdefinisi : }
function FirstIdxBrs (M: Matriks) → indeks
{ Mengirimkan indeks baris terkecil M}
function FirstIdxKol(M: Matriks) → indeks
{ Mengirimkan indeks kolom terkecil M}
function LastIdxBrs (M: Matriks) → indeks
{ Mengirimkan indeks baris terbesar M}
function LastIdxKol (M: Matriks) → indeks
{ Mengirimkan indeks kolom terbesar M}
function GetNBrsEff (M: Matriks) → integer
{ Mengirimkan Banyaknya Baris efektif M}
function GetNKolEff → integer
{ Mengirimkan Banyaknya Kolom efektif M}
function IsIdxEff (M: Matriks, i,j: indeks) → boolean
{ Mengirimkan true jika i,j adalah indeks efektif bagi M}
function GetElmt(M: Matriks, i,j : indeks) → el_type
{ Mengirimkan Elemen M dg nomor baris i dan nomor kolom j}
function GetElmtDiagonal(M: Matriks, i : indeks) → el_type
{ Mengirimkan Elemen M(i,i)}
{*** Operasi mengubah nilai elemen matriks: Set / Assign }
procedure SetBrsEff (Input/Output M: Matriks, Input NB : integer)
{I.S. M sudah terdefinisi }
{F.S. Nilai M.BrsEff diisi dengan NB, }
procedure SetKolEff (Input/Output M: Matriks, Input NK : integer)
{I.S. M sudah terdefinisi }
{F.S. Nilai M.NKolEff diisi dengan NK }
procedure SetEl (Input/Output M: Matriks, Input i,j : integer
input X : el_type)
{I.S. M sudah terdefinisi }
{F.S. M(i,j) bernilai X }
{Proses: Mengisi M(i,j) dengan X }
{ ****** Assignment MATRIKS *}
Procedure (Input Min: MATRIKS, Output MHsl: MATRIKS)
{ Melakukan assignment MHsl ← Min }
{ ******* KELOMPOK BACA/TULIS
procedure BacaMATRIKS (Output M: MATRIKS, Input NB,NK : integer)
{ I.S. IsIdxValid(NB,NK) }
{ F.S. M terdefinisi nilai elemen efektifnya, dan berukuran NB x NK }
{ Melakukan MakeMatriks(M,NB,NK) dan mengisi nilai efektifnya}
{ dari pembacaan dengan traversal per baris}
procedure TulisMATRIKS (Input M: MATRIKS)
{ I.S. M terdefinisi }
{ F.S. Sama dengan I.S, dan nilai M(i,j) ditulis ke layar}
{ Menulis Nilai setiap indeks dan elemen M ke layar }
{ dengan traversal per baris }
{ KELOMPOK OPERASI ARITMATIKA TERHADAP TYPE }
function "+" (M1,M2: MATRIKS) → MATRIKS
{ Precond : M1 berukuran sama dengan M2}
{ Mengirim hasil penjumlahan matriks: M1 + M2 }
function "-" (M1,M2: MATRIKS) → MATRIKS
{ Precond : M berukuran sama dengan M}
{ Mengirim hasil pengurangan matriks: salinan M1 M2 }
function "*" (M1,M2: MATRIKS) → MATRIKS
{ Precond : Ukuran Baris efektif M = Ukuran kolom efektif M}
{ Mengirim hasil perkalian matriks: salinan M1 * M2}
function "*" (M: MATRIKS, X: integer) → MATRIKS
{ Mengirim hasil perkalian setiap elemen M dengan X}
procedure "*" (M: MATRIKS, K : integer)
{ Mengalikan setiap elemen M dengan K}
{ ** Kelompok operasi relasional terhadap MATRIKS }
function "="(M1,M2: MATRIKS) → boolean
{ Mengirimkan true jika M1 = M2, }
{ yaitu NBElmt(M1) = NBElmt(M2) dan }
{ untuk setiap i,j yang merupakan indeks baris dan kolom}
{ M1(i,j) = M2(i,j) }
function StrongEQ (M1,M2: MATRIKS) → boolean
{ Mengirimkan true jika M1 "strongly equal" M2, }
{ yaitu FirstIdx(M1) = FirstIdx(M2) dan LastIdx(M1)=LastIdx(M2) dan }
{ untuk setiap i,j yang merupakan indeks baris dan kolom}
{ M1(i,j) = M2(i,j) }
function NEQ(M1,M2: MATRIKS) → boolean
{ Mengirimkan true jika not strongEQ(M1,M2) }
function EQSize(M1,M2: MATRIKS) → boolean
{ Mengirimkan true jika ukuran efektif matriks M1 sama dengan}
{ ukuran efektif M2 }
{ yaitu GetBrsEff(M1) = GetNBrsEff (M2) }
{ dan GetNKolEff (M1) = GetNKolEff (M2) }
function "<"(M1,M2: MATRIKS) → boolean
{ Mengirimkan true jika ukutan efektif M1 < Ukuran efektif M2}
{ *** Operasi lain ****}
function NBElmt(M:Matriks) → integer
{ Mengirimkan banyaknya elemen M }
{ ** Kelompok Test terhadap MATRIKS}
function IsBujurSangkar(M:Matriks) → boolean
{Mengirimkan true jika M adalah matriks dg ukuran baris dan kolom
sama}
function IsSymetri (M:Matriks) → boolean
{ Mengirimkan true jika M adalah matriks simetri : IsBujurSangkar(M)
dan untuk setiap elemen M, M(i,j)=M(j,i)}
function IsSatuan(M:Matriks) → boolean
{ Mengirimkan true jika M adalah matriks satuan: IsBujurSangkar(M)
dan Setiap elemen diagonal M bernilai 1 dan elemen yang bukan
diagonal bernilai 0 }
function IsSparse(M:Matriks) → boolean
{ Mengirimkan true jika M adalah matriks sparse: mariks "jarang"
dengan definisi : hanya maksimal 5% dari memori matriks yang efektif
bukan bernilai 0 }
function Invers1(M:Matriks) → MATRIKS
{ Menghasilkan salinan M dg setiap elemen "diinvers" }
{ yaitu dinegasikan}
function Invers(M:Matriks) → MATRIKS
{ Menghasilkan salinan M dg setiap elemen "diinvers" }
{ yaitu di-invers sesuai dengan aturan inversi matriks}
function Determinan → real
{ Menghitung nilai determinan M}
procedure traversalBrs (Input M : MATRIKS)
{ Melakukan traversal terhadap M, per baris}
{ I.S. M terdefinisi}
{F.S. setiap elemen M diproses dengan Proses P(el_type) yang
terdefinisi }
procedure traversalKol (Input M : MATRIKS)
{ Melakukan traversal terhadap M, per kolom per kolom}
{ I.S. M terdefinisi}
{F.S. setiap elemen M diproses dengan Proses P P(el_type) yang
terdefinisi }
procedure Invers1(Input/Output M : MATRIKS)
{ I.S. M terdefinisi }
{ F.S. M diinvers, yaitu setiap elemennya dinegasikan }
procedure Invers(Input/Output M : MATRIKS)
{ I.S. M terdefinisi }
{ F.S. M "di-invers", yaitu diproses sesuai dengan aturan invers
matriks }
procedure Transpose (Input/Output M : MATRIKS)
{ I.S. M terdefinisi, dan IsBujursangkar(M) }
{ F.S. M "di-transpose", yaitu setiap elemen M(i,j) ditukar nilainya
dengan elemen M(j,i)}
Tidak ada komentar:
Posting Komentar