BAB 2 LANDASAN TEORI
2.1
Algoritma
2.1.1
Definisi Algoritma Secara umum algoritma adalah urutan logis langkah-langkah penyelesaian
masalah yang disusun secara sistematis [Rinaldi Munir, 2005, p.175]. Kata algoritma sebenarnya berasal dari kata Algorism yang pertama kali diungkapkan oleh Abu Ja’far Mohammad Ibn Musa Al Khowarizmi dalam buku Al-jabr w’almulqabala . Kata algorism pertama kali dimaksudkan sebagai aturan dalam melakukan fungsi aritmatika menggunakan Hindu-Arab numerik. Dengan penerjemahaan Eropa Latin maka kata yang diberikan oleh Al Khowarizmi menjadi algorithm dalam bahasa Inggris pada abad ke-18. Kata itu berkembang menjadi arti prosedur pasti untuk memecahkan masalah atau melakukan suatu pekerjaan. Kata algorithm akhirnya diterjemahkan ke dalam bahasa Indonesia menjadi algoritma.
2.1.2
Langkah Dasar Membangun Algoritma Menurut Drs. Saulus Silitonga, MSc (1990, p.1), ada beberapa langkah dasar
yang perlu diikuti untuk membangun suatu algoritma, antara lain sebagai berikut. a. Pernyataan masalah b. Membangun model dari masalah c. Merancang algoritma dari model
8
d. Menguji kebenaran algoritma e. Implementasikan dengan suatu bahasa pemrograman yang dimengerti oleh user f. Dokumentasi g. Analisis kompleksitas algoritma
Meskipun
algoritma
sesungguhnya dalam
sering
dikaitkan
dengan
ilmu
komputer,
kehidupan sehari-haripun banyak terdapat
proses
namun yang
digambarkan dalam suatu algoritma. Misalnya resep membuat masakan Rendang Padang berikut ini: 1. Potong daging sapi menjadi potongan-potongan dadu atau sesuai selera. 2. Haluskan bumbu berupa bawang merah, bawang putih, cabe merah, kunyit, laos, dan jahe. 3. Masukkan seluruh bumbu yang sudah dihaluskan ke dalam santan. Tambahkan dua buah daun jeruk, satu lembar daun kunyit, dan sebatang serai. 4. Masak santan di atas api sedang. Aduk terus hingga santan mendidih. 5. Masukkan daging sapi, dan kecilkan api. Sesekali santan diaduk agar tidak pecah. 6. Jika sudah timbul minyak dan santan sudah kering, matikan api. Rendang siap untuk dihidangkan.
9
Contoh-contoh algoritma yang lain dalam kehidupan sehari-hari misalnya pola pakaian, panduan praktikum, papan not balok, dan pengisian voucher ditunjukkan pada tabel 2.1 di bawah ini. Tabel 2.1 Contoh-contoh Algoritma dalam Kehidupan sehari-hari (Sumber: Rinaldi Munir, 2005, p.176) Proses Algoritma Contoh Langkah dalam Algoritma 1. Membuat kue Resep kue Masukkan telur ke dalam wajan, kocok sampai mengembang, dst. 2. Membuat pakaian Pola pakaian Gunting kain dari pinggir kiri bawah ke arah kanan sejauh 5 cm, dst. 3. Praktikum reaksi kimia Panduan praktikum Campurkan 10 ml H 2 SO4 dengan 15 ml NaOH, dst. 4. Merakit mobil Panduan merakit Sambungkan komponen A dengan komponen B, dst. 5. Kegiatan sehari-hari Jadwal harian Pukul 15.00 : tidur siang, pukul 16.00 : membuat PR, dst. 6. Memainkan musik Papan not balok Not balok 7. Mengisi voucher kartu Panduan pengisian Tekan nomor 888 prabayar telepon genggam Masukkan 14 digit nomor (HP) voucher, dst
2.2
Optimisasi
2.2.1
Definisi Optimisasi Optimisasi ialah suatu proses untuk mencapai hasil yang ideal atau optimal (nilai
efektif yang dapat dicapai) [Ibnu Sina Wardy, 2008, p.2]. Dalam matematika, istilah optimisasi berkaitan erat
dengan masalah pencarian nilai minimum atau nilai
maksimum dari fungsi riil dengan memilih nilai dari variabel secara sistematis dari himpunan yang ada. Masalah ini dapat direpresentasikan sebagai berikut.
10
Diberikan sebuah fungsi f : A → R dari himpunan bilangan A ke himpunan bilangan riil. Akan dicari x 0 dari himpunan A dimana:
f( x 0 ) ≤ f(x) untuk semua x pada A, untuk proses minimalisasi
f( x 0 ) ≥ f(x) untuk semua x pada A, untuk proses maksimalisasi.
Secara khusus, A adalah himpunan bagian dari dimensi Euclid R n . Pada A terdapat beberapa kendala berupa persamaan atau pertidaksamaan yang harus dipenuhi oleh anggota himpunan A. Domain dari himpunan A disebut daerah asal dan elemenelemen dari himpunan A disebut solusi kandidat atau feasible solution. Fungsi f disebut objective function atau cost function. 2.2.2
Macam-Macam Permasalahan Optimisasi Persoalan yang berkaitan dengan optimisasi sangat kompleks dalam kehidupan
sehari-hari. Nilai optimal yang didapat dalam optimisasi dapat berupa besaran panjang, waktu, jarak, dan lain-lain. Berikut ini adalah beberapa persoalan yang memerlukan optimisasi: a. Menentukan lintasan terpendek dari suatu tempat ke tempat yang lain. b. Menentukan jumlah pekerja seminimal mungkin untuk melakukan suatu proses produksi agar pengeluaran biaya pekerja dapat diminimalkan dan hasil produksi tetap maksimal. c. Mengatur jalur kendaraan umum agar semua lokasi dapat dijangkau. d. Mengatur routing jaringan kabel telepon agar biaya pemasangan kabel tidak terlalu besar dan penggunaannya tidak boros.
11
2.3
Teori Graf
2.3.1
Pengenalan Teori Graf Teori graf adalah cabang ilmu yang mempelajari sifat-sifat graf, yang pertama
kali diperkenalkan pada tahun 1736. Baru pada sekitar tahun 1920 teori graf berkembang pesat terutama di bidang ilmu komputer, kimia, bahasa, ekonomi, dan riset operasi.
Gambar 2.1 Jembatan utama di Königsberg (Sumber: Rinaldi Munir, 2005, p.355) Menurut catatan sejarah, masalah jembatan Königsberg adalah masalah yang pertama kali menggunakan graf (tahun 1739) [Rinaldi Munir, 2005, p.354]. Di kota Königsberg (sebelah timur negara bagian Prussia, Jerman), sekarang bernama kota Kaliningrad, terdapat sungai Pregal yang mengalir mengitari Pulau Kneiphof lalu bercabang menjadi dua buah anak sungai yang diperlihatkan oleh gambar 2.1. Permasalahannya ialah menemukan pejalanan atau rute dari suatu kota melalui ketujuh buah jembatan masing-masing tepat satu kali, kemudian kembali lagi ke tempat awal. Pulau tersebut tidak dapat dicapai oleh rute apapun selain melalui jembatan-jembatan tersebut.
12
Tahun 1736, Leonhard Euler adalah orang pertama yang berhasil menemukan jawaban masalah tersebut dengan pembuktian yang sederhana (melalui karya tulisannya Seven Bridges of Königsberg). Daratan (titik-titik yang dihubungkan oleh jembatan) dinyatakan sebagai titik disebut verteks dan jembatan dinyatakan sebagai edge. Dari analisa Euler pada jembatan Königsberg menghasilkan sebuah model graf, seperti yang diperlihatkan pada gambar 2.2. Analisis Euler mengenai permasalahan jembatan di Königsberg tidak menghasilkan solusi. Karena orang tidak mungkin melalui ketujuh jembatan masing-masing tepat satu kali dan kembali lagi ke tempat awal keberangkatan jika derajat (banyaknya garis yang bersisian dengan titik) setiap verteks tidak seluruhnya genap. Penemuan Euler adalah kunci yang menandai perkembangan topologi, di mana perbedaan antara layout sebenarnya dan graf scematic adalah contoh yang bagus untuk gagasan bahwa topologi tidak dibatasi dengan bentuk kaku dari objek-objek tertentu. C
A
D
B
Gambar 2.2 Graf yang merepresentasikan jembatan Königsberg (Sumber: Rinaldi Munir, 2005, p.355) 2.3.2
Definisi Graf Graf adalah pasangan himpunan (V,E), ditulis dengan notasi G(V,E), yang dalam
hal ini. i.
V adalah himpunan tidak kosong dari simpul-simpul (titik/verteks/node).
ii.
E adalah himpunan sisi (rusuk/edge) yang menghubungkan sepasang simpul.
13
Simpul-simpul pada graf dapat merupakan obyek sembarang seperti kota, atomatom suatu zat, nama anak, jenis buah, komponen alat elektronik dan sebagainya. Busur dapat menunjukkan hubungan (relasi) sembarang seperti rute penerbangan, jalan raya, sambungan telepon, ikatan kimia, dan lain-lain. Notasi graf: G(V,E) artinya graf G memiliki verteks V dan rusuk E.
2.3.3
Jenis-Jenis Graf Graf dapat dikelompokkan menjadi beberapa kategori (jenis) bergantung pada sudut
pandang pengelompokkannya. Pengelompokkan graf dapat dipandang berdasarkan ada tidaknya sisi ganda atau sisi kalang, berdasarkan jumlah simpul, atau berdasarkan orientasi arah pada sisi. Berdasarkan ada tidaknya gelang atau sisi ganda pada suatu graf, maka secara umum graf dapat digolongkan menjadi dua jenis:
1. Graf Sederhana (simple graph) Graf yang tidak mengandung gelang maupun sisi ganda dinamakan graf sederhana. Pada Gambar 2.3 adalah contoh graf sederhana. Pada graf sederhana, sisi adalah pasangan tak-terurut (unordered pairs). Jadi, menuliskan sisi (u,v) sama saja dengan (v,u). Graf sederhana G = (V,E) terdiri dari himpunan tidak kosong simpul-simpul dan E adalah himpunan pasangan tak-terurut yang berbeda disebut sisi.
14
G1 1
2
3
4
Gambar 2.3 Graf sederhana (Sumber: Rinaldi Munir, 2005, p.356)
2. Graf tak-sederhana Graf yang mengandung sisi ganda atau gelang dinamakan graf tak-sederhana (umsimple graph). Ada dua macam graf tak sederhana, yaitu graf ganda (multigraph) dan graf semu (pseudograph). Graf ganda adalah graf yang mengandung sisi ganda. Graf ganda G = (V,E) terdiri dari himpunan tidak kosong simpu-simpul dan E adalah himpunan-ganda (multiset) yang mengandung sisi ganda. Sedangkan graf semu adalah graf yang mengandung gelang (loop). (b) G3
(a) G2 1
1
e4
e1
e2
2
3
e3 e2
2
e6
e5
e4
e1
e3
e6
e5
e7 4
3
e8
e7 4
Gambar 2.4 Dua buah graf (a) graf ganda dan (b) graf semu (Sumber: Rinaldi Munir, 2005, p.356) Sisi pada graf dapat mempunyai orientasi arah. Berdasarkan orientasi arah pada sisi, maka secara umum graf dibedakan menjadi 2 jenis:
15
1.
Graf tak-berarah (undirected graph) Graf yang sisinya tidak mempunyai orientasi arah disebut graf tak-berarah. Pada graf tak-berarah, urutan pasangan simpul yang dihubungkan oleh sisi tidak diperhatikan. Jadi, (u,v) = (v,u) adalah sisi yang sama. G1 1
2
3
4
Gambar 2.5 Graf tak-berarah (undirected graph) (Sumber: Rinaldi Munir, 2005, p.356) 2.
Graf berarah (directed graph) Graf yang setiap sisinya diberikan orientasi arah disebut sebagai graf berarah. Pada graf berarah, (u,v) dan (v,u) adalah dua busur yang berbeda. Untuk busur (u,v), simpul u dinamakan simpul asal (initial vertex) dan simpul v dinamakan simpul terminal (terminal vertex). G4 1
e1
e4
e3
e2
2
3
e6
e5
e7 4
Gambar 2.6 Graf berarah (directed graph) (Sumber: Rinaldi Munir, 2005, p.359)
16
2.3.4
Representasi Graf Misalkan G adalah sebuah graf dengan verteks-verteks v1, v2, …, vn dan edge e1,
e2, …, en maka didefinisikan dua macam matriks yang berhubungan dengan sebuah graf G [Seymour Lipschutz, 1985, p.87]. 1. Matriks adjacency Misalkan A=(aij) adalah matriks m x n yang didefinisikan oleh:
1 jika {u, v} adalah edge, yaitu vi adjacent terhadap vj aij 0 lainnya 2. Matriks incident Misalkan M=(mij) adalah matriks m x i didefinisikan oleh:
1 verteks vi adalah incident pada edge ei lainnya m 0 Contoh: Diketahui graf G: e5 v1
e2 e1
v2
e3
v5 e6 e7
e4
e8 v3 1
maka:
v4
17
v1 v2 v3 v4 v5
e1 e2 e3 e4 e5 e6 e7 e8
v1 0 v2 1 A v3 1 v4 1 v5 1
v1 1 1 1 0 1 0 0 0 1 1 1 1 v2 1 0 0 1 0 0 0 0 0 1 0 0 m v3 0 0 1 1 0 0 1 1 1 0 1 1 v4 0 0 0 0 1 1 0 1 0 1 0 1 v5 0 1 0 0 0 1 1 0 0 1 1 0 (a) (b) Gambar 2.7 matriks adjecency (a) dan matriks incidence (b) (Sumber: Seymour Lipschutz, 1985, p.87)
2.4
Teori Lintasan dan Siklus Misalkan 𝑣0 dan 𝑣𝑛 adalah verteks-verteks dalam sebuah graf [Richard
Johnsonbaugh, 2002, p.12]. Sebuah lintasan dari 𝑣0 ke 𝑣𝑛 dengan panjang n adalah sebuah barisan berselang-seling dari (n+1) verteks dan n rusuk yang berawal dengan verteks 𝑣0 dan berakhir dengan verteks 𝑣𝑛 , (𝑣0 , 𝑒1 , 𝑣1 , 𝑒2 , 𝑣2 , ... , 𝑣𝑛−1 , 𝑒𝑛 , 𝑣𝑛 ), dengan rusuk 𝑒𝑖 insiden pada verteks 𝑣𝑖−1 dan 𝑣𝑖 untuk i = 1,2,...,n. Sebuah siklus adalah sebuah lintasan yang mempunyai panjang lintasan tidak nol dari kota pertama sampai kota terakhir yang merupakan kota pertama juga pada suatu graf. Dalam hal ini tidak terdapat rusuk yang dilalui lebih dari sekali. Sebuah siklus sederhana adalah siklus dari kota pertama sampai kota terakhir yang merupakan kota terakhir juga pada suatu graf. Kecuali kota pertama dan kota terakhir yang keduanya sama, tidak terdapat node yang dilalui lebih dari sekali.
18
Untuk mengamati perbedaan antara lintasan, siklus, siklus sederhana, dapat diperhatikann contoh graf pada gambar 2.7 di bawah yang akan disajikan dalam bentuk tabel. Tabel 2.2 Perbedaan Lintasan, Siklus, dan Siklus Sederhana (Sumber: Richard Johnsonbaugh, 2002, p.276) LINTASAN
LINTASAN SEDERHANA
SIKLUS
SIKLUS SEDERHANA
Tidak
Tidak
Tidak
Ya
Tidak
Tidak
(2, 6, 5, 2, 4, 3, 2)
Tidak
Ya
Tidak
(5, 6, 2, 5)
Tidak
Ya
Ya
Ya
Tidak
Tidak
(6, 5, 2, 4, 3, 2, 1) (6, 5, 2, 4)
(7)
Gambar 2.8 Sebuah graf yang tidak berarah (Sumber: Richard Johnsonbaugh, 2002, p.274)
2.5
Siklus Hamilton (Hamiltonian Cycle) Sebuah graf G = (V,E) yang merupakan sebuah graf yang terhubung dengan n
node, dikatakan sebagai sebuah Hamiltonian Cycle jika dapat membentuk suatu jalur yang melalui n buah rusuk pada G dan mengunjungi setiap node hanya satu kali lalu kembali ke node awal. Dengan kata lain sebuah graf adalah Hamiltonian Cycle jika dimulai dari suatu node 𝑣𝑖
G dan semua node dalam G dikunjungi dengan urutan 𝑣1 ,
𝑣2 , ..., 𝑣𝑛+1 . Rusuk-rusuk yang menghubungkan verteks-verteks tersebut merupakan
19
anggota E dalam G, pada i ≤ i ≤ n dan semua 𝑣𝑖 berbeda kecuali 𝑣1 dan 𝑣𝑛 +1 yang merupakan node yang sama. Sir William Rowan Hamilton mencetuskan sebuah teka-teki pada pertengahan tahun 1800-an dalam bentuk sebuah dodecahedron (lihat Gambar 2.8). Masing-masing sudut yang berjumlah 20 tersebut diberi nama sebuah kota dan masalahnya berawal dari sembarang kota, kemudian menjalani rusuk-rusuk, mengunjungi setiap kota tepat satu kali, dan kembali ke kota semula. Siklus dalam graf G yang mengandung setiap verteks di G tepat satu kali, kecuali verteks awal dan akhir yang muncul dua kali disebut siklus Hamilton (Hamiltonian Cycle). Pada gambar 2.6 diperlihatkan sebuah contoh graf yang mempunyai siklus Hamilton. Pada gambar 2.9 diperlihatkan contoh graf yang diselesaikan sesuai teka-teki Hamilton di mana siklus dalam graf G mengandung setiap verteks tepat satu kali (kecuali verteks awal dan akhir yang muncul dua kali).
Gambar 2.9 Sebuah graf yang mempunyai siklus Hamilton (sumber: Richard Johnsonbaugh, 2002, p.286)
20
Gambar 2.10 (a) Teka-teki Hamilton, (b) Pemodelan Dodecahedron dalam graf, (c) Salah satu penyelesaian berbentuk siklus Hamilton (sumber: Richard Johnsonbaugh, 2002, p.285) 2.6
Travelling Salesman Problem Travelling Salesman Problem (TSP) adalah permasalahan pada metematika
diskrit dan optimalisasi kombinatorial yang berhubungan dengan permasalahan dalam menemukan satu siklus hamiltonian dalam suatu grafik [Richard Johnsonbaugh, 2002, p.287]. TSP pertama kali dikemukakan pada tahun 1800-an oleh seorang matematikawan asal Irlandia, Sir William Hamilton dan seorang matematikawan asal Inggris, Thomas Penyngton Kirkman. Bentuk umum dari TSP pertama dipelajari oleh para matematikawan mulai tahun 1930. Diawali oleh Karl Menger di Vienna dan Harvard. Setelah itu permasalahan TSP dipublikasikan oleh Hasler Whitney dan Merrill Flood di Princeton. Penelitian secara rinci mengenai hubungan anatara penemuan Menger dan Whitney, serta perkembangan TSP dapat ditemukan dalam makalah Alexander Schrijver “On the history of combinatorial optimization (till 1960)”. TSP memerlukan keputusan dari siklus biaya minimal, yang melalui setiap simpul pada graf yang relevan. Jika biaya bersifat simetris, yakni jika biaya antar dua lokasi tidak tergantung pada arah lintasan, maka TSP jenis ini bersifat simetris, sedangkan dalam hal lain bersifat asimetris, yang disebut TSP berarah.
21
Solusi-solusi dari berbagai metode dianalisis dan setiap n buah simpul memerlukan sejumlah waktu f(n). Besaran f(n) fungsi waktu dari sebuah metode terhadap jumlah kota n. Untuk membandingkan dua buah metode, cukup dibandingkan fungsi f(n) dari masing-masing metode. Suatu metode mungkin baik tetapi analisisnya buruk, sehingga menghasilkan f(n) yang buruk. Dalam banyak permasalahan komputasi, studi tentang algoritma dan fungsi telah menghasilkan solusi matematika yang sangat bagus, yang penting dalam penyelesaian permasalahan praktis. Hal ini telah menjadi subjek studi yang utama dalam sains komputer. Untuk setiap masalah TSP fungsi f(n)-nya adalah (n-1)! = (n-1) (n-2) (n3)...(3),(2),(1) dan jumlah jalur yang mungkin tejadi adalah (n-1)!/2. Hasil yang lebih baik ditemukan pada tahun 1962 oleh Michael Held dan
Richard Karp, yang
menemukan algoritma dan fungsi yang mempunyai f(n) = n 2 2 n , yaitu n ...
n
2
2
2. Untuk setiap n bernilai besar, fungsi f(n) Held-Karp akan selalu lebih kecil
dibandingkan (n-1)!
2.7
Vehicle Routing Problem Vehicle Routing Problem (VRP) adalah permasalahan dari combinatorial
optimization di mana sebuah set rute akan dibentuk dari sejumlah kota atau pelanggan didasarkan atas satu atau beberapa depot. Setiap kota atau pelanggan akan dilayani oleh satu kendaraan dengan batasan-batasan tertentu, rute tersebut di awali dan diakhiri di depot [http://neo.lcc.uma.es/radi-aeb/WebVRP].
22
Vehicle Routing Problem pertama kali diformulasikan oleh Dantzig dan Ramser pada tahun 1959 sebagai masalah utama dalam bidang transportasi, distribusi, dan logistik. Dalam sektor perdagangan, transportasi yang baik berarti semakin baiknya daya jual dari suatu barang. Selanjutnya dikembangkan metode komputerisasi untuk transportasi yang menghasilkan penghematan yang signifikan dari total biaya.
Gambar 2.11 Contoh visualisasi input dari Vehicle Routing Problem (Sumber: http://neo.lcc.uma.es/radi-aeb/WebVRP/)
Gambar 2.12 Salah satu output dari persoalan VRP dari input gambar 2.11 (Sumber: http://neo.lcc.uma.es/radi-aeb/WebVRP/)
23
Vehicle Routing Problem bertujuan untuk meminimalkan jarak yang dilalui oleh armada kendaraan yang melayani sekumpulan pelanggan seperti pada gambar 2.9 dan menghasilkan beberapa rute sesuai jumlah kendaraan seperti pada gambar 2.10. Kasus ini sama dengan Travelling Salesman Problem (TSP), hanya saja Travelling Salesman Problem hanya memiliki satu rute, di mana perbaikan rute dilakukan dalam satu rute itu sendiri, sedangkan dalam Vehicle Routing Problem memiliki banyak rute yang jumlahnya sesuai kendaraan yang akan dipakai. Tujuan keduanya sama yaitu untuk mencari jarak minimum dengan melewati semua node sebanyak satu kali. Pada perkembangannya, VRP memiliki beberapa karakteristik sehingga dapat dibagi-bagi dalam beberapa kategori masalah, seperti yang dapat ditunjukkan dalam tabel 2.3. Kategori ini dibuat oleh Bodin dan
Golden (1981), yang memaparkan
berbagai karakteristik umum, yang akan membedakan VRP. Keseluruhan tabel memberikan gambaran singkat tentang masalah routing. Tabel 2.3 Kategori masalah dalam VRP (sumber: Titiporn Thammapimookkul, 2001, p16) NO 1 2
3
KARAKTERISTIK Jumlah kendaraan Pengangkut Tipe kendaraan Pengangkut
4
Tempat asal kendaraan (pusat) Tipe permintaan
5
Lokasi permintaan
6
Jaringan yang mendasari
VARIAN YANG MUNGKIN Satu kendaraan pengangkut Multi kendaraan pengangkut Homogen (satu tipe kendaraan pengangkut) Heterogen ( multi tipe kendaraan pengangkut) Tipe khusus Satu pusat Multi pusat Permintaan deterministik Permintaan stokastik Permintaan kepuasan sebagian Simpul Garis Campuran Tidak berarah Berarah Campuran Euclid
24
7
2.8
8
Batasan kapasitas kendaraan Pengangkut Rute maksimum
9
Sistem pengoperasian
10
Biaya
11
Tujuan
Semuanya sama Jalur yang berbeda Kapasitas tak terbatas Sama untuk semua rute Berbeda untuk setiap rute Tidak ditentukan Pengambilan saja Pengiriman saja Pengambilan dan pengiriman Variabel atau biaya rute Biaya tetap pengoperasian atau biaya tetap kendaraan Pengangkut Biaya pengangkutan umum Meminimalkan biaya total rute Meminimalkan jumlah kendaraan pengangkut yang Diperlukan Meminimalkan fungsi kegunaan bedasarkan pada pelayanan dan kenyamanan Meminimalkan fungsi kegunaan bedasarkan pada prioritas pelanggan
Teknik-Teknik Penyelesaian VRP Ada beberapa teknik penyelesaian VRP, antara lain sebagai berikut. 1. Dynamic Programming Dynamic Programming adalah suatu metoda yang dapat digunakan jika solusi suatu persoalan (problem) dapat dipandang sebagai hasil dari sederetan keputusan [Drs. Saulus Silitonga, MSc, 1990, p.78]. Untuk menyelesaikan masalah yang besar, dilakukan pemecahan masalah tersebut menjadi bagianbagian kecil yang serupa dan independen di mana bagian-bagian tersebut dapat dipecahkan dengan metode yang serupa dengan masalah induk. Setelah bagianbagian kecil tersebut diselesaikan maka hasil-hasil yang diperoleh digabung kembali dengan suatu metode tertentu untuk memberikan solusi yang sebenarnya pada masalah tersebut.
25
2. Branch and Bound Pendekatan branch and bound terdiri dari dua prosedur dasar. Branching adalah proses mempartisi masalah yang besar menjadi dua atau lebih masalah kecil dan bounding adalah proses menghitung batas bawah pada solusi optimal dari masalah kecil tersebut. Bounding function yang digunakan yaitu, pemrosesan hanya dilakukan pada branch yang baik dan branch yang buruk tidak akan diproses dengan harapan branch yang baik akan memberikan hasil yang optimal dalam proses selanjutnya. 3. Branch and Cut Pendekatan branch and cut merupakan pendekatan yang menggunakan branch and bound dengan penambahan algoritma pemotongan atau cutting pada solusi yang didapatkan. Proses yang dilakukan adalah dengan mengaplikasikan branch and bound pada masalah yang akan menghasilkan suatu solusi yang nantinya akan dipotong dengan algoritma tertentu untuk mendapatkan hasil yang lebih baik. Proses tersebut akan diulangi sampai tidak ada pemotongan lagi. 4. Nearest Neighbour Algoritma ini merupakan salah satu dari algoritma pertama yang diterapkan pada masalah pencarian jalur dengan menghubungkan node-node yang mempunyai jarak terpendek dari posisinya sekarang. 5. Farthest Insertion
Algoritma ini hampir sama dengan algoritma nearest neighbour dengan perbedaan pada penghubungan node-node yang mempunyai jarak terjauh dari posisinya sekarang.
26
6.
Local Search Local search (LS) ialah metaheuristik untuk menyelesaikan permasalahan perhitungan optimisasi yang berat. LS dapat digunakan pada permasalahan yang bertujuan memaksimalkan solusi yang standar di antara banyaknya kandidat solusi [http://en.wikipedia.org/wiki/Local_search_(optimization)]. Algoritma LS berpindah dari solusi ke solusi dalam kandidat solusi sampai dianggap solusi tersebut optimal. Algoritma LS dipergunakan secara luas untuk permasalahan perhitungan yang berat, meliputi permasalahan computer science (artificial intelligence), matematika, operations research, engineering, and bioinformatics. Dalam algoritma LS yang paling dasar, dilakukan penyelusuran dalam neighborhood terhadap perjalanan tertentu untuk kemajuan perjalanan. Jika perjalanan tersebut ditemukan maka rute tersebut menggantikan yang lama dan proses tersebut akan diteruskan sampai kemajuan perjalanan tidak dapat ditemukan lagi.
7. 2-Opt 2-Opt ialah algoritma LS yang pertama kali diusulkan oleh Croes pada tahun 1958 untuk menyeleseikan TSP. Ide dasar dibelakang algoritma tersebut ialah memindahkan mengembalikan
atau
menghapus suatu
pasangan perjalanan
[http://en.wikipedia.org/wiki/2-opt].
rute
yang yang
bersilangan
dan
memungkinkan
27
8. 3-Opt Analisis 3-Opt meliputi penghapusan tiga edge dalam perjalanan, kemudian menghubungkan kembali perjalanan tersebut ke dalam perjalanan yang memungkinkan dan kemudian mengevaluasi tiap metode pengembalian untuk mencari yang paling optimum. Proses ini kemudian diulang untuk set tiga set koneksi yang berbeda [http://en. wikipedia.org/wiki/3-opt]. 9. Particle Swarm Optimization (PSO) Particle Swarm Optimization (PSO) merupakan teknik komputasi heuristik berbasis populasi paralel yang diajukan oleh Kennedy dan Eberhart (Kennedy dan Eberhart 1995), yang dimotivasi dari perilaku organisme seperti kumpulan ikan atau burung. Misalkan ada sejumlah burung yang sedang mencari makanan di sebuah daerah secara acak. Di daerah tersebut hanya ada satu potong makanan. Semua burung tidak tahu di mana makanan tersebut berada. Tetapi mereka tahu seberapa jauh makanan tersebut. Jadi strategi yang baik untuk menemukan makanan tersebut adalah dengan mengikuti posisi burung yang terdekat dengan makanan. 10. Simulated Annealing Simulated Annealing (SA) merupakan algoritma heuristik untuk masalah optimalisasi global. SA bekerja berdasarkan proses annealing. Annealing adalah teknik dalam metalurgi yang menyangkut pemanasan dan pendinginan yang terkontrol dari suatu material untuk meningkatkan ukuran dari kristal dan mengurangi kekurangannya. Panasnya menyebabkan atom-atom berpindah dari posisi mereka semula dan bergerak secara acak menuju energi yang lebih tinggi.
28
Pendinginannya yang lambat memberikan mereka kesempatan untuk mencari konfigurasi dengan energi yang lebih rendah dari sebelumnya. Dengan kata lain, setiap langkah dari algoritma SA menukarkan solusi yang ada sekarang dengan solusi acak lain yang dekat. Karena perbedaan nilai fungsi yang bersangkutan dan temperatur global, maka suhu akan turun secara bertahap. 11. Harmony Search Harmony search (HS) ialah algoritma metaheuristic (algoritma soft computing atau
algoritma
evolusioner)
meniru
proses
improvisasi
musisi
[http://en.wikipedia.org/wiki/Harmony_search]. Setiap musisi memainkan nada untuk mencari harmoni yang terbaik bersama-sama, sama seperti setiap variabel keputusan dalam proses optimasi memiliki nilai untuk menemukan vektor terbaik serentak. HS mencoba mencari vektor x yang meminimalkan beberapa pengeluaran fungsi. 12. Ant Colony System Algoritma Ant Colony Optimization (ACO) atau Algoritma Semut merupakan teknik probabilistik untuk menjawab masalah komputasi yang bisa dikurangi dengan menemukan jalur yang baik dengan graf. Sesuai dengan nama algoritmanya, ACO di inspirasi oleh koloni semut karena tingkah laku semut yang menarik ketika mencari makanan [Heitor S. Lopes et al., 2005, p.2]. Secara alamiah koloni semut mampu menemukan rute terpendek dalam perjalanan dari sarang ke tempat-tempat sumber makanan. Koloni semut dapat menemukan rute terpendek antara sarang dan sumber makanan berdasarkan jejak kaki pada lintasan yang telah dilalui. Dalam dunia nyata, semut mencari jalan secara acak,
29
menemukan makanan, dan kembali ke sarang sambil meninggalkan jejak pheromone. Jika semut lain menemukan jalur tersebut, maka mereka tidak akan berjalan secara acak lagi tetapi mulai mengikuti jejak pheromone yang ditinggalkan, kembali sambil meninggalkan jejak pheromone yang kemudian menguatkan jejak tersebut. Jejak pheromone tersebut akan memudar seiring berjalannya waktu. Untuk jalur-jalur yang panjang, jejak tersebut akan mulai memudar karena jarang dilalui, sedangkan untuk jalur-jalur yang pendek, jejak tersebut akan mempunyai ketebalan pheromone yang tinggi dan membuat jalur tersebut yang akan dipilih dan jalur yang panjang akan ditinggalkan.
2.9
Algoritma Genetik Algoritma Genetik banyak dipengaruhi oleh ilmu Biologi (Suyanto 2005). Sesuai
dengan namanya, proses-proses yang terjadi dalam Algoritma Genetik sama dengan apa yang terjadi pada evolusi biologi. Dalam biologi, sekumpulan individu yang sama, yang disebut spesies, hidup, bereproduksi, dan mati dalam suatu area, yang disebut populasi. Jika anggota-anggota populasi terpisah, misalkan karena terjadi banjir, gempa bumi atau bencana alam lainnya, maka individu-individu tersebut akan membentuk beberapa populasi yang terpisah. Dalam waktu yang cukup lama, mungkin saja akan terjadi proses pembentukan spesies baru. Dalam hal ini, terjadi perubahan hereditas secara bertahap yang membentuk ciri-ciri baru pada spesies tersebut. Perubahan bertahap secara bersamaan pada kedua spesies dikenal sebagai co-evolution. Konsep yang penting disini adalah hereditas, yaitu sebuah ide yang menyatakan bahwa sifat-sifat individu dapat dikodekan dengan cara tertentu, sehingga sifat-sifat
30
tersebut dapat diturunkan kepada generasi berikutnya. Setiap individu dari suatu spesies membawa sebuah genome yang berisi beberapa kromosom dalam bentuk molekulmolekul DNA (Deoxyribo Nucleic Acid). Setiap kromosom berisi sejumlah gen, dimana unit-unit hereditas dan pengkodean informasi diperlukan untuk membangun dan menjaga suatu individu. Setiap gen dibangun dari suatu urutan bases. Terdapat empat bases dalam kromosom yang dinyatakan sebagai A, C, G, dan T. Jadi, informasi disimpan dalam suatu pola digital, menggunakan keempat simbol tersebut. Selama perkembangan dan juga selama kehidupan suatu individu, DNA dibaca dengan suatu enzim yang disebut RNA (Ribo Nucleic Acid) polymerase. Proses ini dikenal sebagai transcription yang menghasilkan Mesenger RNA(mRNA). Selanjutnya, protein dibentuk dalam suatu proses yang disebut translation menggunakan mRNA sebagai sebuah template. Masing-masing gen dapat memiliki beberapa setting, yang dikenal dengan allele. Selanjutnya, genome yang lengkap dari suatu individu dengan semua setting-nya disebut sebagai genotype. Suatu individu dengan semua sifat-sifatnya dikenal dengan istilah phenotype. Konsep penting dalam teori evolusi adalah fitness dan selection untuk proses reproduksi. Pada proses evolusi di dunia nyata, terdapat dua cara reproduksi, yaitu reproduksi seksual dan aseksual. Pada reproduksi seksual, kromosom-kromosom dari dua individu (sebagai orang tua) dikombinasikan untuk menghasilkan individu baru. Artinya, kromosom pada individu baru berisi beberapa gen yang diambil dari orangtua pertama dan beberapa gen lainnya diambil dari orangtua kedua. Hal ini disebut dengan crossover (pindah silang). Namun demikian, proses pengkopian gen orangtua ini tidak
31
luput dari kesalahan. Kesalahan pengkopian gen ini dikenal dengan istilah mutation (mutasi). Sedangkan pada reproduksi aseksual, hanya satu individu orangtua yang diperhatikan, sehingga tidak terjadi proses crossover. Tetapi, proses mutasi juga mungkin terjadi pada reproduksi aseksual. Sejak pertama kali dirintis oleh John Holland pada tahun 1960-an, Algoritma Genetik telah dipelajari, diteliti dan diaplikasikan secara kuat pada berbagai bidang. Algoritma Genetik sangat berguna dan efisien untuk masalah dengan karakteristik sebagai berikut. a. Ruang masalah sangat besar, kompleks, dan sulit dipahami. b. Kurang
atau
bahkan
tidak
ada
pengetahuan
yang
memadai
untuk
merepresentasikan masalah ke dalam ruang pencarian yang lebih sempit. c. Tidak tersedianya analisis matematika yang memadai. d. Ketika metode konvensional tidak mampu menyelesaikan masalah yang dihadapi. e. Solusi yang diharapkan tidak harus paling optimal, tetapi cukup dapat diterima. f. Terdapat batasan waktu, misalnya dalam real time system.
2.10
Teori Perancangan Program Menurut Pressmann (2005, p.36), perangkat lunak didefinisikan sebagai berikut.
a.
Instruksi-instruksi yang jika dijalankan memberikan fungsi dan kerja yang diinginkan.
b.
Struktur data yang membuat program mampu memanipulasi suatu informasi.
c.
Dokumen-dokumen yang menjelaskan operasi dan pemakaian suatu program.
32
Perangkat lunak dapat dibagi menjadi dua kategori besar, yaitu: a.
Sistem operasi, yang mengontrol jalannya komputer.
b.
Aplikasi yang dapat mengerjakan berbagai fungsi atau tugas yang diinginkan manusia dalam menggunakan komputer.
Perangkat lunak berbeda dengan perangkat keras. Perangkat lunak merupakan suatu elemen sistem yang bersifat logis, bukan fisik dan tidak berwujud nyata. Perangkat lunak memiliki beberapa karakteristik sebagai berikut. a.
Perangkat lunak dikembangkan dan direkayasa. Perangkat lunak tidak dirakit seperti perangkat keras.
b.
Perangkat lunak tidak dapat dirusak, tetapi dapat mengalami kegagalan fungsi, walaupun kegagalan ini dapat diperbaiki. Sedangkan perangkat keras dapat rusak karena pengaruh lingkungan, sehingga harus diganti jika sudah tidak mungkin diperbaiki. Pemeliharaan perangkat lunak lebih rumit daripada perangkat keras.
c.
Perangkat lunak dibuat mulai dari komponen terkecil kemudian digabungkan, sehingga dapat membentuk suatu fungsi tertentu. Sedangkan perangkat keras dirakit dari berbagai komponen yang sudah ada.
Untuk membuat sebuah perangkat lunak, Pressmann (2005, p.79), mengusulkan paradigma yang dapat dipakai sebagai pendekatan yang digunakan untuk perancangan perangkat lunak, yaitu Software Development Life Cycle (SDLC). Pendekatan waterfall digunakan untuk menggambarkan SDLC. Pendekatan ini merupakan pendekatan
33
paradigma paling kuno dan paling banyak dipakai dalam pembuatan perangkat lunak yang sudah menjadi pola dasar dalam paradigma-paradigma lainnya. (1) System Investigation
(2) System Analysis
(3) System Design
(4) Programming
(5) Testing (6) Implementation
(7) Operation
(8) Maintenance
Go Back to a Previous Stage or Stop
Gambar 2.13 SDLC (Sumber: Turban, et, al., 2001, p477) Tahap-tahap SDLC adalah sebagai berikut: 1. System Investigation (Take dcision / go or not) Pembelajaran terhadap segala kemungkinan yang dapat terjadi adalah tahap terpenting dalam tahap ini. Dengan pembelajaran yang benar maka suatu perusahaan dapat terhindar dari kesalahan yang dapat meningkatkan jumlah pengeluaran perusahaan. Pembelajaran tersebut menentukan kemungkinan adanya keuntungan dari proyek pengembangan sistem yang diajukan dan menilai proyek tersebut secara teknik, biaya, dan sifat. 2. System Analysis Tahap ini menganalisis masalah yang perlu diselesaikan. Tahap ini mendefinisikan permasalahan, mengidentifikasikan penyebab, menspesifikasikan solusi, serta mengidentifikasi informasi-informasi yang diperlukan. Tujuan utama dari tahap ini untuk menggabungkan informasi mengenai sistem yang ada dan menentukan kebutuhan dari sistem yang baru. Beberapa hal yang dihasilkan dari tahap analisis.
34
a. Kelebihan dan kekurangan dari sistem yang telah ada. b. Fungsi-fungsi yang diperlukan oleh sistem yang baru untuk menyelesaikan permasalahan. c. Kebutuhan informasi mengenai pengguna untuk sistem yang baru. 3. System Design Tahap ini menjelaskan bagaimana suatu sistem akan bekerja. Yang dihasilkan oleh desain sistem adalah sebagai berikut: a. Output, input, dan user interface dari sistem. b. Hardware, software, database, telekomunikasi, personel, dan prosedur c. Penjelasan mengenai bagaimana komponen terintegrasi. 4. Programming Tahap ini mencakup penerjemahan spesifikasi desain ke dalam bahasa komputer. 5. Testing Tahap ini dipergunakan untuk memeriksa apakah pemrograman telah menghasilkan hasil yang diinginkan dan diharapkan atas situasi tertentu. Testing dilakukan untuk mendeteksi adanya error didalam coding. 6. Implementation Implementasi adalah proses perubahan dari penggunaan sistem lama ke sistem yang baru. Ada empat strategi yang dapat digunakan oleh suatu perusahaan dalam menghadapi perubahan adalah sebagai berikut.
Parallel conversion: dengan menerapkan dua sistem, yang lama dan yang baru, secara simultan dalam periode waktu tertentu.
35
Direct conversion: sistem yang baru akan digunakan dalam satu bagian dari organisasi. Apabila sistem baru tersebut berhasil maka akan digunakan pada bagian lain dari organisasi.
Phased conversion: sistem akan digunakan secara bertahap, per komponen atau modul. Satu persatu modul akan dicoba dan dinilai, bila satu modul berhasil maka modul lain akan digunakan sampai seluruh sistem bekerja dengan baik.
7. Operation dan Maintenance Setelah tahap konversi berhasil maka sistem baru akan dioperasikan dalam suatu periode waktu. Ada beberapa tahap dalam maintenance atau pemeliharaan, diantaranya:
Debugging the program: proses yang berlangsung selama sistem berjalan.
Terus memperbaharui sistem untuk mengakomodasi perubahan dalam situasi bisnis.
2.11
Menambah fungsi atau feature baru ke dalam sistem.
Interaksi Manusia dan Komputer Menurut Shneiderman (2005, p4), Interaksi manusia dan komputer merupakan
disiplin ilmu yang berhubungan dengan, perancangan, evaluasi, dan implementasi sistem komputer interaktif untuk digunakan oleh manusia, serta studi fenomena-fenomena besar yang berhubungan dengannya. Pada interaksi manusia dan komputer ditekankan pada pembuatan antarmuka pemakai (user interface), dimana user interface yang dibuat diusahakan sedemikian rupa sehingga seorang user dapat dengan baik dan nyaman menggunakan aplikasi perangkat
36
lunak dibuat. Antar muka pemakai (user interface) adalah bagian sistem komputer yang memungkinkan manusia berinteraksi dengan komputer. Tujuan antar muka pemakai adalah agar sistem komputer dapat digunakan oleh pemakai (user interface), istilah tersebut digunakan untuk menunjuk kepada kemampuan yang dimiliki oleh piranti lunak atau program aplikasi yang mudah dioperasikan dan dapat membantu menyelesaikan suatu persoalan dengan hasil yang sesuai dengan keinginan pengguna atau biasa disebut user friendly. Pedoman untuk menghasilkan suatu rancangan antar muka program yang user friendly adalah dengan menggunakan pedoman Eight Golden Rules. Eight Golden Rules tersebut menjelaskan mengenai beberapa aturan yang diperbolehkan dan tidak diperbolehkan sebagai pedoman untuk merancang antar muka program. Kedelapan aturan tersebut, yaitu: a. Strive for consistency, konsistensi dalam perancangan antar muka; b. Enable frequent user to use shorcuts, memungkinkan pengguna menggunakan shortcuts secara berkala; c. Offer informative feed back, memberikan umpan balik yang informative; d. Design dialogs to yield closure, merancang dialog untuk menghasilkan keadaan akhir; e. Offer simple error handling, memberikan penanganan kesalahan yang sederhana; f. Permit easy reversal of actions, mengijinkan pembalikkan aksi dengan mudah;
37
g. Support internal locus of control, mendukung pengguna menguasai system yang dibuat; h. Short-term memory load, mengurangi beban jangka pendek kepada pengguna.
2.12
Unified Modelling Language (UML) Unified Modeling Language (UML) adalah sebuah bahasa yang berdasarkan
grafik/gambar untuk membuat visualisasi, spesifikasi, dan dokumentasi dari sebuah sistem pengembangan software berbasis Object-Oriented (OO). UML sendiri juga memberikan standar penulisan sebuah sistem blue print, yang meliputi konsep bisnis proses, penulisan kelas-kelas dalam bahasa program yang spesifik, skema database, serta komponen-komponen yang diperlukan dalam sistem software [Joseph Schmuller 1999, p6]. UML sebagai sebuah bahasa memberikan vocabulary dan tatanan penulisan katakata dalam „MS Word‟ untuk kegunaan komunikasi. UML tidak hanya merupakan sebuah bahasa pemograman visual saja, namun juga dapat secara langsung dihubungkan ke berbagai bahasa pemograman, seperti JAVA, C++, Visual Basic, atau bahkan dihubungkan secara langsung ke dalam sebuah object-oriented database.
2.12.1 Komponen UML Pemodelan dengan UML terdiri dari 8 tipe diagram yang berbeda untuk memodelkan sistem perangkat lunak. Masing-masing diagram UML didesain untuk menunjukkan satu sisi dari bermacam-macam sudut pandang (perspektif) dan terdiri dari tingkat abstraksi yang berbeda.
38
Class Diagram Sebuah Class Diagram menunjukkan struktur yang statis dari beberapa class
dalam suatu sistem. Class-class merepresentasikan suatu keadaan (atribut/properti) dan yang akan dikerjakan oleh sistem (metoda/fungsi). Class memiliki tiga area pokok yaitu: 1. Nama (dan stereotype) 2. Atribut 3. Metoda Atribut dan metoda dalam class diagram dapat memiliki salah satu sifat seperti berikut. •
Private, hanya dapat diakses oleh class itu sendiri.
•
Protected, hanya dapat diakses oleh class itu sendiri dan turunan dari class tersebut.
•
Public, dapat diakses oleh class selain dari class yang bersangkutan.
Class dapat direpresentasikan dalam sebuah interface atau sebaliknya merupakan implementasi dari sebuah interface yang berupa class abstrak yang hanya tidak memiliki attribute dan hanya memiliki metoda. Mesin Cuci Merk Model Nomor seri Kapasitas Add pakain() Add deterjen() Remove pakain() Gambar 2.14 Class Diagram (Sumber: Joseph Schmuller, 1999, p9)
39
•
Object Diagram Salah satu alat dalam perancangan sistem yang digunakan untuk menjelaskan
tentang nama obyek, atribut dan metode yang dipakai.
Kendaraan : Mobil dan motor
Gambar 2.15 Object Diagram (Sumber: Joseph Schmuller, 1999, p10)
Use Case Diagram Use case merupakan sebuah deskripsi dari sifat suatu sistem yang bersal dari
pendirian seorang user. Use case diagram dibutuhkan untuk pengembangan sistem karena merupakan alat yang dapat menunjukkan perilaku dan apa yang dikerjakan oleh seorang user atau pengguna. Use-case diagram merupakan suatu bentuk diagram yang menggambarkan fungsi-fungsi yang diharapkan dari sebuah sistem yang dirancang. Dalam Use-case diagram penekanannya adalah “apa” yag diperbuat oleh sistem, dan bukan “bagaimana”. Sebuah use-case akan merepresentasikan sebuah interaksi antara pelaku atau actor dengan sistem. Use-case diagram yang digunakan dalam mercancang suatu sistem dapat sangat membantu pada saat kita menyusun requirement sebuah sistem, mengomunikasikannya dengan klien, dan merancang pengujian untuk semua fitur yang terdapat dalam sistem. Dalam suatu sistem aplikasi database, use-case diagram sangat membantu requierement apa saja yang diperlukan.
40
-End1 * -End2
Mencuci Pakaian *
Pengguna Mesin Cuci
Gambar 2.16 Use Case Diagram (Sumber: Joseph Schmuller, 1999, p10) •
State Diagram State Diagram mengambarkan seluruh state yang memungkinkan yang mana
obyek-obyek dalam class dapat dimiliki dan kejadian-kejadian yang menyebabkan state berubah. Perubahan dalam suatu state disebut juga transisi (transition). Suatu transisi juga dapat memiliki sebuah aksi yang dihubungkan pada state, lebih spesifik apa yang harus dilakukan dalam hubungannya dengan transisi state.
Soaking
Washing
Rinsing
spinning
Gambar 2.17 State Diagram (Sumber: Joseph Schmuller, 1999, p11) •
Activity Diagram Sebuah Activity Diagram menunjukkan suatu alur kegiatan secara berurutan.
Activity Diagram digunakan untuk mendiskripsikan kegiatan-kegiatan dalam sebuah
41
operasi meskipun juga dapat digunakan untuk mendeskripsikan alur kegiatan yang lainnya seperti use case atau suatu interaksi. Rotate drum back and forth 15 minutes
Empty soapy water
Restart water input
Gambar 2.18 Activity Diagram (Sumber: Joseph Schmuller, 1999, p13) •
Sequence Diagram Sequence Diagram merupakan diagram yang mengambarkan kolaborasi yang
dinamis antara obyek satu dengan yang lain. Kolaborasi ini ditunjukkan dengan adanya interaksi antar obyek di dalam dan di sekitar sistem yang berupa instruksi atau pesan yang berurutan. Sequence diagram umumnya digunakan untuk menggambarkan suatu skenario atau urutan langkah-langkah yang dilakukan baik oleh actor maupun sistem yang merupakan respon dari sebuah kejadian untuk mendapatkan hasil atau output.
Sistem Aplikasi
User
Perhitungan Input Variabel Hasil Perhitungan
Perhitungan Sesuai Input Hasil Perhitungan Fungsi yang Disederhanakan
Fungsi yang Disederhanakan
Gambar 2.19 Sequence Diagram (Sumber: Joseph Schmuller, 1999, p12)
42
•
Collaboration Diagram Sebuah collaboration diagram menunjukkan kolaborasi yang dinamis yang mirip
dengan sequence diagram. Collaboration diagram digambarkan sebagai sebuah object diagram dimana sejumlah obyek ditunjukkan disekitarnya dengan hubunganhubungannya. Contoh: 1: Stop Internal Timer
Water Pipe
2: Rotate back and forth
Drum
Gambar 2.20 Collaboration Diagram (Sumber: Joseph Schmuller, 1999, p13) •
Component Diagram Component Diagram menunjukkan struktur dan hubungan antar komponen
software termasuk ketergantungan (dependency) diantara komponen-komponen tersebut.
Component1
Gambar 2.21 Component Diagram (Sumber: Joseph Schmuller, 1999, p13)
43
•
Deployment Diagram Deployment diagram menunjukkan arsitektur fisik pada hardware dan software
pada suatu sistem yang dirancang. Deployment diagram juga dapat menunjukkan perangkat-perangkat dan nodes diantara hubungan yang dimilikinya antar komponen. >>Processor>> Cobalt Networks Qube Microserver 2700WG
**
*
>>Processor>> Vectra VL Series 7
-End4
-End1 -End3
*
-End2 >>Processor>> Dell Dimension XPS R450
Gambar 2.22 Contoh Gambar Deployment Diagram (Sumber: Joseph Schmuller, 1999, p14) 2.12.2 Flowchart (Diagram Alur) Flowchart atau bagan alir suatu program adalah penggambaran secara grafik dari langkah-langkah dan urut-urutan prosedur dari suatu program. Flowchart biasanya mempermudah penyelesaian suatu masalah khususnya masalah yang perlu dipelajari dan dievaluasi lebih lanjut. Berikut adalah simbol-simbol yang digunakan untuk menggambarkan diagram alur. Tabel 2.4 Tabel simbol flowchart (Sumber: Joseph Schmuller, 1999, p21) Notasi Arti notasi Terminal, untuk menyatakan mulai dan selesei sebagai tanda, tidak melakukan suatu pekerjaan khusus. Process, untuk menyatakan assignment statement
44
Input/Output operation, untuk menyatakan proses baca dan proses tulis Decision, untuk menyatakan pengambilan keputusan sesuai dengan suatu kondisi Garis, untuk menyatakan pelaksanaan, atau alur proses Preparation, pemberi nilai awal suatu variabel Call, memanggil suatu subprogram Titik connector yang berada pada halaman yang sama. Titik connector yang berada pada halaman yang lain.