SEMINAR NASIONAL MATEMATIKA DAN PENDIDIKAN MATEMATIKA UNY 2015 T - 41
Konstruksi Super Matriks Simetris Persegi Latin Hendra Kartika Program Studi Pendidikan Matematika, Universitas Singaperbangsa Karawang, Jln. H.S. Ronggowaluyo Telukjambe Timur, Karawang-Jawa Barat 41361
[email protected]
Abstrak—Beberapa literatur menjelaskan bahwa ada beberapa cara untuk mengkontruksi matriks persegi latin, tetapi implementasi tentang super matriks simetris persegi latin masih sedikit. Selain itu, telah dilakukan penelitian mengenai algoritma untuk mengkonstruksi super matriks simetris persegi latin dengan orde 2n. Namun, dalam penelitian ini, diusulkan kembali suatu algoritma yang berbeda untuk mengkonstruksi super matriks simetris persegi latin. Tujuannya adalah untuk mengembangkan kajian-kajian baru serta terapan tentang matriks persegi latin dalam bidang kombinatorik, teori design, statistika dan ilmu komputer. Dalam penelitian ini, metode yang digunakan untuk merancang algoritma adalah model alur proses. Sedangkan software yang digunakan dalam penelitian ini adalah Matlab. Dari plot grafik yang terbentuk, diperoleh gambaran grafik yang berbeda dengan pola yang sangat unik khususnya untuk orde n ≥ 6. Kata kunci: persegi latin, super matriks simetris.
I. PENDAHULUAN Beberapa literatur menjelaskan bahwa ada beberapa cara untuk mengkonstruksi matriks persegi latin, tetapi implementasi tentang super matriks simetris persegi latin masih sedikit [3]. Selain itu, telah dilakukan kajian mengenai algoritma untuk mengkonstruksi super matriks simetris persegi latin dengan orde 2n. Namun, dari kajian algoritma yang dilakukan peneliti, terdapat perbedaan langkah-langkah pengerjaan dalam mengkonstruksi super matriks simetris persegi latin. Dari output yang dihasilkan, diperoleh gambaran grafik yang berbeda dengan pola yang sangat unik khususnya untuk orde n ≥ 6. Dalam penelitian ini, diusulkan kembali tentang bagaimana cara untuk mengkonstruksi super matriks simetris persegi latin menggunakan algoritma yang diusulkan. Dari penelitian ini, diharapkan adanya kajian-kajian baru serta terapan tentang matriks persegi latin dalam bidang kombinatorik, teori design, statistika dan ilmu komputer.
II. METODE PENELITIAN Metode yang digunakan dalam penelitian ini adalah model alur proses yang digambarkan dengan diagram alur berikut: Mengkaji teori tentang super matriks simetris persegi latin
Membuat Pertanyaan Penelitian
463
Desain Algoritma
ISBN. 978-602-73403-0-5
Terjemahkan ke Bahasa Matlab
Cek Hasil
Ya
Sesuai dengan teori?
Implementasi Hasil
Tidak Perbaikan
GAMBAR 1. DIAGRAM ALUR PROSES PENELITIAN
Software yang digunakan dalam penelitian ini adalah Matlab versi 7.12.0 (R2011a). Software ini digunakan untuk memudahkan dalam proses perhitungan serta kehandalannya dalam mengolah fungsi matriks, khususnya untuk orde yang sangat besar.
III. HASIL DAN PEMBAHASAN Definisi 1: Matriks persegi latin Matriks persegi latin adalah matriks berukuran n × n yang memuat n simbol yang berbeda sedemikian sehingga setiap simbol tepat muncul satu kali pada baris dan tepat muncul satu kali pada kolom [1]. Simbol yang dimaksud dalam definisi tersebut dapat berupa angka, huruf dan gambar. Definisi 2: Super Matriks Simetris Matriks persegi latin disebut super matriks simetris, jika permutasi dari semua elemen bersesuaian dengan sifat matriks persegi latin. Selain itu, jika dua garis ditarik dan saling berpotongan secara diagonal, membentuk 4 segitiga yang simetri [3]. Berikut ini merupakan beberapa contoh dari super matriks simetris persegi latin. Contoh 1: Super matriks simetris orde 2,
0 1 1 0 Contoh 2: Super matriks simetris orde 4,
1 0 3 2
0 1 2 3
3 2 1 0
2 3 0 1
Contoh 3: Super matriks simetris orde 6,
2 0 1 4 5 3
1 2 0 5 3 4
0 1 2 3 4 5
4 5 3 2 0 1
5 3 4 1 2 0
3 4 5 0 1 2
464
SEMINAR NASIONAL MATEMATIKA DAN PENDIDIKAN MATEMATIKA UNY 2015
Super matriks simetris disebut juga sebagai matriks blok yang memuat sub-sub matriks persegi latin dengan ai,j = aj,i untuk i, j=1, 2,..., n. Pada penelitian ini, super matriks simetris yang akan dikonstruksi menggunakan 4 blok matriks persegi latin. Secara umum dapat dituliskan sebagai berikut:
a1,1 A a 2,1
a1, 2 a 2, 2
a) Langkah-Langkah Algoritma yang Diusulkan 1) Membangkitkan dua buah blok matriks persegi latin. Unsur-unsur pada blok matriks yang pertama merupakan permutasi dari nilai 0, 1, ..., n-1. Unsur pada diagonal kanan, mempunyai nilai yang sama, sedemikian hingga d1,1=d2,2=...=dn,n. Sedangkan unsur-unsur pada blok matriks yang kedua merupakan permutasi dari nilai n, n+1, ..., 2n-1, unsur pada diagonal kiri, mempunyai nilai yang sama, sedemikian hingga d1,n=d2,n-1=...=dn,1. Misal,
2 Blok Matriks 1 0 1 4 Blok Matriks 2 5 3 2)
1 0 2 1 , 0 2 5 3 3 4 . 4 5
Selanjutnya, Blok Matriks 1=a1,1 sedangkan Blok Matriks 2=a1,2. Sedemikian hingga,
2 1 0 2 1 0 A a 2,1
0 4 1 5 2 3
5 3 4 a 2, 2
3 4 5
3) Kemudian, blok matriks a2,1 dan blok matriks a2,2 didapat dari dua blok matriks secara menyilang,
2 1 0 2 1 0 A a 2,1
0 4 1 5 2 3
5 3 4 a 2, 2
3 4 5
2 0 1 A 4 5 3
1 2 0 5 3 4
0 1 2 3 4 5
4 5 3 2 0 1
5 3 4 1 2 0
3 4 5 0 1 2
b) Pseudocode dari Implementasi Algoritma Input dari algoritma ini adalah orde blok, sedangkan outputnya adalah super matriks simetris persegi latin A=[ai,j]n×n. Pseudocode dari algoritma yang diusulkan merupakan pengembangan dari pseudocode algoritma persegi latin [2]. Berikut ini merupakan pseudocode dari implementasi algoritma yang diusulkan:
465
ISBN. 978-602-73403-0-5
SUPER_SIMETRIS_LATIN(orde_blok, A)
h orde _ blok 1
for i
to orde_blok do for j to orde_blok do M[i,j] i+j*h-1 mod orde_blok return M for i to orde_blok do for j to orde_blok do N[i,j] (i+j-1 mod orde_blok) + orde_blok return N
Blok _ Matriks1 M Blok _ Matriks2 N
Blok _ Matriks1 Blok _ Matriks2 A Blok _ Matriks2 Blok _ Matriks1 GAMBAR 2. PSEUDOCODE DARI IMPLEMENTASI ALGORITMA YANG DIUSULKAN
function Large=latin(orde_blok) clc; h=orde_blok-1; for i=1:orde_blok for j=1:orde_blok M(i,j)=mod((i+j*h-1),orde_blok); end; end; for i=1:orde_blok for j=1:orde_blok N(i,j)=mod((i+j-1),orde_blok)+orde_blok; end; end; BlokMatriks1=M BlokMatriks2=N Large=[M N;N M]; plot(Large)
GAMBAR 3. PSEUDOCODE ALGORITMA DALAM BENTUK FUNGSI MATLAB
c) Output Berikut ini merupakan output yang dihasilkan setelah pseudocode dari algoritma diterjemahkan ke dalam bahasa Matlab.
466
SEMINAR NASIONAL MATEMATIKA DAN PENDIDIKAN MATEMATIKA UNY 2015
GAMBAR 4. GENERATE SUPER MATRIKS SIMETRIS ORDE 4
GAMBAR 6. GENERATE SUPER MATRIKS MATRIKS SIMETRIS ORDE 6
GAMBAR 5. PLOT GRAFIK SUPER MATRIKS SIMETRIS ORDE 4
GAMBAR 7. PLOT GRAFIK SUPER MATRIKS SIMETRIS ORDE 6
467
ISBN. 978-602-73403-0-5
IV. SIMPULAN DAN SARAN Hasil dari implementasi algoritma yang diusulkan setelah dilihat dari output Matlab yang dihasilkan sudah mendukung teori tentang super matriks simetris persegi latin. Dari plot grafik yang terbentuk, diperoleh gambaran grafik dengan pola yang sangat unik khususnya untuk orde n ≥ 6. Untuk penelitian selanjutnya, diperlukan adanya kajian-kajian baru serta terapan tentang matriks persegi latin dalam bidang kombinatorik, teori design, statistika dan ilmu komputer. DAFTAR PUSTAKA [1]
Evans, A.B., “A class of Orthogonal Latin Square Graphs,” Australian Journal of Combinatorics, vol. 57, pp. 189-216, 2013.
[2]
Ivanyi, A., Nemeth, Z., “List coloring of Latin and Sudoku graphs,” 8th Joint Conf. on Math. and Comp. Sci. Slovakia: Comarno, 2010, pp. 1-11.
[3]
M.A.P. Chamikara, S.R. Kodituwaku, A.A.C.A. Jayathilake, A.A.I. Perera, “An Algorithm to Construct SuperSymmetric Latin Squares of Order 2n,” IJRIT International Journal of Research in Information Technology, Vol.1, Issue 4, pp. 38-50, April 2013.
468