BAB II LANDASAN TEORI
2.1 Rekayasa Perangkat Lunak Untuk mengetahui apa itu rekayasa perangkat lunak, sebaiknya kita harus mengetahui apa itu sebuah perangkat lunak:
Perangkat Lunak adalah Perintah (program komputer) yang bila dieksekusi memberikan fungsi dan unjuk kerja seperti yang diperintahkan, tetapi juga semua dokumentasi dan konfigurasi data yang berhubungan, yang diperlukan untuk membuat agar program beroperasi dengan benar. Sistem Perangkat Lunak terdiri dari : Sejumlah program yang terpisah. File-file konfigurasi. Dokumentasi sistem. Dokumentasi User. Dua tipe produk perangkat lunak : Produk Generik adalah sistem stand-alone standar yang diproduksi oleh organisasi pengembang dan dijual ke pasar terbuka ke siapapun yang membelinya biasa disebut sebagai software shrinkwrapped.).
Produk pesanan (yang disesuaikan) adalah Sistem yg dipesan oleh pelanggan tertentu dan dikembangkan khusus bagi pelanggan oleh kontraktor perangkat lunak. contoh : Sistem untuk mendukung proses bisnis tertentu dan sistem kontrol lalu lintas udara.
Rekayasa perangkat lunak atau Software Engineering (SE) adalah disiplin ilmu yang membahas semua aspek produksi perangkat lunak, mulai dari tahap awal spesifikasi sistem sampai pemeliharaan sistem
setelah digunakan. Dalam
penelitian ini, perangkat lunak dikembangkan dengan menggunakan metodologi rekayasa dan metode pengujian perangkat lunak.
2.1.1 Model Proses Perangkat Lunak Merupakan deskripsi yang disederhanakan dari proses perangkat lunak yang di representasikan dengan sudut pandang tertentu. Bisa mencakup kegiatan yang merupakan bagian dari proses perangkat lunak, produk perangkat lunak, dan peran orang yang terlibat pada rekayasa perangkat lunak (Perekayasa PL). Roger S. Pressman, Ph. D (R. Pressman, 1997:29) mengatakan metode rekayasa perangkat lunak memberikan teknik untuk membangun perangkat lunak. Metode-metode itu menyangkut serangkaian tugas yang luas menyangkut analisis kebutuhan, konstruksi program, disain, pengujian, dan pemeliharaan. Model atau paradigma umum pada proses Perangkat Lunak : 1. Model air terjun (waterfall) adalah mengambil kegiatan dasar seperti spesifikasi,
pengembangan,
validasi,
dan
evolusi
dan
merepresentasikannya sebagai fase-fase proses yang berbeda seperti
spesifikasi persyaratan perancangan perangkat lunak, implementasi, pengujian dan seterusnya. 2. Pengembangan evolusioner adalah pendekatan yang berhimpitan dengan kegiatan
spesifikasi,
pengembangan,
dan
validasi.
Sistem
awal
dikembangkan dengan cepat dari spesifikasi abstrak. sistem ini kemudian di perbaiki dengan masukan dari pelanggan untuk menghasilkan sistem yang memuaskan kebutuhan pelanggan. 3. Pengembangan Sistem Formal adalah pendekatan yang menghasilkan suatu sistem matematis yang formal dan mentransformasikan spesifikasi ini, dengan menggunakan metode matematik menjadi sebuah program. 4. Pengembangan berdasarkan pemakaian ulang (Reusable) adalah teknik yanh menganggap bahwa bagian-bagian pada sistem sudah ada. proses pengembangan sistem terfokus pada pengintegrasian bagian-bagian sistem dan bukan pengembangannya dari awal.
2.1.2 Metode Pengujian Perangkat Lunak Pengujian adalah sebuah proses terhadap program/aplikasi untuk menemukan kesalahan dan segala kemungkinan yang akan menimbulkan kesalahan sesuai dengan spesifikasi perangkat lunak yang telah ditentukan sebelum aplikasi tersebut diserahkan kepada customer dalam hal ini user pengguna aplikasi. Metode pengujian perangkat lunak terbagi dua yaitu : metode pengujian white-box, dan metode pengujian black-box.
2.1.2.1 Pengujian Kotak Putih (White-Box) Pengujian white-box adalah pengujian yang dilakukan untuk menguji prosedur-prosedur yang ada. Lintasan lojik yang dilalui oleh setiap bagian prosedur diuji dengan memberikan kondisi/loop spesifik. Dengan menggunakan metode pengujian white-box, perekayasa sistem dapat melakukan test case ( Prosedur pengujian dalam setiap keadaan) yang : Menjamin pengujian terhadap semua lintasan yang tidak bergantungan minimal satu kali. Mencoba semua keputusan lojik dari sisi "true" dan "false". Eksekusi semua loop dalam batasan kondisi dan batasan operasionalnya. Pengujian validasi struktur data internal. 2.1.2.2 Pengujian Kotak Hitam (Black-Box) Pengujian black-box adalah pengujian yang dilakukan untuk antarmuka perangkat lunak, pengujian ini dilakukan untuk memperlihatkan bahwa fungsifungsi bekerja dengan baik dalam arti masukan yang diterima dengan benar dan keluaran yang dihasilkan benar-benar tepat, pengintegrasian dari eksternal data berjalan dengan baik (file/table). Pengujian kotak hitam berusaha menemukan kesalahan dalam kategori sebagai berikut (R. Pressman, 2002:551) : a.
Fungsi-fungsi yang tidak benar atau hilang.
b.
Kesalahan antarmuka (interface).
c.
Kesalahan dalam struktur data atau akses basis data eksternal.
d.
Kesalahan kinerja.
e.
Inisialisasi dan kesalahan terminasi.
2.2 Graf Adalah suatu kumpulan dari simpul-simpul dan busur yang secara matematis dapat dinyatakan sebagai berikut: G=(V,E) Dimana; G = Graph, V = Simpul atau vertex, atau Node atau Titik. E = Busur atau Edge, atau arc. Dalam hal ini V = himpunan berhingga dan tidak kosong dari simpul-simpul (vertices atau node) = { v1 , v 2 ,...,vn } dan E = himpunan sisi (edges atau arcs) yang menghubungkan sepasang simpul = { e1 , e2 ,...,en }. Catatan : busur sebenarnya hanyalah sebuah kejadian (incidence) dimana dua buah simpul mempunyai hubungan satu sama lain. sehingga dapat dikatakan, busur adalah dua buah simpul yang berpasangan. untuk menyatakan dua buah simpul yang berpasangan. maka diilustrasikan dengan sebuah garis yang menghubungkan kedua buah simpul tersebut. jadi secara fisik garis itu tidak ada. untuk menyatakan sebuah busur yang merupakan pasangan simpul v1 dan v2 biasanya ditulis sebagai berikut : ev1v2 atau e12 atau (1,2)
Simpul pada graf dapat dinomori dengan huruf, seperti v, w,…,dengan bilangan asli 1, 2, 3,…, atau gabungan keduanya. sedangkan sisi yang menghubungkan simpul vi dengan simpul v j dinyatakan dengan pasangan ( vi , v j ) atau dengan lambang e1 , e2 ,.... dengan kata lain, jika e adalah sisi yang menghubungkan simpul vi dengan simpul v j , maka e dapat ditulis sebagai : e = ( vi , v j ) Secara geometri graf digambarkan sebagai sekumpulan noktah (simpul) di dalam bidang dwimatra yang dihubungkan dengan sekumpulan garis (sisi). berikut adalah contoh gambar : 1 ce 1 2
3
e4 e3 e2
2
3
e6 e5 4
e7 4
(a)
(b) 1 e4 e1
3
e3 e2
2
e8 e6
e5
e7 4
(c) Gambar 2.1 Graf sederhana (a), Graf Ganda (b), Graf semu (c)
2.2.1 Jenis – Jenis Graf Graf dapat dikelompokkan menjadi beberapa jenis bergantung pada sudut pandang pengelompokkannya. Pengelompokan graf dapat dipandang berdasarkan ada tidaknya sisi ganda berdasarkan ada tidakknya 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.1 (a) adalah contoh graf sederhana yang mempresentasikan jaringan komputer. Simpul menyatakan komputer, sedangkan sisi menyatakan saluran telepon untuk berkomunikasi. Saluran telepon dapat beroperasi pada dua arah. 2. Graf tak sederhana (unsimple graph) Graf yang mengandung sisi ganda atau gelang dinamakan graf tak sederhana (unsimple graph). Ada dua macam graf tak sederhana, yaitu graf ganda (multigraph) dan graf semu (pseudograph). Graf ganda adalah graf yang mengandung sisi ganda. Gambar 2.1 (b) adalah graf ganda. Sisi ganda pada gambar 2.1 (b) dapat diandaikan sebagai saluran telepon tambahan apabila beban komunikasi data antar komputer sangat padat. Graf semu adalah graf yang mengandung gelang. Gambar 2.1 (c) adalah graf semu (termasuk bila memiliki sisi ganda sekalipun). Sisi gelang pada gambar 2.1 (c) dapat dianggap sebagai saluran telepon tambahan yang menghubungkan komputer dengan dirinya sendiri (mungkin untuk tujuan
diagnotik). Graf semu lebih umum daripada graf ganda, karena sisi pada graf semu dapat terhubung ke dirinya sendiri. Berdasarkan jumlah simpul pada suatu graf, maka secara umum graf dapat digolongkan menjadi dua jenis : 1. Graf berhingga (limited graph) Graf berhingga adalah graf yang jumlah simpulnya , n , berhingga. Dua buah graf pada gambar 2.1 adalah contoh graf yang berhingga. 2. Graf tak berhingga (unlimited graph) Graf yang jumlah simpulnya , n , tidak berhingga banyaknya disebut graf tak berhingga. Berikut adalah contoh gambar graf yang tak berhingga.
Gambar 2.2 Graf tak berhingga Sisi pada graf dapat mempunyai orientasi arah. berdasarkan orientasi arah pada sisi, maka secara umum graf dibedakan atas 2 jenis yaitu : 1. Graf tak berarah (undirect graph) Graf yang sisinya tidak mempunyai orientasi arah disebut graf tak berarah. Pada graf tak berarah, urutan pasangan simpul yang dihubungkan oleh sisi yang sama. 2. Graf berarah (directed graph atau digraph) Graf yang setiap sisinya diberikan orintasi arah disebut sebagai graf berarah. Menyebut sisi berarah lebih sering dengan sebutan busur (arc).
Pada graf berarah, ( v j , vk ) dan ( vk , v j ) menyatakan dua buah busur yang berbeda, dengan kata lain ( v j , vk ) tidak sama dengan ( vk , v j ). Untuk busur ( v j , vk ), simpul v j dinamakan simpul asal (initial vertex) dan simpul v k dinamakan simpul terminal (terminal vertex). Pada gambar di bawah ini
adalah contoh graf berarah. Gambar 2.1 (a) diandaikan saluran telepon tidak dapat beroperasi pada dua arah. Saluran hanya beroperasi pada arah yang ditunjukkan oleh anak panah. Jadi, sebagai contoh, saluran telepon (1, 2) tidak sama dengan saluran telepon (2,1). Graf
berarah sering
dipakai untuk menggambarkan aliran proses, peta lalu lintas suatu kota (jalan searah atau dua arah) dan sebagainya. Pada graf berarah, gelang diperbolehkan tetapi sisi ganda tidak.
v5
e4
v2
v3
e1
e2
e5
v4
e3
v1 Gambar 2.3 Graf Berarah
Definisi graf dapat diperluas sehingga mencakup graf ganda berarah. Tabel 2.1 meringkas perluasan definisi graf. disini kita menyebut graf baik sisinya tak
berarah maupun berarah, baik mengandung gelang maupun sisi ganda, baik graf sederhana maupun graf tak sederhana. Tabel 2.1 Jenis-Jenis Graf
Jenis
Sisi
Sisi ganda
Sisi gelang
dibolehkan ?
dibolehkan ?
Graf sederhana
Tak berarah
Tidak
Tidak
Graf ganda
Tak berarah
Ya
Tidak
Graf semu
Tak berarah
Ya
Ya
Graf berarah
Berarah
Tidak
Ya
Graf ganda berarah
Berarah
Ya
Ya
2.2.2 Terminologi Graf Terminologi (istilah) pada pembahasan mengenai graf cukup banyak terminologi yang sering dipakai, meliputi : 1. Ketetanggaan (Adjacent). Dua buah simpul (vertex) dikatakan bertetangga jika keduanya terhubung langsung. Pada gambar 2.1 (a), simpul (vertex) 1 bertetangga dengan simpul (vertex) 2 dan 3, tetapi tidak bertetangga dengan simpul (vertex ) 4. 2.
Derajat (Degree). Derajat (Degree) suatu simpul adalah jumlah sisi yang bersisian dengan simpul tersebut dan jika terdapat gelang (loop), gelang tersebut dihitung dua (dua buah sisi). Notasinya : d(v). Pada gambar 2.1 (a) d(1) = d(4) = 2, d(2) = d(3) = 3.
3. Sirkuit (Circuit). Sirkuit adalah lintasan dengan simpul (vertex) pertama sama dengan simpul yang terakhir, dimana semua simpul yang dilalui hanya muncul
sekali. Contoh sirkuit, pada gambar 2.1 (a), 1, 2, 3, 1 adalah merupakan sirkuit. 4. Terhubung (Connected). Graf terhubung (Connected Graph) merupakan graf tak berarah dimana pada setiap pasang simpul (vertex) vi dan v j terdapat lintasan dari vi ke
v j yang juga berarti ada lintasan v j ke vi , jika tidak maka graf tersebut disebut graf tak terhubung (disconnected graph). Gambar 2.4 (a) menunjukkan contoh graf terhubung (connected graph), dan gambar 2.4 (b) adalah contoh dari graf tak terhubung (disconnected graph).
1
2
1
3
2
3 5
4 (a)
4 (b)
Gambar 2.4 Graf Terhubung (a) dan Graf Tak Terhubung (b)
5.
Graf Berbobot (Weighted Graph). Graf berbobot (weighted graph) adalah graf yang setiap sisinya diberi sebuah nilai (bobot). Bobot tiap sisi dapat menyatakan jarak antara dua buah kota atau panjang suatu jalan pada sebuah kota, biaya perjalanan antara dua buah kota, ongkos produksi, dan sebagainya. Gambar 2.4 dan 2.5 adalah contoh graf berbobot.
a 10
12 8
e
b 15
11
d
9 c
14
Gambar 2.5 Graf Berbobot 6. Graf Lengkap (Complete Graph). Graf lengkap (complete graph) adalah graf sederhana yang setiap simpulnya (vertex-nya) terhubung dengan semua simpul (vertex) yang lainnya. Derajat tiap simpul dari graf lengkap dengan n buah simpul lainnya melalui satu sisi..
Gambar 2.6 Graf Lengkap dari Dua, Tiga, Empat dan Lima 7. Graf Planar (Planar Graph). Graf yang dapat digambarkan pada bidang datar dengan sisi-sisi tidak saling memotong disebut sebagai graf planar, jika tidak disebut graf takplanar.
Gambar 2.7 adalah Graf Planar
2.2.3
Representasi Graf
2.2.4
Representasi Graf Pemrosesan graf dengan program komputer, memerlukan representasi graf
dalam memori. Ada beberapa representasi graf yang mungkin untuk dilakukan, salah satunya adalah dengan matriks ketetanggaan (adjacency matrix). Matriks ketetanggaan adalah representasi graf yang paling umum digunakan. Misalkan G = (V, E) adalah graf dengan n simpul, n ≥ 1. Matriks ketetanggaan G adalah matriks yang berukuran n x n. bila matriks tersebut dinamakan matriks A = [ a ij ] maka bernilai 1 jika simpul i dan j bertetanggaan dan bernilai 0 jika simpul i dan simpul j tidak bertetangga. Matriks ketetanggaan untuk graf sederhana dan tidak berarah selalu simetris dan diagonal utamanya selalu bernilai 0 (nol) karena tidak ada sisi gelang (loop). Jumlah elemen matriks ketetanggaan untuk graf dengan n simpul adalah n 2 , jika tiap elemen membutuhkan ruang memori sebesar p maka ruang memori yang dibutuhkan seluruhnya adalah pn 2 . Pada matriks ketetanggaan untuk graf tak berarah sederhana simetris, cukup dengan menyimpan elemen segitiga atas saja, karena matriksnya simetris, sehingga ruang memori akan dapat dihemat sebesar pn 2 /2. Pada graf berbobot, a ij menyatakan tiap sisi yang menghubungkan simpul i dengan simpul j. Gambar 2.8 merupakan contoh graf berbobot beserta matriks ketetanggaannya.
a 10
a
12 8
e
b
15
11
9
d
c 14
a b c d e
b 12
c
d
e 10 12 9 11 8 9 14 11 14 15 10 8 15
Gambar 2.8 Matriks Ketetanggaan untuk Graf 2.2.4 Lintasan dan Sirkuit Euler Lintasan yang melalui masing-masing sisi dalam graf tepat satu kali disebut Lintasan Euler. Jika lintasan tersebut adalah lintasan tertutup, maka lintasan tertutup tersebut disebut sirkuit Euler. Contoh seperti pada gambar 2.9 berikut:
2
1
Lintasan Euler : 3, 1, 2, 3, 4, 1 Tidak ada sirkuit Euler
3
4
Gambar 2.9 Contoh Lintasan Euler Untuk membuat graf G yang mempunyai Lintasan Euler harus dipenuhi kondisi : 1. Graf terhubung. 2. Graf tidak mempunyai simpul derajat ganjil sama sekali atau mempunyai 2 buah simpul berderajat ganjil. Untuk membuat graf G yang mempunyai sirkuit Euler harus dipenuhi kondisi :
1. Graf terhubung. 2. Semua simpul berderajat genap.
Graf berarah G mempunyai Lintasan Euler jika G terhubung dan setiap simpul mempunyai derajat masuk dan derajat keluar sama kecuali 2 simpul. Yang pertama memiliki derajat keluar satu lebih besar dari derajat masuk dan yang kedua memiliki derajat masuk satu lebih besar dari derajat keluar. Graf berarah G mempunyai Sirkuit Euler jika hanya jika g terhubung dan setiap simpul mempunyai derajat masuk dan derajat keluar sama.
2.2.5
Lintasan dan Sirkuit Hamilton Lintasan Hamilton adalah lintasan yang melalui tiap simpul dalam graf
tepat satu kali. Jika lintasannya adalah lintasan tertutup maka disebut Sirkuit Hamilton. Graf yang mempunyai sirkuit hamilton disebut Graf Hamilton. Graf yang hanya mempunyai lintasan hamilton disebut Graf Semi Hamilton. Contoh seperti pada gambar 2.10 berikut :
1
2
1
2
4
3
4
3
Lintasan Hamilton : 3, 2, 1, 4
Sirkuit Hamilton : 1, 2, 3, 4, 1
Gambar 2.10 Contoh Lintasan dan sirkuit Hamilton
2.3 Algoritma Untuk Pencarian Rute
Penentuan dalam pencarian rute optimum atau path terbaik ini diciptakan membantu untuk mendapatkan keefisienan waktu tempuh, sehingga pengguna jalan tepat waktu untuk sampai tempat tujuan.
Dalam teknik pencarian untuk mendapatkan solusi dalam penetuan rute dari suatu permasalahan kita dapat menggunakan beberapa jenis metode yang sangat umum berikut bagan yang dapat disajikan dalam metode pencarian yang diantaranya:
Gambar 2.12 Contoh Peta dalam Bentuk Graph
Gambar 2.13 Gambar 2.13 Struktur Tree dari Graph 2.12
2.3.1 Algoritma Breadth First Search Pada metode Breadth-first Search, semua node pada level n akan dikunjungi terlebih dahulu sebelum mengunjungi node-node pada level n+1. Pencarian dimulai dari node akar terus ke level 1 dari kiri ke kanan, kemudian berpindah ke level berikutnya demikian pula dari kiri ke kanan sampai ditemukannya solusi
Gambar 2.14 Tree untuk Breadth First Search
o Algoritma 1. Buat sebuah Antrian, inisialisasi node pertama dengan root dan tree. 2. Bila node pertama, jika ≠ GOAL, diganti dengan anak-anaknya dan diletakkan di belakang PER LEVEL. 3. Bila node pertama = GOAL, selesai.
Keuntungan: Tidak akan menemui jalan buntu. Jika ada satu solusi, maka breadth-first search akan menemukannya dan jika ada lebih dari satu solusi, maka solusi minimum akan ditemukan.
Kelemahan: Membutuhkan memori yang cukup banyak, karena menyimpan semua node dalam satu pohon. Membutuhkan waktu yang cukup lama, karena akan menguji n level untuk mendapatkan solusi pada level yang ke-(n+1)
2.3.2 Algoritma Depth First Search Pencarian Depth First Search dilakukan pada satu node dalam setiap level dari yang paling kiri. jika pada level yang paling dalam, solusi belum ditemukan, maka pencarian dilanjutkan pada node sebelah kanan. Node yang kiri dapat dihapus dari memori. Jika pada level yang paling dalam tidak ditemukan solusi, maka pencarian dilanjutkan pada level sebelumnya. Demikian seterusnya sampai ditemukan solusi. Jika solusi ditemukan maka tidak diperlukan proses backtracking (penelusuran balik untuk mendapatkan jalur yang dinginkan).
o Algoritma 1. Buat sebuah Antrian,inisialisasi node pertama dengan Root dari Tree 2. Bila node pertama, jika
GOAL,node dihapus diganti dengan
anak-anaknya dengan urutan Lchild 3. bila node pertama = GOAL, selesai
Gambar 2.15 Tree untuk Depth-First Search
Keuntungan Membutuhkan memori yang relatif kecil, karena hanya node-node pada lintasan yang aktif saja yang disimpan. Secara kebetulan, metode depth-first search akan menemukan solusi tanpa harus menguji labih banyak lagi dalam ruang keadaan.
Kelemahan DFS adalah: Jika pohon yang dibangkitkan mempunyai level yang dalam (tak terhingga), maka tidak ada jaminan untuk menemukan solusi (Tidak Complete). Jika terdapat lebih dari satu solusi yang sama tetapi berada pada level yang berbeda, maka pada DFS tidak ada jaminan untuk menemukan solusi yang paling baik (Tidak Optimal).
2.3.3 Algoritma Best First Search Best First Search (BFS) adalah algoritma pathfinding yang menggunakan menggunakan fungsi heuristic untuk ‘menuntun’ pencarian solusi, dengan menghitung berapa jauh goal dari node sekarang dari sekian pilihan jalan, dipilih jalan yang paling dekat ke tujuan. BFS tidak menjamin menemukan rute yang paling pendek, namun algoritma ini bekerja dengan sangat cepat. Masalah utama pada algoritma pathfinding BFS ini adalah cara kerjanya yang terus mencoba bergerak ke arah tujuan/goal, meskipun jalan yang dilaluinya bukan jalan yang benar. Karena BFS hanya memperhitungkan cost untuk mencapai goal dan mengabaikan cost jalan yang sudah ditempuhnya untuk sampai ke current state, maka algoritma tersebut terus maju meskipun jalan yang telah dilaluinya sudah terlalu panjang. Algoritma ini merupakan penyempurna dari breadth first search dan depth fist search.
Gambar 2.16 Tree untuk Best-First Search
o Algoritma 1. Buat sebuah Antrian, inisialisasi node pertama dengan root dari tree. 2. Bila node pertama, jika ≠ GOAL, node dihapus & diganti dengan anak-anaknya.selanjutnya keseluruhan node yang ada di Queue di-sort Ascending. 3. Bila node pertama = Goal, selesai.
o Keuntungan 1. Membutuhkan memori yang relative kecil. Karena hanya nodenode pada lintasan yang aktif saja yang disimpan. 2. Secara kebetulan metode best search akan menemukan solusi tanpa harus menguji lebih banyak lagi dalam ruang keadaan. o Kelemahan 1. Algoritma akan berhenti kalau mencapai nilai optimal local. 2. Tidak diijinkan untuk melihat satupun langkah sebelumnya.
2.3.4 Algoritma Hill Climbing ( Pencarian mendaki )
Gambar 2.17 Tree untuk Hill Climbing o Algoritma 1. Buat sebuah Antrian, inisialisasi node pertama dengan Root dari tree 2. Bila node pertama, jika ≠ GOAL, node dihapus diganti dengan Anak-anaknya dengan urutan paling kecil jaraknya 3. Bila node pertama = Goal, selesai
o Keuntungan 1. Membutuhkan memori yang relative kecil. Karena hanya nodenode pada lintasan yang aktif saja yang disimpan. 2. Metode hill climbing search akan menemukan solusi tanpa harus menguji lebih banyak lagi dalam ruang keadaan. o Kelemahan 1. Algoritma akan berhenti kalau mencapai nilai optimal local. 2. Perlu menentukan aturan yang tepat.
2.3.5 Algoritma A *(A Star) Algoritma A* adalah sebuah algoritma yang telah diperkaya. Hal ini karena algoritma A* merupakan penyempurnaan dari algoritma-algoritma pencarian sejenis yang terdahulu, seperti algoritma Djikstra, algoritma Primm’s, algoritma breadth first search, depth first search, algoritma best first search. Dengan menerapkan suatu heuristik, algoritma ini membuang langkah-langkah yang tidak perlu dengan pertimbangan bahwa langkah-langkah yang dibuang, pasti merupakan langkah-langkah yang tidak akan mencapai solusi yang diinginkan dengan estimasi inilah solusi biaya terkecil untuk mencapai suatu tujuan dengan jarak tempuh terdekat dan memiliki nilai heuristik yang digunakan sebagai dasar pertimbangan. Heuristik adalah kriteria, metoda, atau prinsip-prinsip untuk menentukan pilihan sejumlah alternatif untuk mencapai sasaran dengan efektif. Nilai heuristik dipergunakan untuk mempersempit ruang pencarian.
Metoda pencarian A* menghasilkan jalur optimal mulai dari tempat awal kemudian melalui graph menuju tempat yang dituju. Metode ini berdasarkan formula: f(n) = g(n) + h(n) Keterangan : h(n) = biaya estimasi dari node n ke tujuan. g(n) = biaya path / perjalanan. f(n) = solusi biaya estimasi termurah node n untuk mencapai tujuan. ( Russel dan Norvig dikutip dalam Novie Theresia Br. Pasaribu dkk., 2008). Keuntungan : Dapat menemukan solusi yang terbaik dibandingkan algoritma pencarian yang lain karena teknik pencarian A star berdasarkan cost atau nilai terkecil dari node tersebut, Sedangkan algoritma sejenis tidak mempertimbangkan cost atau nilai dari node tersebut, sehingga A star merupakan pencarian yang optimal. Kelemahan : jika dibandingkan dengan algoritma Best First Search, A star tidak menemukan solusi pencarian dalam hal penyimpanan node atau jalur, karena dalam pencarian A star tidak memperhatikan seberapa banyak penyimpanan node. Algoritma ini memperhitungkan biaya atau nilai dari node tersebut. Sehingga membutuhkan memori yang cukup banyak dalam penyimpanan node dan membutuhkan waktu yang lama dalam melakukan pencarian dari node awal ke arah node tujuan.
2.3.6 Algoritma Branch and Bound Algoritma Branch and Bound (B&B) merupakan suatu metode pencarian di dalam ruang solusi secara sistematis. Ruang solusi diorganisasikan ke dalam
pohon ruang status yang dibangun secara dinamis dengan skema Breadth First Search (BFS). Tiap simpul yang dibangkitkan akan diberikan nilai ongkos (cost). Untuk mempercepat pencarian solusi maka simpul berikut yang diekspansi tidak berdasarkan urutan pembangkitnya tetapi berdasarkan cost yang dimiliki oleh simpul-simpul hidup. Cost pada setiap simpul i menyatakan perkiraan ongkos termurah lintasan dari simpul i ke simpul solusi. o Algoritma 1. Buat sebuah antrian, inisialisasi node pertama dengan root dari tree. 2. bila lintasan parsial ≠ lintasan GOAL, maka lintasan parsial diganti dengan lintasan parsial + node child, semuanya diatur berdasarkan harga yang diurut secara ascending. 3. Bila node pertama = lintasan GOAL, selesai. Keuntungan 1. Algoritma berhenti pada nilai optimum sebenarnya ( menemukan optimum global ). Kelemahan 1. Membutuhkan memori yang cukup banyak, karena biasa jadi menyimpan semua lintasan parsial yang memungkinkan. 2.
2.3.7 Algoritma Dynamic Programming Metode ini sama dengan Branch and Bound tetapi lebih efisien karena bisa mengurangi lebar / melakukan pemotongan terhadap lebar tree. Hal ini dilakukan dengan cara mereduksi lintasan parsial yang menuju ke suatu node yang sudah pernah dikunjungi sebelumnya. o Algoritma 1. Buat sebuah antrian. Inisialisasi node pertama dengan root dari tree. 2. Bila lintasan parsial ≠ lintasan GOAL, jika ada lintasan parsial dengan node terakhir yang sama (dalam satu queue) maka diambil yang harganya paling minimal, sedangkan yang lebih mahal dari queue, sehingga tree akan lebih kurus. 3. Bila node pertama = lintasan GOAL, selesai.
Gambar 2.18 Gambar Tree yang Dihasilkan dengan Metode Branch and Bound dan Dynamic Programming
o Keuntungan 1. Algoritma berhenti pada nilai optimum sebenarnya. 2. Lebih efisien dari metode Branch & Bound dalam penggunaan memori dan waktu eksekusi karena ada pemotongan. o Kelemahan 1. Harus mengingat node terakhir dari lintasan parsial yang sudah dicapai sebelumnya. Dalam pembuatan aplikasi ini penulis menggunakan metode Dynamic Programming.
2.4
UML (Unified Modelling Language) Unified Modelling Language (selanjutnya disebut UML) adalah keluarga
notasi grafis yang didukung oleh meta-model tunggal, yang membantu
pendeskripsian dan desain sistem perangkat lunak, khususnya sistem yang dibangun menggunakan pemrograman berorientasi objek (Fowler, 2005:1). Selain itu UML juga dapat diartikan sebagai sebuah bahasa yang telah menjadi standar dalam industri untuk visualisasi, merancang dan mendokumentasikan sistem piranti lunak (Dharwiyanti dan Wahono, 2003:2). UML menawarkan sebuah standar untuk merancang model sebuah sistem. Dengan menggunakan UML kita dapat membuat model untuk semua jenis aplikasi piranti lunak, dimana aplikasi tersebut dapat berjalan pada piranti keras, sistem operasi dan jaringan apapun, serta ditulis dalam bahasa pemrograman apapun. Tetapi karena UML juga menggunakan class dan operation dalam konsep dasarnya, maka ia lebih cocok untuk penulis. Notasi UML terutama diturunkan dari 3 notasi yang telah ada sebelumnya yaitu : Grady Booch OOD (ObjectOriented Design), Jim Rumbaugh OMT (Object Modelling Technique) dan Ivar Jacobson OOSE (Object-Oriented Software Engineering). Dalam perancangan model perangkat lunak, UML mendukung 3 (tiga) jenis model yaitu: a. Model Fungsional (Functional Model) Model fungsional menunjukkan fungsionalitas sebuah sistem dari sudut pandang pengguna. b. Model Obyek (Object Model) Model obyek menunjukkan struktur dan sub struktur dari sistem menggunakan obyek, atribut, operasi dan asosiasi.
c. Model Dinamis (Dynamic Model) Model dinamis menunjukkan sifat internal dari sebuah sistem. Piranti lunak dalam bahasa berorientasi objek seperti C++, Java, C# atau VB.NET. Seperti bahasa-bahasa lainnya, UML mendefinisikan notasi dan syntax atau semantik.
Notasi
UML
merupakan
sekumpulan
bentuk
khusus
untuk
menggambarkan berbagai diagram piranti lunak. Setiap bentuk memiliki makna tertentu, dan syntax UML mendefinisikan bagaimana bentuk-bentuk tersebut dapat dikombinasikan. UML terdiri atas 13 jenis diagram resmi seperti tertulis dalam Tabel 2.2 Table 2.2 Jenis Diagram Resmi UML No.
Diagram
Kegunaan
1.
Activity
Behavior prosedural dan parallel
2.
Class
Class, fitur, dan hubungan-hubungan
3.
Communication
Interaksi antar objek; penekanan pada jalur
4.
Component
Struktur dan koneksi komponen
5.
Composite structure Deployment
Dekomposisi runtime sebuah class
Campuran sequence dan activity diagram
8.
Interaction overview Object
9.
Package
Struktur hirarki compile-time
10.
Sequence
Interaksi antar objek; penekanan pada sequence
11.
State machihne
Bagaimana even mengubah objek selama aktif
12.
Timing
Interaksi antar objek; penekanan pada timing
13.
Use case
Bagaimana pengguna berinteraksi dengan sebuah sistem
6. 7.
Pemindahan artifak ke node
Contoh konfigurasi dari contoh-contoh
Diagram UML yang akan dibahas pada bab ini adalah use case diagram, Activity diagram.
2.4.1 Use Case Diagram Use Case diagram adalah teknik untuk merekam persyaratan fungsional sebuah sistem. Use case diagram mendeskripsikan interaksi tipikal antara para pengguna sistem dengan sistem itu sendiri, dengan memberi sebuah narasi tentang bagaimana sistem tersebut digunakan. Use case diagram menggambarkan fungsionalitas yang diharapkan dari sebuah sistem yang ditekankan adalah apa yang diperbuat sistem, dan bukan bagaimana. Sebuah use case diagram merepresentasikan sebuah interaksi antara aktor dengan sistem. Use case merupakan sebuah pekerjaan tertentu, misalnya login ke sistem, membuat sebuah daftar belanja, dan sebagainya. Seorang atau sebuah aktor adalah sebuah entitas manusia atau mesin yang berinteraksi dengan sistem untuk melakukan pekerjaan-pekerjaan tertentu. Use case diagram dapat sangat membantu bila kita sedang menyusun persyaratan (requirement) sebuah sistem, mengkomunikasikan rancangan dengan klien, dan merancang test case untuk semua feature yang ada pada sistem. Sebuah use case diagram dapat memasukkan fungsionalitas use case diagram lain sebagai bagian dari proses dalam dirinya. Secara umum diasumsikan bahwa use case diagram yang dimasukkan akan dipanggil setiap kali use case diagram yang memasukkan dieksekusi secara normal. Sebuah use case diagram dapat dimasukkan oleh lebih dari satu use case diagram lain, sehingga duplikasi fungsionalitas dapat dihindari dengan cara menarik keluar fungsionalitas yang umum (common). Sebuah use case diagram juga dapat memperluas use case diagram lain dengan aktivitasnya (behaviour) sendiri. Sementara hubungan generalisasi antar
use case diagram menunjukkan bahwa use case diagram yang satu merupakan spesialisasi dari yang lain. Berikut ini adalah notasi use case diagram.
Aktor
Use Case
Penghubung antara aktor dengan use case
Gambar 2.19 Notasi use case diagram Notasi-notasi yang digunakan dalam pemodelan use case pada Gambar 2.19 adalah: 1. Aktor, merupakan sebuah peran yang dimainkan seorang pengguna dalam kaitannya dengan sistem. 2. Use Case adalah rangkaian atau uraian sekelompok yang saling terkait dan membentuk sistem secara teratur yang dilakukan atau diawasi oleh sebuah aktor. Use case digunakan untuk membentuk tingkah-laku benda dalam sebuah model serta direalisasikan oleh sebuah kolaborasi (collaboration). 3. Penghubung antara aktor dengan use case (generalization), menggambarkan hubungan khusus dalam obyek anak (child) yang menggantikan obyek induk (parent).
2.4.2
Activity Diagram Activity diagram adalah teknik untuk menggambarkan logika prosedural,
proses bisnis, dan jalur kerja. Dalam beberapa hal, diagram ini memainkan peran mirip sebuah diagram alir, tetapi perbedaan prinsip antara diagram ini dan notasi diagram alir adalah diagram ini mendukung behavior paralel (Fowler, 2005:163).
Activity diagram memungkinkan siapapun yang melakukan proses untuk memilih urutan dalam melakukannya. Dengan kata lain, diagram hanya menyebutkan aturan-aturan rangkaian dasar yang harus diikuti. Hal ini penting untuk permodelan bisnis, karena proses-proses sering muncul secara paralel. Ini juga berguna pada algoritma yang bersamaan, dimana urutan-urutan independen dapat melakukan hal-hal secara paralel.
2.4.3 Teori Dasar Objek Oriented Programming Objek Oriented Programing merupakan sebuah teknik baru dalam dunia pemograman, dimana pemogram memodelkan masalah dengan pendekatan objek, bukan melalui cara prosedural, modular, maupun abstraksi data. Beberapa keunggulan atau manfaat OOP adalah : 1. Lebih sedikit dalam penggunaan kode, sehingga tidak menyulitkan programmer. 2.
Programmer
dapat
membagi-bagi
tugas
membuat
program
dengan
berkelompok. 3. Lebih sederhana karena program dibagi kedalam objek-objeknya. 4. Mudah dalam tracing error. Untuk dapat merasakan manfaat di atas dalam membuat program, programmer harus bisa mempraktekkan konsep-konsep OOP dalam pembuatan programnya. Ada 4 konsep utama dalam OOP, yaitu class (kelas), encapsulation (enkapsulasi), inheritance (pewarisan), dan polymorphism (polimorfisme). 1. Kelas (Class)
Kelas merupakan deskripsi abstrak informasi dan tingkah laku dari sekumpulan data. suatu kelas terdiri atas data kelas (data field), prosedur dan fungsi (method), dan sifat kelas (property). Kelas dikenal juga sebagai tipe objek, penggambaran objek, atau blueprint dari objek. Karena itu, representasi atau wakil dari suatu kelas adalah objek kelas tersebut. Suatu objek hanya terdiri dari satu kelas, dan satu kelas dapat terdiri dari beberapa objek. Objek-objek dengan kelas yang sama akan memiliki perilaku yang sama juga. Contoh sederhana dari kelas adalah kelas sepeda_motor. data field kelas sepeda motor adalah komposisi bahan bakar, udara, serta energi yang dibutuhkan maupun yang dikeluarkan oleh sepeda motor tersebut. Sementara method dari sepeda motor tersebut adalah proses yang terjadi di dalam mesin untuk menjalankan sepeda motor. Sementara property dari sepeda motor tersebut adalah seperti stank, gas, rem , dan berbagai antarmuka untuk menjalankan sepeda motor tersebut. sementara objek dari kelas sepeda motor dapat berupa sepeda motor bebek, harley, sepeda motor besar, dan lain-lain. 2. Enkapsulasi (encapsulation). Enkapsulasi adalah penyembunyian detail informasi dan fungsionalitas yang ada pada suatu kelas. Jadi kita tidak perlu tahu bagaimana detail dari kelas kelas tersebut. Yang perlu kita ketahui hanyalah bagaimana cara menggunakan kelas tersebut. Sebagai contoh, kelas sepeda motor yang tadi kita hanya perlu mengetahui bagaimana cara menggunakan sepeda motor tersebut, tanpa harus tahu bagaimana sepeda motor tersebut dapat berjalan, dan lain sebagainya. 3. Pewarisan (Inheritance). Pewarisan (seperti namanya) merupakan pewarisan sifat kelas dari induk kelas ke anaknya. Disini kita hanya mengembangkan kelas yang sudah ada untuk
membuat kelas baru. Kita bisa memodifikasi sifat-sifat kelas induk, menambah, mengurangi, maupun memperbaiki untuk dijadikan sifat kelas anak (subkelas). penurunan kelas ini dapat dilakukan secara bertingkat-tingkat sehingga semakin kebawah maka kelas itu menjadi semakin spesifik. Contohnya adalah kelas makanan, dari kelas makanan kita dapat turunkan menjadi kelas dodol, kemudian dari kelas dodol dapat diturunkan lagi menjadi kelas dodol durian, dodol melon, dodol nangka, dodol keju, dan lain-lain. Dari kelas-kelas tersebut juga dapat diturunkan lagi menjadi dodol durian spesial keju, jadi sifat-sifat induknya dapat turun ke sifat-sifat anaknya. 4. Polimorfisme (polymorphism) Polimorfisme adalah kemampuan objek-objek yang berbeda kelas tapi terkait dalam pewarisan untuk merespon secara berbeda terhadap suatu pesan yang sama. Polimorfisme juga diartikan kemampuan suatu objek untuk memutuskan method mana yang akan diterapkannya terhadap suatu masalah. Misalkan ada kelas truk memiliki method jalan. Kelas truk memiliki kelas turunan kelas truk mini yang juga memiliki method jalan. Pada saat berjalan, maka kelas truk mini akan memanggil atau memilih method jalan pada truk mini dari pada method jalan pada truk (parent class) karena lebih sesuai dengannya. Kemampuan seperti inilah yang disebut dengan Polimorfisme.
2.5 Perancangan Basis Data Perancangan merupakan suatu hal yang sangat penting dalam pembuatan basis data. Permasalahan yang dihadapi pada waktu perancangan yaitu bagaimana basis data yang akan dibangun ini dapat memenuhi kebutuhan saat ini dan masa
yang akan datang. Untuk itu diperlukan perancangan basis data baik secara fisik maupun secara konseptualnya. Perancangan konseptual akan menunjukkan entity dan relasinya berdasarkan proses yang diiginkan oleh organsisasinya. Untuk menentukan entity dan relasinya perlu dilakukan analisis data tentang informasi yang ada dalam spesifikasi di masa yang akan datang. Dalam penelitian ini perancangan basis data menggunakan microsoft office acces.
2.5.1 Microsoft Office Access Dalam Microsoft Office Access terdapat fasilitas untuk membuat tabel data, selain menyediakan sarana untuk merancang data base, microsoft office access juga dapat digunakan untuk memanipulasi data di dalamnya serta melakukan pencarian item-item tertentu dan dapat memberikan akses untuk memanipulasi field dan record dari file data base langsung dari form yang digunakan.
2.6 Pemrograman Delphi 7 Borland Delphi adalah bahasa pemrograman yang bekerja dalam ruang lingkup windows, kemampuannya dapat dipakai untuk merancang program aplikasi yang berpenampilan seperti program aplikasi lainnya berbasis windows.
2.6.1 Mengenal Borland Delphi 7 Kemampuan
Borland
Delphi
secara umum
adalah menyediakan
komponen-komponen yang memungkinkan kita membuat program aplikasi yang sesuai dengan tampilan dan cara kerja MS. Windows.
Bahasa
pemrograman
delphi
disebut
bahasa
prosedural
artinya
bahasa/sintaxnya mengikuti urutan tertentu / prosedur. Ada jenis pemrograman non-prosedural seperti pemrograman untuk kecerdasan buatan seperti bahasa prolog. Delphi termasuk keluarga visual sekelas Visual Basic, Visual C, artinya perintah-perintah untuk membuat objek dapat dilakukan secara visual. Pemrogram tinggal memilih objek apa yang ingin dimasukkan ke dalam Form/Window, lalu tingkah laku objek tersebut saat menerima event/aksi tinggal dibuat programnya. Delphi merupakan bahasa berorientasi objek, artinya nama objek, property dan methode/prosedur dikemas menjadi satu kemasan (encapsulate ).
2.6.2
Keunggulan Borland Delphi 1. IDE
(Integreted
Develovment
Environment)
atau
lingkungan
pengembangan aplikasi sendiri adalah satu dari beberapa keunggulan delphi , didalamnya terdapat menu-menu yang memudahkan kita untuk membuat suatu proyek program. 2. Proses kompilasi cepat, pada saat apliaksi yang kita buat dijalankan pada delphi, maka secara otomatis dapat dibaca sebagai sebuah program, tanpa dijalankan terpisah. 3. Mudah digunakan, source code delphi yang merupakan turunan dari pascal, sehingga tidak perlu suatu penyesuaian lagi. 4. Bersifat multi purpose, artinya bahasa pemerograman delphi dapat digunakan untuk mengembangkan berbagai keperluan penggembangan aplikasi.
2.6.3
Langkah Membuat Program Aplikasi Dengan Borland Delphi 7 Untuk membuat program aplikasi dengan Borland Delphi 7, dapat melakukan langkah-langkah sbb: 1. Gambar obyek dan tata letak ke dalam jendela form menggunakan ikon-ikon obyek dalam Component Pallette. 2. Bila perlu, tentukan property pada tiap komponen menggunakan lembar properties pada jendela object inspector. 3. Tulis kode program untuk event, pada obyek yang diinginkan. Event adalah suatu kejadian yang dirasakan objek. Misalnya tunjuk, klik atau lainnya.
2.6.4
Komponen Borland Delphi 7 1. Project Project adalah sekumpulan form, unit dan beberapa hal lain. Singkatnya project adalah program aplikasi itu sendiri. 2. Form Form adalah suatu objek yang dipakai sebagai tempat bekerja program aplikasi.
Gambar 2.20 Jendela Form
1. Unit Unit adalah kode program. Satu program mungkin mempunyai satu atau beberapa unit.
Gambar 2.21 Jendela Unit
2. Object Tree View Merupakan sebuah diagram pohon yang menggambarkan hubungan logis menghubungkan semua komponen yang terdapat dalam proyek suatu program. Komponen- komponen tersebut meliputi form, module atau frame.
Gambar 2.22 Jendela Object Tree View 3. Object Inspector Merupakan jendela yang digunakan untuk mengatur tampilan komponen pada form. Secara umum object inspector terbagi dua yaitu :
a. Properties Digunakan untuk mengatur tampilan pada sebuah komponen baik itu meliputi penggantian nama, warna, jenis huruf border dan lain-lain.
Gambar 2.23 Jendela Inspector(Properties) b. Events Merupakan jendela properties yang digunakan untuk memberikan fungsi yang lebih detail dari fungsi sebenarnya.
Gambar 2.24 Jendela Events 4. Component Pallete Merupakan kumpulan icon yang digunakan untuk merancang semua aplikasi.
Gambar 2.25 Jendela Component Pallete
5. Code Explorer Jendela yang digunakan untuk menampilkan semua variabel, type, rountine yang didefinisikan pada sebuah unit.
Gambar 2.26. Jendela Code Explorer
6. Code Diagram Merupakan fasilitas pada delphi yang digunakan untuk mendesain sebuah diagram atas komponen-komponen yang digunakan dalam rancangan suatu aplikasi.
Gambar 2.27 Jendela Code Diagram
