BAB 2 LANDAS AN TEORI
2.1
Teori Simulasi Simulasi yang juga dapat
disebut pengimitasian
adalah
meniru
atau
menggambarkan operasi-operasi yang terjadi pada berbagai macam fasilitas atau proses yang terjadi pada kehidupan nyata dengan menggunakan bantuan komputer (Law dan Kelton, 2000, p1). Fasilitas-fasilitas atau proses-proses yang disebutkan di atas itulah yang dikenal dengan nama sistem. Lebih lengkapnya, sistem adalah kumpulan kesatuan yang bekerja dan berinteraksi bersama-sama menuju hasil akhir yang logis. Dalam simulasi, komputer digunakan sebagai alat bantu untuk mengevaluasi sebuah model secara numerik, dan data-data dikumpulkan untuk mengestimasi karakteristik sesungguhnya dari sebuah model. Secara umum, sistem dapat dipelajari perilakunya dengan menggunakan beberapa metode yang digambarkan pada diagram berikut.
Gambar 2.1 Cara Mempelajari Sistem Sumber: Law, 2000, p4
9 2.2
System Development Life Cycle (SDLC) Rekayasa Piranti Lunak menurut Fritz Bauer (Pressman, 2005, p23) adalah
penetapan dan pemakaian prinsip-prinsip rekayasa dalam rangka mendapatkan piranti lunak yang ekonomis yaitu terpercaya dan bekerja efisien pada mesin (komputer). Dalam membuat sebuah software dikenal istilah Software Development Life Cycle, yaitu serangkaian kegiatan yang dilakukan selama masa perancangan software. Di sini terdapat beberapa model proses, lima diantaranya adalah The Classic Life Cycle atau yang biasa dikenal dengan Waterfall Model, Prototyping Model, Fourth Generation Techniques (4GT), Spiral Model, dan Combine Model. Dalam perancangan program simulasi penyelesaian rubix cube ini digunakan model proses Waterfall Model. M enurut Winston W. Royce (1929–1995), tahapan-tahapan umum dalam Waterfall Model adalah seperti gambar di bawah ini.
Gambar 2.2 Waterfall Model Sumber: http://www.maxwideman.com/papers/plc-models/fig14.gif
10 Tahap-tahap tersebut disusun seperti model aliran air terjun sehingga disebut dengan Waterfall Model. M odel ini menjadi panduan langkah-langkah perancangan dan pembuatan program yang sesuai dengan kebutuhan dan harapan dari pengguna, supaya proyek pengembangan program tersebut dapat diselesaikan dengan sempurna.
2.3
Flowchart Flowchart adalah representasi skematik dari sebuah algoritma atau sebuah proses
yang teratur, menunjukkan langkah-langkah dalam kotak-kotak yang bervariasi dan urutannya dengan menghubungkan kotak-kotak tersebut dengan panah. Flowchart digunakan dalam mendesain atau mendokumentasikan sebuah proses atau program (Wikipedia, 2008). Flowchart pertama kali diperkenalkan oleh Frank Gilbreth kepada anggota ASME (American Society of Mechanical Engineers) pada tahun 1921 sebagai representasi “Process Charts – First Steps in Finding the One Best Way” dan saat ini menjadi alat yang sering digunakan untuk menunjukkan aliran proses dalam suatu algoritma. Sebuah Flowchart pada umumnya memiliki simbol-simbol sebagai berikut. 1. Start and end symbols Direpresentasikan dalam bentuk oval, atau persegi panjang dengan ujung yang membulat, biasanya mengandung kata “Start” atau “End” atau frase lainnya yang menujukkan awal proses atau akhir dari proses, seperti “submit enquiry” atau “receive product”.
11 2. Arrows M enunjukkan apa yang disebut sebagai “flow of control” dalam ilmu komputer. Sebuah arrow datang dari sebuah simbol dan berakhir pada simbol lainnya merepresentasikan bahwa kontrol berpindah pada simbol yang ditunjukkan oleh arrow. 3. Processing steps Direpresentasikan sebagai sebuah persegi panjang. Contoh: “tambahkan 1 pada X”; “ganti bagian yang diidentifikasi”; “simpan data”. 4. Input / Output Direpresentasikan sebagai sebuah jajaran genjang. Contoh: “ambil X dari user”; ”tampilkan X”. 5. Conditional or decision Direpresentasikan sebagai sebuah belah ketupat/bentuk berlian. Biasanya berisi pertanyaan yang mempunyai jawaban “yes” atau “no”, ataupun “true” atau “false”. Simbol ini unik karena ada dua arrows yang keluar dari simbol ini. Biasanya terdapat pada bagian bawah dan kanan, dan berkorespondensi pada jawaban “yes” atau “no”, ataupun “true” atau “false”. Tiap arrow harus diberi label di dalamnya. Lebih dari dua arrows dapat digunakan, tetapi secara normal berarti bagian tersebut dapat dipecah lagi secara lebih mendalam.
12
Gambar 2.3 Flowchart Sumber: http://fishbowl.pastiche.org/archives/pictures/life-lessons-flowchart.png
2.4
Sequence Diagram Sequence Diagram digunakan untuk memodelkan skenario penggunaan
(Hariyanto 2004, p309). Skenario penggunaan adalah barisan kejadian yang terjadi selama satu eksekusi sistem. Cakupan skenario dapat beragam, mulai dari semua kejadian di sistem atau hanya kejadian pada objek-objek tertentu. Skenario menjadi rekaman historis eksekusi sistem atau gagasan eksperimen eksekusi sistem yang diusulkan.
13 Sequence Diagram menunjukkan objek sebagai garis vertikal dan tiap kejadian sebagai panah horizontal dari objek pengirim ke objek penerima. Waktu berlalu dari atas ke bawah dengan lama waktu tidak relevan. Diagram ini hanya menunjukkan barisan kejadian, bukan waktu nyata. Sequence Diagram secara umum digunakan untuk: 1. Overview perilaku sistem, 2. M enunjukkan objek-objek yang diperlukan, 3. M endokumentasikan skenario dari suatu use case diagram, 4. M emeriksa jalur-jalur pengaksesan.
Gambar 2.4 Sequence Diagram Sumber: Whitten, 2004, p441
14 2.5
Aljabar Abstrak Aljabar abstrak adalah salah satu bagian matematika yang mempelajari tentang
struktur aljabar, seperti grup, ring, field, modul, fungsi, dan ruang vektor. Kata aljabar abstrak sekarang mengarah pada pembelajaran dari semua struktur aljabar. Secara khusus struktur aljabar adalah himpunan tak kosong dengan satu komposisi biner atau lebih. Contoh: •
A = {x | x bilangan real} dengan operasi +, (x + y)
A,
(x
A,
y)
x,y x,y
A A
Berikut adalah beberapa notasi yang akan digunakan dalam skripsi ini. Z:
kumpulan bilangan bulat …, -3, -2, -1, 0, 1, 2, 3, …
N:
kumpulan bilangan positif 1, 2, 3, …
Q:
kumpulan bilangan rasional
R:
kumpulan bilangan riil
Z/nZ:
kumpulan integer modulo n
(Z/nZ)x: kumpulan unit modulo n Tujuan dari notasi ini adalah untuk memberi perkenalan tentang teori grup, yang akan digunakan untuk menyelesaikan rubix cube.
15 2.6
Fungsi Fungsi disebut juga sebagai sebuah transformasi dari sebuah domain menuju
sebuah range dengan aturan tertentu (Joyner, 2002, p11). Untuk mengerti keseluruhan dari sebuah rubix cube, pertama-tama akan dijelaskan tentang berbagai sifat fungsi. 1. Sebuah fungsi atau pemetaan f dari sebuah domain D pada sebuah range R (ditulis f : D Æ R) adalah aturan yang diterapkan pada setiap elemen x unik y
D, sebuah elemen
R. Ditulis f(x) = y. Dikatakan bahwa y adalah image dari x dan bahwa x
adalah preimage dari y. Perhatikan bahwa sebuah elemen pada D memiliki tepat satu image, tetapi sebuah elemen dari R bisa saja memiliki 0, 1, atau lebih dari 1 preimage. 2. Sebuah fungsi f : D Æ R disebut fungsi satu-satu jika x1 f(x2) untuk x1, x
2
x2, menyebabkan f(x1)
D. Pada fungsi ini, masing-masing elemen dari R memiliki tepat
satu preimage. 3. Sebuah fungsi f : D Æ R disebut sebagai fungsi onto, jika untuk setiap y terdapat x
R,
D, sehingga f(x) = y. Dengan kata lain, setiap elemen dari R memiliki
paling tidak satu preimage. 4. Sebuah fungsi f : D Æ R disebut sebagai fungsi bijektif, jika fungsi tersebut adalah fungsi satu-satu dan juga merupakan fungsi onto. Dengan kata lain, setiap elemen dari R memiliki tepat satu preimage. 5. Jika diketahui f : S1 Æ S2 dan g : S2 Æ S3, maka dapat didefinisikan sebuah fungsi baru g o f : S1 Æ S3 dengan notasi (g o f)(x) = g(f(x)). Operasi dari o disebut komposisi fungsi.
2.7
Grup
16 Grup adalah suatu sistem atau struktur aljabar yang sederhana yang memenuhi beberapa definisi tertentu (Chen, 2004, p7). Jika suatu himpunan G
dengan suatu
operasi o yang didefinisikan bagi elemen-elemen G, yang bersifat tertutup, asosiatif, mempunyai elemen identitas dan setiap elemen G mempunyai invers terhadap operasi biner tersebut, maka himpunan G terhadap operasi biner itu membentuk suatu grup. Berikut ini adalah beberapa definisi tentang grup. Sebuah grup (G, sebuah set G dan sebuah operasi 1. G tertutup di bawah
) terdiri dari
sehingga:
. Hal ini terjadi jika a, b
G, dan a
b
G.
Contoh : -
Z/4Z adalah tertutup di bawah +; di sini akan ditulis tabel penjumlahan, yang memberitahukan bagaimana menambahkan dua elemen sembarang dari Z/4Z dan mendapatkan elemen lain dari Z/4Z. Sama halnya, (Z/5Z)x adalah tertutup di bawah perkalian.
-
Z adalah tertutup di bawah +: jika a, b juga tertutup di bawah
-
Z, maka a + b
Z. Sama halnya, Z
.
R adalah tertutup di bawah perkalian: jika kita dua bilangan riil dikalikan, akan diperoleh bilangan riil lagi.
-
Kumpulan dari bilangan negatif tidak tertutup di bawah perkalian, karena perkalian dua bilangan negatif tidak akan menghasilkan bilangan negatif lagi.
2.
adalah asosiatif, apabila untuk setiap a, b, c
G, a (b
c) = (a
Contoh: -
Penjumlahan dan perkalian adalah asosiatif.
-
Pengurangan tidak asosiatif karena a – (b – c)
(a – b) – c.
b)
c.
17 3. M emiliki sebuah “elemen identitas” e g
e, untuk semua g
G, yang memenuhi persamaan g = e
g=
G.
Contoh: -
Untuk (Z/4Z,+), 0 adalah elemen identitas karena g = 0 + g = g + 0 untuk setiap g
-
Z/4Z.
Untuk ((Z/5Z)x ,), 1 adalah elemen identitas karena g = 1 setiap g
-
g= g
1 untuk
(Z/5Z)x.
Untuk (Z,+), 0 adalah elemen identitas karena g = 0 + g = g + 0 untuk setiap g Z.
-
Untuk (R, ), 1 adalah elemen identitas karena g = 1
g= g
1 untuk setiap g
R. 4. M emiliki invers, untuk setiap g sedemikian sehingga g
h=h
G, akan memiliki sebuah elemen h
G,
g = e. (h disebut sebagai invers dari g).
Contoh: -
M enggunakan tabel penjumlahan untuk Z/4Z, dapat ditemukan invers dari semua elemen Z/4Z. Dapat dilihat pada tabel bahwa 1 + 3 = 3 + 1 = 0, maka 3 adalah invers dari 1. Dengan kata lain, karena tabel untuk (Z/5Z)x adalah identik, maka semua elemen dari (Z/5Z)x memiliki invers.
-
Untuk (Z,+), invers n
-
Untuk (R, ), tidak semua elemen memiliki invers. 0 tidak memiliki invers. Tetapi apabila x
Z adalah –n karena n + (–n) = (–n) + n = 0.
0, maka
adalah invers dari x karena x
=
Contoh grup sejauh ini memiliki sifat yang spesial: untuk setiap g, h =h
g; karena operasi
x = 1. G, g
h
adalah komutatif. Hal ini tidak berlaku untuk setiap grup. Jika
18 hal tersebut adalah benar untuk (G, ), maka dapat dikatakan bahwa (G, ) adalah abelian. Berikut ini adalah dua sifat penting dari grup. 1. Sebuah grup memiliki tepat satu elemen identitas. Bukti: Sebuah grup (G, ), dan anggap e dan e’ adalah elemen identitas dari G (G mempunyai paling tidak satu elemen identitas dari definisi grup). Lalu, e karena e’ adalah elemen identitas. Di pihak lain, e
e’ = e,
e’ = e’, karena e adalah elemen
identitas. M aka, e = e’ karena masing-masing adalah sama pada e 2. Jika (G, ) adalah sebuah grup, maka masing-masing g
e’.
G memiliki tepat satu
invers. Bukti: Pada g
G, dan anggap g1, g2 adalah invers dari G (paling tidak pada satu
invers dari definisi grup); maka, g Dengan sifat asosiatif, (g1 (g1
g)
g2 = e
g)
g1 = g1
g2 = g1
(g
g = e dan g
g2 = g2
g = e.
g2). Karena g1 adalah invers dari g,
g2 = g2. Karena g2 adalah invers dari g, g1
(g
g2) = g1
e
= g1. M aka, g2 = g1. Secara umum, invers dari g ditulis sebagai g-1. Tetapi, jika diketahui bahwa operasi grup adalah penjumlahan, maka invers dari g ditulis sebagai –g.
Tabel 1.1 Penjumlahan modulo 4 (4Z/Z) Sumber: Chen, 2004, p6 + 0 1 2 3 0 0 1 2 3 1 1 2 3 0 2 2 3 0 1 3 3 0 1 2 Tabel 1.1 adalah tabel penjumlahan modulo 4, yang terdiri dari elemen: 0, 1, 2, dan 3.
19 Selanjutnya akan ditulis tabel 1.2, yang menggunakan simbol
untuk menggantikan
simbol + untuk penjumlahan, dan juga e = 0, a = 1, b = 2, dan c = 3.
Tabel 1.2 Bintang modulo 4 (4Z/Z) Sumber: Chen, 2004, p6
e a b c
e e a b c
a a b c e
b b c e a
c c e a b
Selanjutnya akan dilakukan hal yang sama untuk (Z/5Z)x, yaitu tabel perkalian modulo 5 dengan elemen: 1, 2, 3, dan 4. Tabel 1.3 Perkalian modulo 5 (Z/5Z)x Sumber: Chen, 2004, p6
1 2 4 3
1 1 2 4 3
2 2 4 3 1
4 4 3 1 2
3 3 1 2 4
Selanjutnya akan ditulis tabel 1.4, yang menggunakan simbol simbol
untuk menggantikan
untuk perkalian, dan juga e = 1, a = 2, b = 4, dan c = 3. Tabel 1.4 Bintang modulo 5 (Z/5Z)x Sumber: Chen, 2004, p6
e e e a a b b c c Dapat dilihat bahwa tabel bintang modulo
a b c a b c b c e c e a e a b 4 (Z/4Z) ternyata sama dengan tabel bintang
modulo 5 (Z/5Z)x. Hal ini menunjukkan bahwa pernyataan algebra untuk penjumlahan
20 dari elemen modulo 4 (Z/4Z) dapat ditranslasikan menjadi pernyataan aljabar untuk perkalian dari elemen modulo 5 (Z/4Z)x.
2.8
Rubix Cube dan Subgrup
2.8.1
Notasi kubus Rubix cube terdiri dari 27 kubus kecil, yang disebut dengan “cubies”. 26 dari cubies ini dapat dilihat secara langsung (jika rubix cube dibongkar, maka akan ditemukan bahwa cubie ke-27 tidak ada). Dalam proses penyelesaian sebuah rubix cube, sangatlah penting untuk mempunyai sebuah cara sistematis untuk memberi nama pada masing-masing cubies. Sebenarnya secara alami dapat digunakan warna pada tiap cubies, tetapi akan lebih berguna untuk memberi nama yang dapat menyatakan lokasi untuk tiap cubies. Cubies pada bagian sudut disebut dengan, “corner cubies”. Tiap corner cubies memiliki tiga bagian yang tampak dan berjumlah 8 buah. Cubies dengan dua bagian yang tampak disebut “edge cubies” dan berjumlah 12 buah. Terakhir, cubies yang memiliki satu bagian tampak disebut “center cubies” dan berjumlah 6 buah. Dengan mengikuti notasi yang dikembangkan oleh David Singmaster, keenam sisi dari rubix cube akan dinamakan sebagai berikut: right (r), left (l), up (u), down (d), front (f), dan back (b) (Chen, 2004, p10). Keuntungan dari sistem penamaan ini adalah bahwa setiap sisi dapat dinotasikan dengan satu huruf. Untuk memberi nama sebuah corner cubie, dapat dibuat list sisinya searah jarum jam. Cubie yang berada di bagian upper, right, front corner ditulis sebagai urf, dapat juga ditulis sebagai rfu atau fur.
21 Untuk memberi nama pada edge dan center cubies cukup dibuat list pada sisi cubies yang tampak. Cubie pada bagian center dari front disebut sebagai f, karena hanya itu bagian yang tampak pada bagian depan cube. Juga akan dibicarakan tentang “cubicles”. Cubicles diberi label seperti halnya dengan cubies. M ereka mendeskripsikan ruangan di mana cubie “tinggal”. Apabila sebuah rubix cube berada pada keadaan awal (rubix cube yang telah diselesaikan), maka masing-masing cubie berada pada cubicle dengan nama yang sama (urf cubie tinggal di urf cubicle, f cubie tinggal di f cubicle, dan seterusnya). Jika sisi sebuah rubix cube telah diputar, maka cubicles tidak bergerak, hanya cubie yang bergerak dan tentu saja semua center cubies tetap berada pada cubicles masing-masing. Pergerakan dari rubix cube juga akan diberi nama. Gerakan paling dasar yang dapat dilakukan seseorang adalah memutar sebuah sisi. Digunakan simbol R untuk menotasikan sebuah rotasi searah jarum jam pada sisi sebelah kanan (lihat pada sisi kanan dan putar 90 searah jarum jam). Dengan cara yang sama, akan digunakan huruf kapital L, R, U, D, F, dan B untuk menotasikan putaran searah jarum jam pada sisi yang berkorespondensi. Secara umum, setiap putaran dari keenam sisi ini adalah sebuah “gerakan” pada rubix cube. M erotasi sisi kanan berlawanan arah jarum jam adalah sebuah gerakan yang sama dengan melakukan R sebanyak tiga kali. Telah diobservasi bahwa 6 gerakan dasar akan tetap menempatkan center cubies pada cubicles-nya. Karena setiap gerakan adalah rangkaian dari keenam gerakan dasar tersebut, maka setiap gerakan dari rubix cube akan tetap menempatkan center cubies pada cubicles masing-masing. Setiap gerakan dari
22 rubix cube juga akan menempatkan corner cubies pada corner cubicles, dan edge cubies pada edge cubicles; adalah mustahil untuk sebuah corner cubie untuk tinggal pada sebuah edge cubicle dan sebaliknya. M enggunakan dua fakta berikut, dapat diperkirakan berapa banyak konfigurasi yang dimiliki oleh sebuah rubix cube. Pada cubicle urf, secara teori maka kedelapan corner cubies dapat tinggal pada cubicle tersebut. Hal ini menyebabkan 7 corner cubies dapat tinggal pada cubicle urb, menyebabkan 6 corner sisanya dapat menempati cubicle lainnya, dan seterusnya. M aka, terdapat 8
7
6
5
4
3
2
1 = 8!
kemungkinan penempatan dari corner cubies. Perhatikan bahwa sebuah corner cubie dapat menempati cubicle-nya dengan 3 cara berbeda. Apabila sebuah cubie berwarna merah, putih, dan biru tinggal pada urf cubicle, maka warna merah, putih, ataupun biru dapat berada pada sisi u dari cubicle tersebut (hal ini juga menunjukkan letak 2 sisi lainnya). Karena terdapat 8 corner cubies dan masingmasing dapat menempati cubicle-nya dengan 3 cara berbeda, maka terdapat 38 cara untuk menempatkan corner cubies. Jadi, dapat dilihat bahwa terdapat 38 8! konfigurasi yang mungkin untuk corner cubies. Dengan cara yang sama, karena pada rubix cube terdapat 12 edge cubies, maka terdapat 12! posisi dari edge cubies; masing-masing edge cubies memiliki 2 kemungkinan orientasi, hal ini memberikan 212 kemungkinan untuk penempatan. Jadi, terdapat 212 posisi yang berbeda untuk edge cubies, dan memberikan total sebesar 212 8!
12! 38
12! kemungkinan untuk konfigurasi sebuah rubix cube (sekitar 5.19 x 1020). Biarpun konfigurasi tersebut secara teori adalah mungkin, tetapi tidak
berarti bahwa konfigurasi tersebut dapat benar-benar terjadi. Dapat dikatakan bahwa sebuah konfigurasi dari rubix cube adalah valid, apabila dapat dicapai
23 dengan rangkaian gerakan, dimulai dari konfigurasi awal (rubix cube yang telah diselesaikan).
2.8.2
Membuat Rubix Cube Menjadi Sebuah Grup Dapat dibuat set dari gerakan rubix cube menjadi sebuah grup, yang dinotasikan dengan (G, ). Elemen-elemen dari G akan menjadi semua gerakan yang mungkin pada sebuah rubix cube (sebagai contoh, satu gerakan yang mungkin adalah sebuah rotasi searah jarum jam pada sisi atas, diikuti oleh sebuah rotasi berlawanan arah jarum jam pada sisi kanan). Dua gerakan juga dapat disebut sama apabila menghasilkan konfigurasi yang sama (sebagai contoh, memutar sebuah sisi sebesar 180
searah jarum jam adalah sama dengan
memutar sebuah sisi yang sama sebesar 180
berlawanan jarum jam). Operasi
dari grup akan didefinisikan sebagai berikut: jika M1 dan M2 adalah dua gerakan, maka M2
M1 adalah gerakan di mana M1 dilakukan terlebih dahulu, dan
kemudian M2.
Hal ini disebut sebagai grup karena memenuhi 4 definisi dari grup sebagai berikut. 1. G adalah tertutup di bawah maka M1
, karena apabila M1 dan M2 adalah gerakan,
M2 adalah gerakan juga.
2. Jika e adalah gerakan “kosong” (gerakan yang tidak membuat perubahan pada konfigurasi rubix cube sama sekali), maka M
e berarti “pertama
lakukan M dan kemudian tidak melakukan apa-apa”. Hal ini adalah sama
24 dengan melakukan M saja, sehingga M
e = M. Jadi, (G, ) memiliki
elemen identitas. 3. Jika M adalah sebuah gerakan, maka kebalikan langkah tersebut adalah sebuah gerakan M’. Lalu, gerakan M’
M berarti “pertama lakukan gerakan
M, dan kemudian balikkan kembali gerakan dari M”. Hal ini adalah sama dengan tidak melakukan apa-apa, jadi M’
M = e, sehingga M’ adalah
invers dari M. Jadi, hal ini membuktikan bahwa semua elemen dari G memiliki invers. 4. Perlu diperhatikan bahwa sebuah gerakan dapat didefinisikan oleh perubahan yang disebabkannya pada konfigurasi. Secara khusus, sebuah gerakan ditentukan oleh posisi dan orientasi yang ditempatkan oleh gerakan tersebut untuk masing-masing cubie. Jika C adalah cubie yang berorientasi, dapat dituliskan M(C) untuk cubicle yang berorientasi dan menyebabkan C berakhir pada cubicle tersebut setelah dilakukan gerakan M, dengan sisi dari M(C) tertulis dengan urutan yang sama dengan sisi dari C. Sisi pertama dari C seharusnya berakhir pada sisi dari M(C) dan seterusnya. Sebagai contoh, gerakan R menempatkan cubie ur pada cubicle br, dengan sisi u dari cubie terletak pada sisi b dari cubicle dan sisi r dari cubie terletak pada sisi r dari cubicle. M aka dapat ditulis R(ur) = br. Jika M1 dan M2 adalah dua gerakan, maka M2
M1 adalah gerakan di mana
dilakukan M1 terlebih dahulu kemudian dilakukan M 2. Gerakan M1 menggerakkan
C
pada
cubicle
M1(C);
gerakan
M2
kemudian
menggerakkannya pada cubicle M2(M1(C)). Jadi, (M2 M1)(C) = M2(M1(C)).
25 Dari persamaan tersebut, dapat dilihat bahwa [(M3 M3([M2
(M2
M1)](C) =
M1])(C)) = M3(M2(M1(C))). Sedangkan untuk [(M3
M1](C) = (M3 Jadi, (M3
M2)
M2)(M1(C)) = M3(M2(M1(C))).
M2)
M 1 = M3
(M2
M1). Hal ini membuktikan
adalah
asosiatif. Jadi, (G, ) adalah sebuah grup.
2.8.3
Subgrup Telah dikalkulasi sebelumnya bahwa terdapat 5.19 x 1020 kemungkinan pada sebuah rubix cube (biarpun tidak semuanya valid). Karena itu, masalah akan dibatasi dengan melihat gerakan-gerakan yang hanya meliputi rotasi dari sisi bawah dan kanan. Hal ini adalah filosofi umum dari teori grup: untuk mengerti sebuah grup G, haruslah dimulai dari bagian-bagian kecilnya. Subgrup adalah sebuah subset dari grup G yang juga merupakan suatu grup (Joyner, 2002, p77).
Berikut ini adalah beberapa definisi dari subgrup. •
Sebuah subset H tak kosong dari sebuah grup (G, ) disebut sebagai subgrup dari G apabila (H, ) adalah sebuah grup. Hal ini hanya berlaku apabila untuk setiap a, b
H, a
b-1
H. H, maka b-1
Bukti: Anggap H adalah sebuah subgrup. Jika b (H, ) adalah sebuah grup. Jadi, jika a
H, maka a
Sebaliknya, dianggap bahwa untuk setiap a, b -
Pertama,
H, a
b-1 b-1
H. H.
adalah asosiatif karena (G, ) adalah sebuah grup.
H karena
26 H. Karena, a-1
-
Anggap a
-
Jika b
-
Anggap a, b-1
H, maka, b-1
H maka e
H.
H. Ini membuktikan H memiliki invers.
H. Karena (b-1)-1
H atau b
H, maka a
b
H.
Ini membuktikan bahwa H adalah tertutup di bawah . Langkah-langkah di atas menunjukkan bahwa (H, ) adalah sebuah grup, yang berarti H adalah subgrup dari G.
2.8.4
Menyederhanakan Notasi Grup Dalam skripsi ini, operasi grup akan ditulis sebagai perkalian; dituliskan gh untuk menggantikan g
h, dan akan disebut sebagai “produk” dari g dan h.
Kalimat “anggap G adalah grup” berarti bahwa G adalah sebuah grup di bawah sebuah operasi yang akan ditulis sebagai perkalian. Elemen identitas dari G ditulis sebagai 1, bukan e. Digunakan juga notasi eksponensial umum, yang berarti g2 berarti gg, g3 berarti ggg, dan seterusnya. Lebih lanjut, perhitungan akan dilakukan dengan menggunakan (G, ), sehingga untuk seterusnya disebut sebagai grup G, dan operasinya ditulis sebagai perkalian. Contohnya, RD berarti gerakan D diikuti oleh gerakan R. Gerakan yang memutar sisi kanan berlawanan arah jarum jam sebesar 90
adalah sama
dengan sebuah gerakan memutar sisi kanan searah jarum jam sebanyak tiga kali, dan dapat ditulis sebagai R3.
2.9
Grup S imetris Telah dikalkulasikan banyak kemungkinan konfigurasi yang mungkin pada
sebuah rubix cube, dan digunakan fakta bahwa semua gerakan akan menempatkan
27 corner cubies pada corner cubicles untuk mendapatkan 8! kemungkinan untuk memposisikan corner cubies. Pada bagian ini akan dijelaskan dasar matematika untuk mengerti lebih lanjut tentang kemungkinan-kemungkinan tersebut. Daripada hanya melihat pada konfigurasi dari kedelapan cubies, akan lebih baik apabila hanya dilihat konfigurasi dari sembarang objek n. Objek tersebut akan disebut sebagai 1, 2, …, n. Lalu dipikirkan untuk menyusun objek tersebut seperti menempatkan mereka pada n slots. Jika slot tersebut disebut sebagai 1, 2, …, n. M aka dapat didefinisikan sebuah fungsi
: {1, 2, …, n} Æ {1, 2, …, n} dengan notasi
(i) berarti
angka yang diletakkan pada slot i. Berikut ini adalah beberapa definisi dari grup simetris. 1.
adalah bijektif.
2. Grup simetris pada huruf n adalah set bijektif dari {1, 2, …, n} pada {1, 2, …, n} dengan operasi komposisi. Grup ini ditulis sebagai Sn.
2.10
Gerakan Rubix Cube M asing-masing gerakan dari rubix cube dapat ditulis menggunakan notasi cycle
yang dimodifikasi sedikit. Akan dijelaskan apa yang terjadi pada masing-masing cubie yang berorientasi; yaitu ke arah mana masing-masing cubie bergerak dan di mana masing-masing sisi dari cubie bergerak. Sebagai contoh, jika bagian bawah rubix cube dilepas dan digambarkan, maka akan terlihat seperti berikut.
28
Gambar 2.5 Bagian Bawah Rubix Cube Sumber: Chen, 2004, p18
Lalu apabila sisi ini dirotasikan sebesar 90
(gerakan D), maka sisi tersebut akan
terlihat seperti berikut.
Gambar 2.6 Bagian Bawah Rubix Cube S etelah Rotasi Gerakan D Sumber: Chen, 2004, p18
Jadi, D(dlf) = dfr karena cubie dlf sekarang tinggal dalam cubicle dfr (dengan sisi d dari cubie berada pada sisi d pada cubicle, sisi l dari cubie berada pada sisi f pada cubicle, dan sisi f dari cubie berada pada sisi r pada cubicle). Dengan kata lain, D(dfr) = drb, D(drb) = dbl, dan D(dbl) = dlf. Jika dilakukan hal yang sama pada edge cubies, maka akan diperoleh D = (dlf dfr drb dbl) (df dr db dl).
2.11
Konfigurasi Rubix Cube Konfigurasi dari sebuah rubix cube ditentukan oleh empat buah data berikut.
1. Posisi dari corner cubies.
29 dari S8 (elemen dari S8 yang
Hal ini dapat dijelaskan dengan sebuah elemen
menggerakkan corner cubies dari posisi awal ke posisi baru). 2. Posisi dari edge cubies. Hal ini dapat dijelaskan dengan sebuah elemen
dari S12.
3. Orientasi dari corner cubies. Pada dasarnya hal ini adalah bagaimana memperbaiki “orientasi awal” dan cara yang sistematis untuk menuliskan bagaimana sebuah orientasi yang diberikan dapat berbeda dengan orientasi awal. 4. Orientasi dari edge cubies. Sama seperti di atas, hal ini hanyalah masalah notasi.
Sebagai permulaan, akan dimulai dengan corner cubies. M asing-masing corner cubies memiliki 3 kemungkinan orientasi, dan orientasi tersebut akan disebut dengan bilangan 0, 1, dan 2. Bayangkan sebuah rubix cube pada konfigurasi awal, lalu akan dituliskan sebuah angka pada sebuah sisi wajah pada masing-masing corner cubicle, seperti berikut ini. 1 untuk sisi u pada cubicle ufl 2 untuk sisi u pada cubicle urf 3 untuk sisi u pada cubicle ubr 4 untuk sisi u pada cubicle ulb 5 untuk sisi d pada cubicle dbl 6 untuk sisi d pada cubicle dlf 7 untuk sisi d pada cubicle dfr
30 8 untuk sisi d pada cubicle drb
Jadi, masing-mas ing corner cubicle sekarang memiliki sebuah sisi yang bertuliskan sebuah angka. M asing-masing corner cubie memiliki sebuah sisi yang terdapat pada corner cubicle yang telah dituliskan angka. Akan diberikan label 0 pada cubie ini. M asih pada cubie yang sama, akan diberikan label 1 pada sisi cubie yang berada searah jarum jam dari label 0, dan kemudian sisi terakhir diberi label 2.
Gambar 2.7 Contoh Pemberian Label Pada Cubicle Untuk Sisi D Sumber: Chen, 2004, p20
Gambar 2.8 Contoh Pemberian Label Pada Cubie Untuk S isi D Sumber: Chen, 2004, p20 Sekarang, masing-masing sisi pada corner cubie mempunyai nomor. Jika rubix cube berada pada konfigurasi sembarang, maka orientasinya akan dapat dideskripsikan sebagai berikut. Untuk sembarang i antara 1 dan 8, temukan sisi cubicle yang memiliki label i, anggap xi adalah angka sisi cubie yang tinggal pada sisi cubicle. Ditulis x untuk 8-tuple yang berurutan (x1, …, x 8). Perhatikan bahwa masing-masing x i dapat dilihat
31 sebagai perhitungan angka dari rotasi searah jarum jam yang merotasi cubie i menjauhi sisi 0 untuk sisi yang memiliki angka pada cubicle. Sebuah cubie yang berjarak 3 putaran diorientasikan melalui cara yang sama dengan cubie yang berjarak 0 putaran. Jadi, xi dapat dilihat sebagai elemen-elemen dari Z/3Z. M aka, x adalah sebuah 8-tuple dari elemen-elemen Z/3Z; dapat ditulis sebagai x
(Z/3Z)8.
Berikutnya, hal yang sama akan dilakukan untuk edge cubies. Pertama-tama, diberikan label pada edge cubicles seperti berikut. 1 untuk sisi u pada cubicle ub 2 untuk sisi u pada cubicle ur 3 untuk sisi u pada cubicle uf 4 untuk sisi u pada cubicle ul 5 untuk sisi u pada cubicle lb 6 untuk sisi u pada cubicle rb 7 untuk sisi u pada cubicle rf 8 untuk sisi u pada cubicle lf 9 untuk sisi u pada cubicle db 10 untuk sisi u pada cubicle dr 11 untuk sisi u pada cubicle dr 12 untuk sisi u pada cubicle dl M asing-masing edge cubie sekarang mempunyai sebuah sisi yang berada pada sisi cubicle yang memiliki angka; cubie ini diberi label 0, dan sisi lain yang tidak memiliki angka diberi label 1. Kemudian, anggap yi adalah angka dari sisi cubie pada sisi cubicle yang memiliki nomor i. Hal ini mendefisikan y
(Z/2Z)12. M aka,
32 konfigurasi apapun pada rubix cube dapat dideskripsikan sebagai (Z/3Z)8, dan y
S12, x
(Z/2Z)12. Jadi, konfigurasi dari rubix cube dapat ditulis sebagai 4-
tuples yang berurutan ( ,
2.12
S8,
, x, y).
Group Actions Apabila dalam sebuah rubix cube terdapat konfigurasi C = (
melakukan sebuah gerakan M
,
, x, y), maka
G menempatkan rubix cube pada sebuah konfiguras i
baru. Konfigurasi baru ini dapat ditulis sebagai M
C.
Anggap bahwa rubix cube dimulai pada konfigurasi C. Jika dilakukan gerakan M1, konfigurasi dari rubix cube akan menjadi M1 maka konfigurasi akan menjadi M2
(M1
C. Jika dilakukan gerakan lain M2,
C). Dengan kata lain, dimulai dengan
konfigurasi C dan dilakukan gerakan M2M1, jadi cara lain untuk menulis konfigurasi baru adalah (M2M1)
C. Jadi, telah ditunjukkan bahwa M2
untuk setiap konfigurasi C dan setiap gerakan M2M1
(M1
C) = (M2M1)
C
G.
Jika dilakukan gerakan kosong (elemen identitas e pada G), maka konfigurasi tidak berubah sama sekali, maka e
C = C.
Hal ini adalah contoh dari sebuah objek matematika yang disebut “group actions”. Elemen-elemen dari sebuah grup (elemen di sini adalah gerakan pada rubix cube) mempengaruhi elemen-elemen pada suatu set (set dari konfigurasi rubix cube) (Chen, 2004, p32). Sebelumnya group actions juga telah digunakan; contohnya, untuk mengerti Sn, telah dipelajari bagaimana elemen-elemen pada Sn dapat mempengaruhi integers 1, …, n.
33 Untuk memberikan definisi yang formal, diperlukan suatu notasi. Jika S1 dan S2 adakah dua sets, maka S1 S1 dan s2
S2 adalah set dari pasangan yang berurutan (s1, s2) dengan s1
S2. Berikut ini beberapa definisi dari group actions.
1. Sebuah group actions (kanan) pada sebuah grup (G, ) pada sebuah set A (tak G Æ A (diberikan a
kosong) adalah sebuah pemetaan A
dihasilkan elemen lain dari A, yang ditulis sebagai g
A dan g
G, dapat
a) memenuhi dua sifat
berikut. -
g2
-
e
(g1
a) = (g2
a = a, untuk a
g1)
a untuk setiap g1, g2
G dan a
A.
A (e adalah elemen identitas dari G).
Hal ini lebih merupakan aksi kanan daripada aksi kiri karena elemen-elemen grup diletakkan di kanan. Pada kondisi pertama, g1 Sebaliknya, g2g1
a
A, sehingga g2
G, sehingga (g1g2)
(g1
a) adalah mungkin.
a juga adalah mungkin.
Apabila dimiliki sebuah group actions dari G pada sebuah set A, cukup dikatakan sebagai “G beraksi pada A.” 2. Jika G beraksi pada A, maka orbit pada a {g
a:g
A (di bawah aksi ini) adalah sebuah set
G}.
3. Jika sebuah group actions hanya memiliki sebuah orbit, dikatakan bahwa aksi tersebut adalah transitif (atau grup beraksi secara transitif). 4. Anggap bahwa sebuah grup berhingga G beraksi pada A, dan anggap S adalah sebuah set pada generators dari G. Anggap P adalah properti sehingga pernyataan berikut adalah benar: Apabila a
A memenuhi P dan s
S, a
s juga memenuhi P.
34 M aka, jika ao
A memenuhi P, semua elemen pada orbit dari ao juga akan
memenuhi P. Pada kasus sebuah rubix cube, definisi di atas akan diaplikasikan pada aksi dari grup G pada sebuah konfigurasi set A. Secara khusus, jika S = {D, U, L, R, F, B} dan ao adalah konfigurasi awal, maka definisi di atas dapat digunakan untuk membuktikan semua konfigurasi yang valid pada sebuah rubix cube. Sebelumnya, telah dikalkulasikan bahwa terdapat 212
38
8!
12! banyak
kemungkinan dari konfigurasi sebuah rubix cube; definisi-definisi di atas menunjukkan bahwa hanya
2.13
yang valid.
Metode Layer David Singmaster
2.13.1 Notasi David Singmaster David Singmaster menggunakan notasi-notasi berikut untuk menganalisis gerakan dari rubix cube. Berikut ini notasi yang dipakai. •
U, untuk sisi atas;
•
F, untuk sisi depan / muka;
•
D, untuk sisi bawah;
•
B, untuk sisi belakang;
•
L, untuk sisi kiri;
•
R, untuk sisi kanan;
•
X, untuk merotasi rubix cube dengan poros sisi kanan [r]..
•
Y, untuk merotasi rubix cube dengan poros sisi atas [u].
•
Z, untuk merotasi rubix cube dengan posisi sisi depan [f].
35
Gambar 2.9 Notasi Rubix Cube Sumber: http://www.scribd.com/word/full/5454?access_key=kweoq34x08dx7
2.13.2 Operasi David Singmaster Apabila posisi awal telah ditentukan, di sini akan ditetapkan operasi rotasi yang akan menjaga orientasi dari pusat kubus. •
U, berarti memutar 90o sisi atas kubus searah jarum jam.
•
U2, berarti memutar 180o sisi atas kubus searah jarum jam. (U2 = UU).
•
o 3 U’, berarti memutar 90 sisi atas kubus berlawanan arah jarum jam. (U =
UUU).
Gambar 2.10 Operasi U untuk Rubix Cube Sumber: S napp, 2005, p4 •
o F, berarti memutar 90 sisi depan kubus searah jarum jam.
•
F2, berarti memutar 180o sisi depan kubus searah jarum jam. (F2 = FF).
•
o 3 F’, berarti memutar 90 sisi depan kubus berlawanan arah jarum jam. (F =
FFF).
36
Gambar 2.11 Operasi F untuk Rubix Cube Sumber: S napp, 2005, p5
•
D, berarti memutar 90o sisi bawah kubus searah jarum jam.
•
D2, berarti memutar 180o sisi bawah kubus searah jarum jam. (D2 = DD).
•
D’, berarti memutar 90o sisi bawah kubus berlawanan arah jarum jam. (D3 = DDD).
Gambar 2.12 Operasi D untuk Rubix Cube Sumber: S napp, 2005, p6
•
o B, berarti memutar 90 sisi belakang kubus searah jarum jam.
•
2 o 2 B , berarti memutar 180 sisi belakang kubus searah jarum jam. (B = BB).
•
B’, berarti memutar 90o sisi belakang kubus berlawanan arah jarum jam. (B3 = BBB).
Gambar 2.13 Operasi B untuk Rubix Cube
37 Sumber: S napp, 2005, p7
•
L, berarti memutar 90o sisi kiri kubus searah jarum jam.
•
L2, berarti memutar 180o sisi kiri kubus searah jarum jam. (L2 = LL).
•
o 3 L’, berarti memutar 90 sisi kiri kubus berlawanan arah jarum jam. (L =
LLL).
Gambar 2.14 Operasi L untuk Rubix Cube Sumber: S napp, 2005, p8
•
R, berarti memutar 90o sisi kanan kubus searah jarum jam.
•
R2, berarti memutar 180o sisi kanan kubus searah jarum jam. (R2 = RR).
•
R’, berarti memutar 90o sisi kanan kubus berlawanan arah jarum jam. (R3 = RRR).
Gambar 2.15 Operasi R untuk Rubix Cube Sumber: S napp, 2005, p9 2.13.3 Cross Layer Lebih dikenal sebagai tanda plus, dapat dibuat secara intuitif. Berikut ini langkah-langkah dalam menyelesaikan tahap dasar ini.
38 1. Pilih sebuah warna untuk sisi atas (misalnya hijau), dan sebuah warna untuk sisi depan (misalnya merah). 2. Identifikasikan kubus yang berada pada sisi atas (uf), misalnya edge hijaumerah. 3. Jika warna dari rusuk uf harus diputar, lakukan salah satu dari algoritma berikut. a. Warna depan-bawah menjadi atas-depan: D’L’F L. b. Warna depan-atas menjadi atas-depan: F U’ R U. c. Warna depan-kanan menjadi atas-depan: U’ R U. d. Warna depan-kiri menjadi atas-depan: U L’ U’.
Gambar 2.16 Tahap Akhir Cross Layer Sumber: S napp, 2005, p11
2.13.4 Top Layer Pada tahap ini, sisi atas telah selesai sebagian. Bagian yang perlu untuk dikerjakan berikutnya adalah keempat corner. Di sini diperlukan 3 gerakan pada umumnya. Algoritma yang digunakan tergantung dari posisi warna yang diinginkan untuk berada di atas. Pastikan bahwa cubie yang ingin ditempatkan pada urf berada pada drf. Lalu, samakan warna dari bagian bawah yang mempunyai warna pada bagian atas dan lakukan algoritma berikut, apabila: 1. Warna terdapat pada bagian kanan: R’D’R.
39 2. Warna terdapat pada bagian depan: F D F’. 3. Warna terdapat pada bagian bawah: R’ D’ R D (3 kali)
Gambar 2.17 Tahap Akhir Top Layer Sumber: S napp, 2005, p14
2.13.5 Middle Layer Pada tahap ini, terkadang sisi pertama yang telah selesai harus dirombak lagi untuk membuat sisi yang kedua. Pada dasarnya yang kita lakukan di sini adalah langkah yang sama untuk setiap sisi kubus. Putar sisi bawah sampai salah satu dari bagian tengah kepingan menyatu dengan bagian tengah dari edge yang terdapat pada sisi tengah. Apabila semua telah sama dengan kepingan di tengah, lakukan algoritma berikut, apabila: 1. Kepingan harus berada di sisi kiri pada layer kedua: F D F D F D’ F‘ D’ F’ D’. 2. Kepingan harus berada di sisi kanan pada layer kedua: F’ D’ F’ D’ F’ D F D F D. 3. Apabila tidak terdapat sisi bawah yang sama dengan sisi tengah, atau sisi yang terdapat di tengah tertukar, lakukan salah satu algoritma di atas.
40
Gambar 2.18 Tahap Akhir Middle Layer Sumber: S napp, 2005, p18
2.13.6 Last Layer Cross Pada tahap ini hanya dibutuhkan sebuah algoritma. Untuk melakukan cross ini, pertama-tama lihat pada 3 kemungkinan yang akan terjadi pada layer terakhir. 1. Telah terjadi sebuah cross. 2. Dua edge yang berlawanan tertukar. 3. Dua edge yang berhadapan tertukar. Untuk kasus yang terjadi, pastikan edge yang tertukar berada di depan, dan edge lainnya berada di kiri atau di belakang. Kemudian lakukan algoritma ini: F D L D’ L’ F’. Lakukan algoritma tersebut sebanyak dua kali apabila edge yang berlawanan tertukar (depan dan belakang).
41 Gambar 2.19 Tahap Akhir Last Layer Cross Sumber: S napp, 2005, p20
2.13.7 Carrou sel Edges Pada tahap ini, pertama-tama lakukan [F2] sehingga last layer cross terdapat di posisi atas. Di sini akan terdapat beberapa kategori sebagai berikut. 1. Tidak ada edges yang tertukar. 2. Tiga edges tertukar, pertahankan edge yang telah selesai di depan. Lihat kasus yang terjadi. a. Edges harus diputar searah jarum jam. Apabila terjadi kasus a, lakukan algoritma: R U2 R’ U’ R U’ R’. b. Edges harus diputar berlawanan arah jarum jam. Apabila terjadi kasus b, lakukan algoritma: R U R’ U R U2 R’. 3. Empat edges tertukar dalam pasangan yang berlawanan, lihat kasus c. Lakukan algoritma yang sebelumnya, dan akan terjadi tiga sudut tertukar.
Gambar 2.20 Beberapa Kasus Carrou sel Edges Sumber: Harris, 2008, p31
42
Gambar 2.21 Tahap Akhir Carrousel Edges Sumber: S napp, 2005, p25
2.13.7 Rotate Corners Pada langkah ini hanya dibutuhkan sebuah algoritma. Beberapa kasus yang mungkin adalah seperti berikut. 1. Semua sudut telah terisi sempurna. Rubix cube telah selesai. 2. Tempatkan corner yang belum selesai di bagian urb. Lakukan algoritma: R D R’ D’. Lakukan gerakan U untuk menempatkan corner lainnya di bagian urb, sampai warna yang berada di depan atau di samping berada di atas.
Gambar 2.22 Tahap Akhir Rotate Corners Sumber: S napp, 2005, p21
2.13.8 Swap Corners
43 Tahap terakhir pada metode David Singmaster. Di sini akan terjadi beberapa kategori seperti berikut. 1. Tidak ada corner yang tertukar. Rubix cube telah selesai dengan sempurna. 2. Terdapat tiga corner yang tertukar. Pertahankan corner yang selesai pada sudut kiri atas (ulf), dan perhatikan kasus yang terjadi a. Corners harus diputar searah jarum jam. Apabila terjadi kasus a, lakukan algoritma: R’ D2 R U2 R’ D2 R U’ R’ D2 R U’ R’ D2 R. b. Corners harus diputar berlawanan arah jarum jam. Apabila terjadi kasus b, lakukan algoritma: R’ D2 R U R’ D2 R U R’ D2 R U2 R’ D2 R. 3. Semua corner tertukar seperti terlihat pada kasus c dan d. Lakukan algoritma di atas sampai terjadi tiga corner tertukar. Alternatifnya, perhatikan algoritma berikut.
a. Corners yang berhadapan tertukar. Apabila terjadi kasus c, lakukan algoritma: R’ D2 R U’ R’ D2 R U R’ D2 R U R’ D2 R U R’ D2 R U’ R’ D2 R. b. Corners yang bersilangan tertukar. Apabila terjadi kasus d, lakukan algoritma: R’ D2 R U2 R’ D2 R U2 R’ D2 R U R’ D2 R U2 R’ D2 R U2 R’ D2 R.
44 Gambar 2.23 Beberapa Kasus Swap Corners Sumber: Harris, 2008, p34
Gambar 2.24 Tahap Akhir Swap Corners Sumber: S napp, 2005, p22
