BAB 2

LANDASAN TEORI

2.1 TEORI GRAF

2.1.1 Definisi

Definisi 2.1 (Munir, 2009, p356)

Secara matematis, graf G didefinisikan sebagai pasangan himpunan (V,E),

ditulis dengan notasi G = (V,E), yang dalam hal ini V adalah himpunan tidak kosong

dari simpul-sumpul (vertices atau node) dan E adalah himpunan sisi (edges atau

arcs) yang menghubungkan simpul.

Secara geometri graf digambarkan sebagai sekumpulan noktah (simpul) di

dalam bidang kartesius yang dihubungkan dengan sekumpulan garis (sisi).

Gambar 2.1 Graf (Munir, 2009, p356)

     8  

Gambar di halaman sebelumnya menunjukkan sebuah graf G dengan:

• V = {1,2,3,4}

• E = {(1,2) , (2,3) , (1,3) , (1,3) , (2,4) , (3,4) , (3,4)} = { e1, e 2, e 3, e 4, e 5,

e 6, e 7 }

2.1.2 Jenis-jenis Graf

Berdasarkan arah dan bobotnya, graf dibagi menjadi empat bagian sebagai

berikut.

1. Graf berarah dan berbobot: tiap edges mempunyai arah dan bobot

Gambar 2.2 Graf berarah dan berbobot

Gambar 2.2 menunjukkan graf berarah dan berbobot yang terdiri dari

tujuh simpul (vertices), yaitu A,B,C,D,E,F,G. Verteks A mempunyai arah

ke verteks B dan verteks C, verteks B mempunyai arah ke verteks D dan

verteks E, dan seterusnya. Bobot antara satu verteks dengan

verteks lain juga diketahui.

     9  

2. Graf tidak berarah dan berbobot: tiap edges tidak mempunyai arah tetapi

mempunyai bobot (nilai).

Gambar 2.3 Graf tidak berarah dan berbobot

Gambar 2.3 menunjukkan graf tidak berarah dan berbobot yang terdiri

dari tujuh titik (vertices), yaitu A,B,C,D,E,F,G. Verteks A tidak

mempunyai arah ke verteks B maupun ke verteks C, tetapi memiliki

bobot pada edgenya, begitu juga yang terjadi dengan verteks- verteks

lainnnya.

3. Graf berarah dan tidak berbobot: tiap edges mempunyai arah tetapi tidak

mempunyai bobot (nilai).

Gambar 2.4 Graf berarah dan tidak berbobot

     10  

Gambar 2.4 menunjukkan graf berarah dan tidak berbobot yang terdiri

dari tujuh titik (vertices), yaitu A,B,C,D,E,F,G. Verteks A mempunyai

arah ke verteks B dan verteks C, tetapi tidak memiliki bobot untuk setiap

edgenya.

4. Graf tidak berarah dan tidak berbobot :

Gambar 2.5 Graf tidak berarah dan tidak berbobot

Gambar 2.5 menunjukkan graf tidak berarah dan tidak berbobot yang

terdiri dari tujuh titik (vertices), yaitu A,B,C,D,E,F,G. Verteks A tidak

mempunyai arah ke verteks B dan verteks C, verteks C juga tidak

memiliki arah dengan verteks D dan verteks B, begitu juga yang terjadi

dengan verteks-verteks lainnya. Setiap edge tidak memiliki nilai.

2.1.2 Representasi Graf

Suatu graf dapat direpresentasikan ke beberapa bentuk. Representasi graf

dapat digunakan untuk mengimplementasikan graf tersebut ke dalam bentuk tertentu,

sehingga dapat digunakan pada berbagai kasus yang berbeda.

     11  

Gambar 2.6 Contoh Graf ABCDEFG

Representasi graf yang sering digunakan adalah sebagai berikut.

a. Matriks Kedekatan (Adjacency Matrix)

Untuk suatu graf dengan jumlah simpul sebanyak n, maka matriks

kedekatan mempunyai ukuran n x n (n baris dan n kolom). Matriks

kedekatan untuk contoh graf ABCDEFG dapat dilihat pada Tabel 2.1.

Tabel 2.1 Matriks kedekatan graf ABCDEFG

A B C D E F G

A 0 1 1 0 0 0 0

B 1 0 0 1 1 0 0

C 1 0 0 1 0 1 0

D 0 1 1 0 0 0 1

E 0 1 0 0 0 0 1

F 0 0 1 0 0 0 1

G 0 0 0 0 1 1 0

     12  

b. Matriks Bersisian (Incidency Matrix)

Untuk suatu graf dengan jumlah simpul sebanyak n dan jumlah sisi

sebanyak m, maka matriks kedekatan mempunyai ukuran n x m (n baris

dan m kolom). Matriks bersisian untuk graf ABCDEFG dapat dilihat

pada tabel 2.2.

Tabel 2.2 Matriks bersisian graf ABCDEFG

e1 e2 e 3 e 4 e 5 e 6 e 7 e 8 e 9

A 1 1 0 0 0 0 0 0 0

B 1 0 1 1 0 0 0 0 0

C 0 1 0 0 1 1 0 0 0

D 0 0 0 1 1 0 0 1 0

E 0 0 1 0 0 0 1 0 0

F 0 0 0 0 0 1 0 0 1

G 0 0 0 0 0 0 1 0 1

c. List Kedekatan (Adjacency List)

Simpul x dapat dianggap sebagai suatu list yang terdiri dari simpul pada

graf yang berdekatan dengan x. Adjacency list untuk graf ABCDEFG

dapat dilihat pada gambar di bawah ini.

Tabel 2.3 Adjacency List graf ABCDEFG

A B,C B A,D,E

     13  

C A,D,F D B,C,E,F,G E B,G F C,G G D,E,F

2.1.3 Graf Euler dan Graf Hamilton

Definisi 2.2 ( Munir , 2009 , p404 )

Lintasan Euler ialah lintasan yang melalui masing-masing sisi di dalam graf

tepat satu kali. Bila lintasan tersebut kembali ke simpul asal, membentuk lintasan

tertutup (sirkuit), maka lintasan tertutup itu dinamakan sirkuit Euler. Jadi, sirkuit

Euler ialah sirkuit melewati masing-masing sisi tepat satu kali.

Gambar 2.7 Lintasan Euler (Munir, 2009, p404)

Lintasan Euler pada Gambar 2.7: 3, 1, 2, 3, 4, 1.

     14  

Gambar 2.8 Sirkuit Euler (Munir, 2009, p405)

Sirkuit Euler pada Gambar 2.8: 1, 2, 3, 4, 7, 3, 5, 7, 6, 5, 2, 6, 1.

Definisi 2.3 ( Munir , 2009 , p408 )

Lintasan Hamilton ialah lintasan yang melalui tiap simpul di dalam graf tepat

satu kali. Bila lintasan itu kembali ke simpul asal membentuk lintasan tertutup

(sirkuit), maka lintasan tertutup itu dinamakan sirkuit Hamilton. Dengan kata lain,

sirkuit Hamilton ialah sirkuit yang melalui tiap simpul di dalam graf tepat satu kali,

kecuali simpul asal (sekaligus simpul akhir) yang dilalui dua kali.

Gambar 2.9 Lintasan Hamilton (Munir, 2009, p409)

     15  

Gambar 2.10 Sirkuit Hamilton (Munir, 2009, p409)

2.2 OPTIMASI

2.2.1 Definisi Masalah Optimasi

Optimasi ialah suatu proses untuk mencapai hasil yang ideal atau optimal

(nilai efektif yang dapat dicapai). Dalam disiplin matematika optimasi merujuk pada

studi permasalahan yang mencoba untuk mencari nilai minimal atau maksimal dari

suatu fungsi riil. Untuk dapat mencapai nilai minimal atau maksimal tersebut, secara

sistimatis dilakukan pemilihan nilai variabel bilangan bulat atau riil yang akan

memberikan solusi optimal.

2.2.2 Macam-macam Permasalahan Optimasi

Permasalahan optimasi mempunyai hubungan yang erat dalam kehidupan

sehari-hari. Nilai optimal yang dapat dioptimasi dapat berupa besaran waktu,

panjang, jarak, dan jadwal. Berikut ini adalah beberapa contoh dari permasalahan

optimasi.

     16  

1. Travelling Salesman Problem

Sebuah permasalahan dalam menentukan lintasan terpendek dari suatu

kota menuju seluruh kota lainnya dan kembali ke kota semula.

2. Quadratic Assignment Problem (QAP)

Sebuah permasalahan untuk mengalokasikan sejumlah n resources untuk

ditempatkan pada sejumlah M lokasi dengan meminimumkan biaya

alokasi.

3. Job Scheduling Problem (JSP)

Sebuah permasalahan untuk menjadwalkan sejumlah j pekerjaan

menggunakan sejumlah m mesin, sehingga seluruh pekerjaan diselesaikan

dengan waktu yang minimal.

4. Pewarnaan graf.

2.2.3 Permasalahan Rute Terpendek

Masalah rute terpendek merupakan masalah yang berkaitan dengan penentuan

edge-edge dalam sebuah graf yang membentuk rute terdekat antara sumber dan

tujuan. Tujuan dari permasalahan rute terpendek adalah mencari rute yang memiliki

jarak terdekat antara titik asal dan titik tujuan.

     17  

Gambar 2.11 Graph ABCDEFG

Pada gambar 2.11 dimisalkan kota A merupakan kota awal dan kota G adalah

kota tujuan. Dari kota awal sampai dengan kota tujuan, dapat dipilih beberapa rute

sebagai berikut.

• A→ B →C → D → E →G

• A→ B →C → D → F →G

• A→ B →C → D →G

• A→ B →C → F →G

• A→ B → D → E →G

• A→ B → D → F →G

• A→ B → D →G

• A→ B → E →G

• A→C → D → E →G

• A→C → D → F →G

• A→C → D →G

• A→C → F →G

     18  

Berdasarkan data di halaman sebelumnya, dapat dihitung rute terpendek

dengan mencari jarak antar rute tersebut. Apabila jarak antar rute belum diketahui,

jarak dapat dihitung berdasarkan koordinat dari kota-kota tersebut, kemudian

dihitung jarak yang paling pendek yang dapat dilalui.

2.2.4 Penyelesaian Masalah Optimasi

Secara umum, penyelesaian masalah pencarian rute terpendek dapat

dilakukan dengan menggunakan dua metode, yaitu metode konvensional dan metode

heuristik.

1. Metode Konvensional adalah metode yang menggunakan matematika

biasa.

Contoh: algoritma Djikstra, algoritma Floyd-Warshall, algoritma

Bellman-Ford.

2. Metode heuristik adalah suatu metode yang merujuk pada metode

komputasi yang mengoptimasi sebuah permasalahan dengan mencoba

secara iteratif mencari kandidat solusi sehingga mendapatkan yang paling

optimal.

Contoh: algoritma genetika dan algoritma Ant Colony Optimization.

(I’ing Mutakhiroh, Indrato, Taufiq Hidayat, 2007)

     19  

2.3 Travelling Salesman Problem

Sebuah permasalahan dalam menentukan lintasan terpendek dari suatu kota

menuju seluruh n kota lainnya dan kembali ke kota semula dengan sekali kunjung

untuk tiap kota.

Permasalahan TSP ini dapat dimisalkan menjadi persoalan pada graph, yaitu

bagaimana menentukan sirkuit hamilton yang memiliki bobot paling minimum pada

graph tersebut.

Misalkan terdapat n buah titik dalam sebuah graph lengkap dengan n verteks , maka

jumlah sirkuit hamiltonnya adalah ( n - 1 ) ! / 2

Contoh :

Gambar 2.8 Graf lengkap (Munir , 2009 , p423)

Graph di atas memiliki ( 4 – 1 ) ! / 2 = 3 sirkuit hamilton

I1 = (a, b, c, d, a) atau (a, d, c, b, a) ==> panjang

= 10 + 12 + 8 + 15 = 45

     20  

I2 = (a, c, d, b, a) atau (a, b, d, c, a) ==> panjang

= 12 + 5 + 9 + 15 = 41

I3 = (a, c, b, d, a) atau (a, d, b, c, a) ==> panjang

= 10 + 5 + 9 + 8 = 32

Jadi dari 3 sirkuit hamilton yang telah didapat, sirkuit hamilton yang paling

pendek adalah I3 = (a, c, b, d, a) atau (a, d, b, c, a) dengan panjang sirkuit =

10 + 5 + 9 + 8 = 32.

2.4 ALGORITMA ANT COLONY

Algoritma Semut (Ant Colony Algorithm) merupakan algoritma yang

terinspirasi dari pengamatan terhadap suatu koloni semut. Semut merupakan hewan

yang hidup sebagai suatu kesatuan dalam koloninya. Suatu perilaku penting dan

menarik untuk ditinjau dari suatu koloni semut adalah perilaku mereka pada saat

mencari makan, terutama bagaimana mereka mampu menemukan rute yang

menghubungkan antara sumber makanan dengan sarang mereka. Ketika berjalan

menuju sumber makanan dan sebaliknya, semut meninggalkan jejak berupa suatu zat

yang disebut pheromone. Semut-semut dapat mencium pheromone, dan ketika

memilih rute yang akan dilalui, semut akan memiliki kecenderungan untuk memilih

rute yang memiliki tingkat konsentrasi pheromone yang tinggi.

     21  

Gambar 2.12 Semut menciptakan solusi, dari sumber menuju tujuan (Dorigo,p10)

Proses peninggalan pheromone ini merupakan salah satu contoh dari proses

stigmergy, yaitu sebuah proses yang meninggalkan jejak pada lingkungan oleh suatu

aksi dan merangsang perkembangan pada aksi berikutnya. Proses peninggalan

pheromone ini sangat berguna bagi semut yang memungkinkan para semut untuk

mengingat jalan pulang ke sarang dan juga memungkinkan para semut

berkomunikasi dengan koloninya.

Seiring waktu, bagaimanapun juga jejak dari pheromone akan menguap dan

akan mengurangi kekuatan daya tariknya. Lebih cepat setiap semut pulang pergi

melalui rute tersebut, maka pheromone yang menguap lebih sedikit. Begitu pula yang

terjadi dengan hal sebaliknya jika semut lebih lama pulang pergi melalui rute, maka

pheromone yang menguap akan lebih banyak.

2.4.1 Cara Kerja Algoritma Semut

Semut secara alamiah dapat mencari jalan terpendek yang menghubungkan

antara sumber makanan dengan sarangnya. Untuk lebih jelasnya diberikan contoh

seperti di halaman berikut.

     22  

Gambar 2.13 Perjalanan semut dari sarang(A) menuju sumber makanan(E) Sumber: ftp://iridia.ulb.ac.be/pub/mdorigo/journals/IJ.10-SMC96.pdf

Gambar 2.9.a di atas menunjukkan ada dua kelompok semut yang sedang

melakukan perjalanan. Kelompok yang berangkat dari bawah yang merupakan

sarang semut dan kelompok lain yang berangkat dari atas yang merupakan sumber

makanan. Pada gambar 2.9.b ada sebuah penghalang (obstacle) yang menghalangi

jalur semut dan membagi jalur semut menjadi 2, yaitu jalur kiri dan jalur kanan.

Semut dengan kecepatan yang sama berjalan sembari meninggalkan jejak pheromone

di jalan yang telah dilewatinya. Gambar 2.9.c terlihat jumlah semut yang lebih

banyak melewati jalur yang kanan, sehingga lebih banyak jejak pheromone yang

tertinggal.

Untuk lebih mudah membayangkan sistem koloni semut, lihatlah pemodelan

dari sistem koloni semut seperti gambar yang ada di bawah ini.

     23  

Gambar 2.14 Permodelan Sistem Koloni Semut Sumber: ftp://iridia.ulb.ac.be/pub/mdorigo/journals/IJ.10-SMC96.pdf

Misalkan jarak antara D dan H, antara B dan H, dan antara B dan D

(melalui C) adalah sama besar yaitu 1. Misalkan C berada dalam pertengahan jalan

antara D dan B (Gambar 2.10a). Misalkan juga ada 30 semut yang datang menuju B

dari A, dan 30 semut menuju D dari E pada suatu waktu yang bergerak dengan

kecepatan sama, dan setiap langkah semut akan meninggalkan jejak pheromone.

Pada gambar 2.10.b menunjukkan waktu pada saat t=0. Dalam keadaan ini

tidak ada jejak feromon sama sekali pada seluruh edge, oleh karena itu kemungkinan

untuk memilih jalur kanan dan kiri adalah sama besar.

Pada gambar 2.10.c menunjukkan waktu pada saat t=1. Dalam keadaan ini

jejak pheromone pada jalur yang lebih pendek akan lebih kuat, oleh karena itu lebih

banyak semut memilih jalur kanan, yang merupakan jalur terpendek.

     24  

Semakin sedikit semut yang melalui suatu jalur, maka semakin sedikit pula

pheromone yang ditinggalkan, dan pada akhirnya jejak pheromon akan benar-benar

hilang ketika tidak ada semut lagi yang memilih jalur tersebut.

2.5 Algoritma Elitist Ant System

Algoritma Elitist Ant System merupakan pengembangan dari algoritma Ant

System. Pada dasarnya algoritma Elitist Ant System memiliki similiaritas atau

kesamaan dengan algoritma Ant System dalam menyelesaikan permasalahan TSP.

Yang membedakan antara keduanya adalah pada saat perhitungan perubahan nilai

intensitas jejak pheromone antar kota. Pada algoritma Elitist Ant System terjadi

penambahan sebesar e / Lbs pada edge-edge yang merupakan rute terbaik, dimana e

adalah parameter yang menunjukkan adanya rute terbaik dan Lbs adalah panjang rute

terbaik.

Dalam algoritma Elitist Ant System, diperlukan beberapa variabel dan

langkah-langkah untuk menentukan jalur terpendek sebagai berikut.

Langkah 1 : Penetapan parameter dan nilai pheromone awal

a. Inisialisasi harga parameter-parameter algoritma.

Parameter-parameter yang diinisilisasikan adalah:

1. Intensitas jejak semut antar kota dan perubahannya (τij)

2. Banyak kota (n) termasuk x dan y (koordinat) atau dij (jarak antar

kota)

     25  

3. Penentuan kota berangkat dan kota tujuan

4. Tetapan siklus-semut (Q)

5. Tetapan pengendali intensitas jejak semut (α)

6. Tetapan pengendali visibilitas (β)

7. Visibilitas antar kota = 1/dij (ηij)

8. Jumlah semut (m)

9. Tetapan penguapan jejak semut (ρ)

10. Jumlah siklus maksimum (NCmax) bersifat tetap selama algoritma

dijalankan. sedangkan τij akan selalu diperbaharui harganya pada

setiap siklus algoritma mulai dari siklus pertama (NC=1) sampai

tercapai jumlah siklus maksimum (NC=NCmax) atau sampai

terjadi konvergensi.

b. Inisialisasi titik pertama setiap semut

Pengisian kota pertama ke dalam tabu list. Hasil inisialisasi kota pertama

semut pada langkah 1 harus diisikan sebagai elemen pertama tabu list.

Hasil dari langkah ini adalah terisinya elemen pertama tabu list setiap

semut dengan indeks kota pertama.

Langkah 2 : Penyusunan kunjungan

Penyusunan jalur kunjungan setiap semut ke setiap kota. Koloni semut yang

sudah terdistribusi ke kota tujuan. Kemudian dari kota kedua, masing-masing koloni

semut akan melanjutkan perjalanan dengan memilih salah satu dari kota-kota yang

tidak terdapat pada tabu k sebagai kota tujuan selanjutnya. Perjalanan pertama semut

     26  

akan mulai melakukan perjalanan dari kota pertama sebagai kota asal dan salah satu

kota lainnya sebagai kota koloni semut berlangsung terus-menerus hingga mencapai

kota yang telah ditentukan. Jika s menyatakan indeks urutan kunjungan, kota asal

dinyatakan sebagai tabuk(s) dan kota-kota lainnya dinyatakan sebagai {N-tabuk},

maka untuk menentukan kota tujuan digunakan persamaan probabilitas kota untuk

dikunjungi sebagai berikut.

= 0, untuk lainnya

dengan i sebagai indeks kota asal dan j sebagai indeks kota tujuan.

Langkah 3 : Mencari rute terbaik

a. Perhitungan panjang jalur setiap semut.

Perhitungan panjang jalur tertutup (length closed tour) atau Lk setiap

semut dilakukan setelah satu siklus diselesaikan oleh semua semut.

Perhitungan dilakukan berdasarkan tabuk masing-masing dengan

persamaan berikut:

dengan dij adalah jarak antara kota i ke kota j yang dihitung berdasarkan

persamaan :

     27  

b. Perhitungan rute terpendek

Setelah Lk setiap semut dihitung, akan diperoleh harga minimal

panjang jalur tertutup setiap siklus atau LminNC dan harga minimal

panjang jalur tertutup secara keseluruhan adalah atau Lmin.

Langkah 4 : Perubahan Intensitas Pheromone

Perhitungan harga intensitas jejak kaki semut antar kota untuk siklus

selanjutnya. Harga intensitas jejak kaki semut antar kota pada semua lintasan antar

kota ada kemungkinan berubah, karena adanya penguapan dan perbedaan jumlah

semut yang melewati. Untuk siklus selanjutnya, semut yang akan melewati lintasan

tersebut harga intensitasnya telah berubah. Harga intensitas jejak kaki semut antar

kota untuk siklus selanjutnya dihitung dengan persamaan:

dengan adalah perubahan harga intensitas jejak pheromone antar kota

setiap semut dan yang dihitung berdasarkan persamaan dan

untuk edge yang memiliki tur terbaik

lainnya

Langkah 5 : Penyelesaian

Tabu list dikosongkan kembali untuk diisi dengan urutan titik baru pada

iterasi selanjutnya, jika NCmax belum tercapai atau belum terjadi konvergensi

(semua semut hanya menemukan satu tour yang sama dengan jarak yang sama pula).

Algoritma diulang lagi dari langkah 2 dengan harga parameter intensitas pheromone

     28  

antar titik yang sudah diperbaharui. Perhitungan akan dilanjutkan hingga semut telah

menyelesaikan perjalanannya mengunjungi tiap-tiap titik. Hal ini akan berulang

hingga sesuai dengan NCmax yang telah ditentukan atau telah mencapai

konvergensi. Kemudian akan ditentukan jarak terpendek dari masing-masing iterasi.

Jarak terpendek inilah yang merupakan solusi terbaik dari algoritma Elitist Ant

System.

2.6 Software Engineering (Rekayasa Piranti Lunak)

Menurut Fritz Bauer (Pressman, 2001, p19), rekayasa piranti lunak adalah

penetapan dan pemakaian prinsip-prinsip rekayasa dengan tujuan mendapatkan

piranti lunak yang ekonomis, terpercaya, dan bekerja efisien pada mesin yang

sebenarnya (komputer).

Rekayasa piranti lunak terbagi menjadi 3 lapisan yang mampu mengontrol

kualitas dari piranti lunak (Pressman, 2001, p19), yaitu:

a. Proses (Process)

Proses merupakan lapisan paling dasar dalam rekayasa piranti lunak. Proses

dari rekayasa piranti lunak adalah perekat yang menyatukan lapisan-lapisan

teknologi dan memungkinkan pengembangan yang rasional dan periodik dari

pirantik lunak komputer.

b. Metode (Methods)

Metode dari rekayasa piranti lunak menyediakan secara teknis bagaimana

membangun sebuah piranti lunak. Metode meliputi sekumpulan tugas yang

     29  

luas, termasuk di dalamnya analisis kebutuhan, perancangan, konstruksi

program, pengujian, dan pemeliharaan. Metode dari rekayasa piranti lunak

bergantung pada sekumpulan prinsip dasar masing-masing area teknologi dan

memasukkan pemodelan aktivitas, serta teknik deskriptif lainnya.

c. Alat Bantu (Tools)

Alat bantu dari rekayasa piranti lunak menyediakan dukungan otomatis atau

semi otomatis untuk proses dan metode. Ketika alat bantu diintegrasi,

informasi akan diciptakan oleh sebuah alat bantu yang dapat digunakan oleh

lainnnya, sebuah sistem untuk mendukung pengembangan piranti lunak, yang

juga disebut computer-aided software engingeering(CASE). CASE

menggabungkan piranti lunak, perangkat keras, dan database piranti lunak

untuk menciptakan lingkungan rekayasa piranti lunak yang sejalan dengan

CAD / CAE (computer-aided design/engineering) untuk perangkat keras.

Dalam perancangan piranti lunak, dikenal linear sequential model atau yang

lebih dikenal dengan sebutan classic life cycle atau waterfall model. Model ini

menyarankan pendekatan yang sistematik dan berurutan dalam pengembangan

piranti lunak yang melalui analisis, desain, pengkodean, pengujian, dan

pemeliharaan. Model ini meliputi serangkaian aktivitas, yaitu:

a. Rekayasa dan pemodelan sistem

Karena piranti lunak merupakan sebuah bagian dari sistem yang besar, maka

yang perlu dilakukan pertama kali adalah menetapkan kebutuhan untuk

seluruh elemen sistem dan mengalokasikan sebagian dari kebutuhan tersebut

ke piranti lunak.

     30  

b. Analisis kebutuhan piranti lunak

Untuk dapat mengerti inti dari program yang dibangun, diperlukan pengertian

akan informasi yang diperlukan oleh piranti lunak.

c. Perancangan

Perancangan piranti lunak sebenarnya merupakan sebuah proses yang terdiri

dari banyak kegiatan, yang menitikberatkan pada 4 atribut dari program,

yaitu: struktur data, arsitektur piranti lunak, representasi tampilan, dan detil

prosedur.

d. Pengkodean

Dalam pengkodean, perancangan yang telah dilakukan diterjemahkan ke

bentuk yang dimengerti komputer.

e. Pemeliharaan

Pemeliharaan dilakukan untuk mengantisipasi terjadinya kesalahan, karena

perubahan sistem atau peningkatan kebutuhan pengguna akan fungsi baru.

Gambar 2.15 Waterfall Model (Pressman, 2002, p29)

     31  

2.7 Flowchart

Salah satu bentuk untuk menyatakan alur pikiran dalam menyelesaikan suatu

pekerjaan adalah dalam bentuk gambar atau bagan yang disebut program flowchart

atau bagan alir program (Moh. Sjukani, 2004, p5). Berikut adalah simbol-simbol

yang digunakan untuk menggambarkan diagram alir.

Tabel 2.4 Tabel simbol flowchart (Sumber: Moh. Sjukani, 2004,p9)

Notasi Arti Notasi Terminal, untuk menyatakan mulai dan selesai sebagai tanda, tidak melakukan suatu pekerjaan khusus. Process, untuk menyatakan assignment statement.

Input/Output operation, untuk menyatakan proses baca da 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.

2.8 State Transition Diagram

State Transition Diagram (STD) adalah kumpulan keadaan/atribut yang

menggambarkan seseorang atau suatu benda pada waktu tertentu, bentuk keberadaan

     32  

atau kondisi tertentu, seperti menunggu instruksi berikutnya, menunggu pengisian

password, dan lain-lain.

STD merupakan modelling tools yang sangat kuat untuk mendeskripsikan

kelakukan yang dibutuhkan pada sistem yang mempunyai sifat real-time dan juga

bagian interface manusia pada berbagai sistem online. Cara kerja sistem ini ada dua

macam sebagai berikut.

• Passive

Sistem ini melakukan kontrol terhadap lingkungan, tetapi lebih

bersifat memberikan atau menerima data. Kontrol suatu sistem

bertugas mengumpulkan/menerima data melalui sinyal yang dikirim

oleh satelit.

• Active

Sistem ini melakukan kontrol terhadap lingkungan secara aktif dan

dapat memberikan respon terhadap lingkungan sesuai dengan program

yang ditentukan.

Komponen-komponen utama STD sebagai berikut.

1. State

State adalah kumpulan atribut yang mencirikan seseorang atau suatu

benda pada waktu atau kondisi tertentu.

2. Transition State

Transition State yang diberi label dengan ekspresi atau arah, label

tersebut menunjukkan kejadian yang menyebabkan transisi terjadi.

     33  

3. Condition dan Action

Condition adalah suatu peristiwa pada lingkungan eksternal yang

dapat dideteksi oleh sistem. Dan action adalah apa yang dilakukan

oleh sistem apabila terjadi perubahan state, atau bisa juga dikatakan

sebagai reaksi sistem terhadap suatu kondisi, aksi akan menghasilkan

keluaran/tampilan.