BAB 2 LANDASAN TEORI

BAB 2

LANDASAN TEORI

2.1 Teori Graf

Teori graf merupakan pokok bahasan yang banyak penerapannya pada masa kini [2]. Pemakaian teori graf telah banyak dirasakan dalam berbagai ilmu, antara lain: optimisasi jaringan, ekonomi, psikologi, genetika, riset operasi (OR), dan lain-lain. Makalah pertama tentang teori graf ditulis pada tahun 1736 oleh seorang matematikawan Swiss yang bernama Leonard Euler. Ia menggunakan teori graf untuk menyelesaikan masalah jembatan Königsberg [5] (sekarang, bernama Kaliningrad). Berikut adalah ilustrasi masalah tersebut:

Gambar 2.1 Masalah Jembatan Königsberg Masalah yang dikemukakan Euler: Dapatkah melewati setiap jembatan tepat sekali dan kembali lagi ke tempat semula? Berikut adalah sketsa yang merepresentasikan ilustrasi jembatan Königsberg yang pada gambar diatas. Himpunan titik yaitu {A, B, C, D} merepresentasikan sebagai daratan, dan garis yang menghubungkan titik-titik tersebut adalah sebagai jembatan.

Universitas Sumatera Utara

Gambar 2.2 Representasi Graf dari Masalah Jembatan Königsberg Jawaban pertanyaan Euler adalah tidak mungkin. Agar bisa melalui setiap jembatan tepat sekali dan kembali lagi ke tempat semula maka jumlah jembatan yang menghubungkan setiap daratan harus genap.

2.1.1 Definisi Graf

Graf merupakan struktur diskrit yang terdiri himpunan sejumlah berhingga obyek yang disebut simpul (vertices, vertex) dan himpunan sisi (edges) yang menghubungkan simpul-simpul tersebut [8]. Graf digunakan untuk merepresentasikan objek-objek diskrit dan hubungan antara objek-objek tersebut. Notasi sebuah graf adalah G = (V, E), dimana: •

V merupakan himpunan tak kosong dari simpul-simpul (vertices), misalkan V = { v1 , v2 , ... , vn }

•

E merupakan himpunan sisi – sisi (edges) yang menghubungkan sepasang simpul, misalkan E = {e1 , e2 , ... , en }

Contoh: Graf dari masalah jembatan Königsberg dapat disajikan sebagai berikut:


Gambar 2.3 Graf dari Masalah Jembatan Königsberg

2.1.2 Macam – macam Graf

Macam – macam graf menurut arah dan bobotnya, graf dibagi menjadi empat bagian [8], yaitu: 1) Graf berarah dan berbobot: setiap edge mempunyai arah (yang ditunjukkan dengan anak panah) dan bobot. Gambar 2.4 adalah contoh graf berarah dan berbobot yang terdiri dari tujuh vertek yaitu vertek A, B, C, D, E, F, G. Vertek A mempunyai dua edge yang masing – masing menuju ke vertek B dan vertek C, vertek B mempunyai tiga edge yang masing – masing menuju ke vertek C, vertek D dan vertek E. Bobot antara vertek A dan vertek B pun telah di ketahui.

Gambar 2.4 Graf Berarah dan Berbobot

2) Graf tidak berarah dan berbobot: setiap edge tidak mempunyai arah tetapi mempunyai bobot. Gambar 2.5 adalah contoh graf tidak berarah dan berbobot.


Graf terdiri dari tujuh vertek yaitu vertek A, B, C, D, E, F, G. Vertek A mempunyai dua edge yang masing – masing berhubungan dengan vertek B dan vertek C, tetapi dari masing – masing edge tersebut tidak mempunyai arah. Edge yang menghubungkan vertek A dan vertek B mempunyai bobot yang telah diketahui begitu pula dengan edge – edge yang lain.

Gambar 2.5 Graf Tidak Berarah dan Berbobot 3) Graf berarah dan tidak berbobot: setiap edge mempunyai arah tetapi tidak mempunyai bobot. Gambar 2.6 adalah contoh graf berarah dan tidak berbobot.

Gambar 2.6 Graf Berarah dan Tidak Berbobot 4) Graf tidak berarah dan tidak berbobot: setiap edge tidak mempunyai arah dan tidak terbobot. Gambar 2.7 adalah contoh graf tidak berarah dan tidak berbobot.


Gambar 2.7 Graf Tidak Berarah dan Tidak Berbobot

2.1.3 Matriks Ketetanggaan (adjacency matrix) dan Matriks Bersisian (incidency matrix) dari Suatu Graf •

Matriks bertetanggaan Dua buah simpul dikatakan bertetangga jika kedua simpul tersebut terhubung

langsung oleh suatu sisi [8]. Matriks ketetanggaan untuk graf sederhana merupakan matriks busur sangkar yang unsur-unsurnya hanya terdiri dari dua bilangan yaitu 0 (nol) dan 1 (satu). Baris dan kolom pada matriks ini, masing-masing merupakan representasi dari setiap simpul pada graf tersebut. Misalkan 𝑎𝑎𝑖𝑖𝑖𝑖 merupakan unsur pada matriks tersebut, maka:

a) Jika 𝑎𝑎𝑖𝑖𝑖𝑖 = 1 maka hal ini berarti simpul i dan simpul j bertetangga.

b) Jika 𝑎𝑎𝑖𝑖𝑖𝑖 = 0 maka hal ini berarti simpul i dan simpul j tidak bertetangga. Contoh:

Perhatikan graf sederhana berikut ini:

Gambar 2.8 Graf Sederhana

Matriks ketetanggaan dari graf tersebut adalah sebagai berikut:


Tabel 2.1 Matriks Ketetanggaan dari Graf Sederhana P

Q

R

S

A

0

1

0

1

B

1

0

1

1

C

0

1

0

1

D

1

1

1

0

Terlihat bahwa matriks tersebut simetris dan setiap unsur diagonalnya adalah nol (0). Matriks ketetanggaan untuk graf tak sederhana merupakan matriks bujur sangkar yang unsur-unsurnya hanya terdiri dari bilangan 0 (nol), 1 (satu) dan 2 (dua). Baris dan kolom pada matriks ini, masing-masing merupakan representasi dari setiap simpul pada graf tersebut. Misalkan 𝑎𝑎𝑖𝑖𝑖𝑖 merupakan unsur pada matriks tersebut, maka:

a) Jika 𝑎𝑎𝑖𝑖𝑖𝑖 = n maka hal ini berarti simpul i dan simpul j bertetangga oleh n buah sisi.

b) Jika 𝑎𝑎𝑖𝑖𝑖𝑖 = 0 maka hal ini berarti simpul i dan simpul j tidak bertetangga. Contoh:

Perhatikan graf dari masalah jembatan Königsberg:

Gambar 2.9 Graf dari Masalah Jembatan Königsberg Matriks ketetanggaan dari graf tersebut adalah sebagai berikut: Tabel 2.2 Matriks ketetanggaan Graf dari Masalah Jembatan Königsberg P

Q

R

S

A

0

2

2

1

B

2

0

1

1

C

2

1

0

1

D

1

1

1

0


•

Matriks Bersisian

Sementara itu, suatu sisi e dikatakan bersisian dengan simpul v1 dan simpul v2 jika e menghubungkan kedua simpul tersebut, dengan kata lain e = (v1, v2) [8]. Seperti halnya matriks ketetanggaan, unsur-unsur matriks bersisian pun hanya terdiri dari dua bilangan yaitu 0 (nol) dan 1 (satu), tapi tidak harus bujur sangkar. Hal ini disebabkan, baris dan kolom pada matriks bersisian, masing-masing merepresentasikan simpul dan sisi pada graf yang dimaksud. Misalkan 𝑎𝑎𝑖𝑖𝑖𝑖 merupakan unsur pada matriks tersebut, maka:

a) Jika 𝑎𝑎𝑖𝑖𝑖𝑖 = 1 maka hal ini berarti simpul ke-i dan sisi ke-j adalah bersisian.

b) Jika 𝑎𝑎𝑖𝑖𝑖𝑖 = 0 maka hal ini berarti simpul ke-i dan sisi ke-j tidak bersisian. Contoh:

Perhatikan graf berikut ini:

Gambar 2.10 Graf dari Masalah Jembatan Königsberg Bentuk matriks bersisian dari graf tersebut adalah: Tabel 2.3 Matriks Bersisian Graf dari Masalah Jembatan Königsberg

A

𝒆𝒆𝒆𝒆 𝒆𝒆𝒆𝒆 𝒆𝒆𝒆𝒆 𝒆𝒆𝒆𝒆 𝒆𝒆𝒆𝒆 𝒆𝒆𝒆𝒆 𝒆𝒆𝒆𝒆 1

1

1

1

0

1

0

B

0

0

1

1

1

0

0

C

1

1

0

0

0

0

1

D

0

0

0

0

1

1

1


2.1.4 Lintasan dan Sirkuit Euler serta Lintasan dan Sirkuit Hamilton •

Lintasan dan Sirkuit Euler

Lintasan Euler dalam suatu graf merupakan lintasan yang melalui masing-masing sisi di dalam graf tersebut tepat satu kali [8]. Jika lintasan tersebut kembali kesimpul awal sehingga membentuk lintasan tertutup (sirkuit) maka lintasan ini dinamakan sirkuit Euler. Dengan demikian, sirkuit Euler merupakan sirkuit yang melewati masingmasing sisi tepat satu kali. Graf yang memuat sirkuit Euler dinamakan graf Euler (Eulerian graph), sedangkan graf yang memuat lintasan Euler dinamakan graf semi Euler (semi-Eulerian graph).

Contoh: Perhatikan graf berikut ini:

Gambar 2.11 Graf Euler Graf G1 merupakan graf Euler karena memiliki lintasan yang membentuk lintasan tertutup (sirkuit), yaitu: pr – rt – ts – sq – qt – tp. Sementara itu,

Gambar 2.12 Graf Semi Euler Terlihat bahwa graf G2 merupakan graf semi Euler karena graf tersebut memiliki lintasan yang melalui masing-masing sisi didalam graf tersebut tepat satu kali. Lintasan tersebut adalah: pq – qs – st – tp – pr – rt – tq.


•

Lintasan dan Sirkuit Hamilton

Lintasan Hamilton suatu graf merupakan lintasan yang melalui setiap simpul dalam graf tersebut tepat satu kali [8]. Jika lintasan tersebut kembali kesimpul awal, sehingga membentuk lintasan tertutup (sirkuit) maka lintasan ini dinamakan sirkuit Hamilton. Dengan demikian, sirkuit Hamilton merupakan sirkuit yang melewati masingmasing sisi tepat satu kali. Graf yang memuat sirkuit Hamilton dinamakan graf Hamilton (Hamiltonian graph), sedangkan graf yang memuat lintasan Hamilton dinamakan graf semi Hamilton (semi- Hamiltonian graph).

Contoh: Perhatikan tiga graf di bawah ini:

Gambar 2.13 graf Graf G1 merupakan graf semi Hamilton, lintasan hamiltonya adalah: s – r – p – q – r. Sedangkan graf G2 merupakan graf Hamilton, sirkuit hamiltonya adalah: t–p–r–q–p–s–q–t. Sementara itu pada graf G3 tidak terdapat lintasan maupun sirkuit Hamilton.

2.2 Optimasi

2.2.1 Definisi


Optimasi merupakan masalah yang berhubungan dengan keputusan yang terbaik, maksimum, minimum dan

memberikan cara penentuan solusi yang

memuaskan [7].

2.2.2 Permasalahan Optimasi

Permasalahan 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 termasuk beberapa persoalan optimisasi [7]: •

Menentukan lintasan terpendek dari suatu tempat ke tempat yang lain.

•

Menentukan jumlah pekerja seminimal mungkin untuk melakukan suatu proses produksi agar pengeluaran biaya pekerja dapat diminimalkan dan hasil produksi tetap maksimal.

•

Mengatur rute kendaraan umum agar semua lokasi dapat dijangkau.

•

Mengatur routing jaringan kabel telepon agar biaya pemasangan kabel tidak terlalu besar dan penggunaannya tidak boros.

2.3 Travelling Salesman Problem

Travelling Salesman Problem merupakan permasalahan pencarian jalur terdekat dari satu titik ke satu titik itu lagi [3]. Penyelesaian persoalan ini melibatkan banyak lintasan dengan jarak yang berbeda. Solusi merupakan salah satu dari sekian banyak alternatif jalur yang diambil. Pencarian jalur terdekat (TSP) dapat diaplikasikan dalam banyak hal, karena itu sampai saat ini penyelesaian yang paling baik masih terus dicari. Berbagai metode sudah ada dan dapat digunakan untuk menyelesaikan persoalan ini. Metode-metode tersebut bervariasi kompleksitas algoritmanya.

2.4 Algoritma Ant Colony


Ant Colony diadopsi dari perilaku koloni semut yang dikenal sebagai sistem semut [4]. Secara alamiah Ant Colony mampu menentukan 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 dilalui. Semakin banyak semut yang melalui lintasan maka akan semakin jelas jejak kakinya. Hal ini akan menyebabkan lintasan yang dilalui semut dalam jumlah sedikit, semakin lama akan semakin berkurang kepadatan semut yang melewatinya, atau bahkan akan tidak dilewati sama sekali, dan sebaliknya, lintasan yang dilalui semut dalam jumlah banyak, semakin lama akan semakin bertambah kepadatan semut yang melewatinya, atau bahkan semua semut akan melalui lintasan tersebut. Mengingat prinsip algoritma yang didasarkan pada perilaku koloni semut dalam menemukan jarak perjalanan paling pendek tersebut, Ant Colony sangat tepat digunakan untuk diterapkan dalam penyelesaian masalah optimasi, salah satunya adalah untuk menentukan jalur terpendek. Secara alamiah koloni semut mampu menemukan rute terpendek dalam perjalanan dari sarang ke tempat-tempat sumber makanan. Sebagai ilustrasi koloni semut dalam pencarian rute terpendek dapat dilihat pada Gambar 2.14.

Gambar 2.14 Koloni semut. Tabel 2.4 merupakan representasi koloni semut dalam dunia nyata dan saat diimplementasikan pada Algoritma Ant Colony.


Tabel 2.4 Tabel representasi koloni semut No

Kenyataan

ACO

1

Habitat alamai

2

Sarang dan makanan

3

Koloni semut

Agents

4

Visibilitas

1/jarak(n)

5

Feromon

Feromon buatan;(г)

Perilaku mencari

Perjalanan secara acak melalui

makanan

graf

6

Graf Node pada graf; asal dan tujuan

2.4.1 Skema Algoritma Ant Colony

Secara logika dan matematik semut-semut dari titik asal yang sama, misalnya sarang, bergerak sendiri-sendiri melewati jalur masing-masing menuju makanan sebagai titik tujuannya. Setelah mereka sampai pada titik tujuan, semut-semut ini di data satu per satu untuk mengetahui jalur yang dilalui beserta jaraknya. Semut yang menempuh jarak terpendek adalah pemenangnya dan jalur yang dilaluinya ditetapkan sebagai jalur terpendek. Berikut adalah tahapan-tahapan algoritma semut dalam graf:

Gambar 2.15 Perjalanan semut


a) Pada gambar 2.15.a menunjukkan semut yang akan melakukan perjalanan mencari tempat dimana ada makanan, dari X menuju Y. b) Semut akan melakukan gerakan secara acak menuju tempat makanan dengan jalur masing-masing. Seperti pada gambar 2.15.b semut berjalan dengan jalurnya masing-masing. c) Setelah berjalan secara acak berdasarkan jalurnya masing-masing kemudian semut-semut tersebut akan bertemu lagi dimana tempat makanan berada seperti pada gambar 2.15.c d) Pada saat melakukan perjalanan melalui jalurnya masing-masing, semut meninggalkan feromon sebagai jejak yang akan diikuti oleh semut yang lainnya. Semakin banyak semut dan semakin dekat jarak yang ditempuh maka feromon juga semakin kuat sehingga semut yang lainnya akan mengikuti jalur tersebut. e) Pada optimisasi algoritma Ant Colony, proses tadi akan dilakukan secara berulang sesuai dengan siklus maksimum yang telah ditentukan.

Pencarian solusi masalah rute terpendek dengan menggunakan algoritma Ant Colony dimulai dengan meletakkan seekor semut pada sembarang vertex awal. Selanjutnya semut tersebut akan memilih vertex berikutnya berdasarkan pengaruh jumlah pheromone yang terakumulasi pada setiap edge yang berpangkal pada vertex tersebut. Semut kemudian seolah-olah melalui edge tersebut untuk menuju vertex berikutnya, dengan meletakkan sejumlah pheromone (local updating) berdasarkan formula [7]: τrs ←�1-ε�.τrs +ε.τ0 dengan τ0 =

……...……………….. (2.1)

1 nCnn

dimana: τrs

= intensitas jejak semut (pheromone) antara titik r dan titik s

ε

= parameter penguapan (evaporasi) pheromone lokal

τ0

= intensitas jejak semut (pheromone) awal

n

= jumlah titik

Cnn

= panjang sebuah lintasan terbaik


Langkah-langkah dalam menjalankan algoritma Ant Colony: 1.

Set jumlah semut, pheromone awal pada setiap edge, jumlah iterasi

2.

Lakukan sebanyak jumlah iterasi yang diinginkan

3.

Lakukan untuk setiap semut letakkan setiap semut pada setiap node awal.

4.

Lakukan pencarian rumah sakit berikutnya, lakukan local updating sampai semua semut mengunjungi semua node.

5.

Catat rute terpendek yang didapat lakukan global updating sampai batas iterasi.

Selanjutnya pada setiap akhir iterasi akan dilakukan evaluasi untuk menentukan lintasan yang terbaik dan untuk membuat lintasan tersebut menjadi sedikit kurang disenangi pada iterasi berikutnya, maka dilakukan global updating yang diaplikasikan hanya kepada lintasan yang terbaik sampai dengan iterasi tersebut dengan mengunakan formula [7]: τrs ←�1-ρ�.τrs +ρ.∆τbest rs 1

best dengan ∆τbest rs = �C 0

dimana:

……...……………….. (2.2)

jika (r,s) ∈ lintasan terbaik keseluruhan

τrs

= intensitas jejak semut (pheromone) antara titik r dan titik s

ρ

= parameter penguapan (evaporasi) pheromone global

Cbest

= panjang lintasan terbaik keseluruhan

2.5 Android

Android adalah sistem operasi Mobile Phone berbasiskan Linux [12]. Android bersifat open source yang source codenya diberikan secara gratis bagi para pengembang untuk menciptakan aplikasi mereka agar dapat berjalan di Android.


2.5.1 Features

Features yang terdapat pada android itu sendiri adalah: Framework Aplikasi, Mesin Virtual Dalvik, Integrated browser, Grafis, SQLite, Media support, GSM Telephony, Bluetooth, EDGE, 3G dan WiFi, Multi-touch, serta Lingkungan Development Market. Android bukan sekedar hanya untuk perangkat mobile saja. Android merupakan sebuah sistem operasi yang dikemas sedemikian rupa sehingga dapat digunakan untuk berbagai perangkat yang menggunakan layar mobile. Berikut penjelasan mengenai layer arsitektur android: a. Applications Android akan menggabungkan dengan serangkaian aplikasi inti termasuk klien email, program SMS, kalender, peta, browser, kontak, dan lain-lain. b. Application Framework: Dengan menyediakan sebuah platform pengembangan yang terbuka, pengembang Android menawarkan kemampuan untuk membangun aplikasi yang sangat kaya dan inovatif. c. Libraries Android termasuk satu set pustaka C/C++ yang digunakan oleh berbagai komponen sistem Android. d. Android Runtime Android termasuk satu set perpustakaan inti yang menyediakan sebagian besar fungsi yang tersedia di perpustakaan inti dari bahasa pemrograman Java. e. Linux Kernel Android bergantung pada Linux versi 2.6 untuk layanan sistem inti seperti keamanan, manajemen memori, manajemen proses, network stack, dan model pengemudi. Kernel juga bertindak sebagai lapisan abstraksi antara hardware dan seluruh software stack.

2.5.2 Arsitektur Android


Google mengibaratkan Android sebagai sebuah tumpukan software. Setiap lapisan dari tumpukan ini menghimpun beberapa program yang mendukung fungsi-fungsi spesifik dari sistem operasi. Berikut ini susunan dari lapisan – lapisan tersebut jika di lihat dari lapisan dasar hingga lapisan teratas: a. Linux Kernel b. Android Runtime c. Libraries d. Application Framework e. Application

Gambar 2.16 Arsitektur Android [6]

1. Linux Kernel Android menggunakan Kernel Linux versi 2.6 sebagai sistem utama. Fungsi kernel yang digunakan antara lain untuk keamanan, manajemen memori, manajemen proses, manajemen jaringan dan driver model. Kernel juga berfungsi sebagai layer abstrak antara hardware dan lapisan lainnya pada software stack.

2. Android Runtime Tiap aplikasi pada Android memiliki prosesnya masing-masing. Tiap aplikasi tersebut memiliki instan dari Dalvik virtual machine (VM). Dalvik virtual machine dirancang


agar suatu device dapat menjalankan beberapa VM secara efisien. Dalvik VM mengeksekusi file dengan format Dalvik Executable format (.dex) yang dirancang untuk meminimalkan memory footprint. Dalvik VM berbasis register, dan dapat menjalankan kelas-kelas yang dikompilasi dengan bahasa pemrograman java dan ditransformasikan menjadi format .dex. Dalvik VM sendiri bergantung pada Kernel Linux untuk fungsi dasarnya, seperti threading dan manajemen memori secara lowlevel.

3. Libraries Android mendukung beberapa library C/C++ yang digunakan pada berbagai komponen Android. Kemampuan ini dapat diakses oleh developer melalui Android application framework. Beberapa library diantaranya adalah : - System C library. Implementasi library C standar (libc). - Media Libraries. Mendukung berbagai format multimedia (termasuk MPEG4, H.264, MP3, AAC, AMR, JPG, PNG). - Surface Manager. Mengatur akses ke subsistem display. - LibWebCore. Engine web browser modern. - SGL. Engine grafis 2D. - 3D Library. Implementasi OpenGL ES 1.0 yang mendukung akselerasi hardware. - FreeType. Rendering untuk bitmap dan vector font. - SQLite. Basis data relasional yang kecil namun sangat ampuh.

4. Application Framework Lapisan ini berisi sekumpulan API yang dapat digunakan oleh programmer maupun core application dari Android. Lapisan ini dirancang untuk memudahkan penggunaan komponen dari Android sendiri. Aplikasi manapun dalam Android dapat berbagi fungsi sehingga aplikasi lain dapat memanfaatkannya. Aplikasi pada Android disusun atas beberapa komponen: a) Sekumpulan Views. Digunakan untuk mengatur tampilan pada aplikasi. Contohnya adalah lists, grids, text box, button, bahkan embeddable web browser. b) Content providers.


Komponen yang mengatur agar aplikasi dapat mengakses resources dari aplikasi lain (seperti Contacts), atau berbagi data dengan aplikasi lain. c) Resource Manager. Menyediakan akses ke pada resource non-code seperti localized string, grafik dan file layout. d) Notification Manager. Memungkinkan agar suatu aplikasi dapat menampilkan peringatan yang dapat dikostumasi pada status bar. e) Activity Manager. Mengatur siklus aplikasi dan navigasi antar aplikasi yang sedang berjalan.

5. Application Application merupakan program yang langsung berhubungan dengan user. Baik program yang merupakan bawaan dari Android sendiri maupun program yang dibuat oleh developer menggunakan bahasa pemrograman java. Contoh program bawaan dari platform Android sendiri adalah email client, program SMS, calendar, maps, web browser, contact dan sebagainya.

2.5.3 The Dalvik Virtual Machine (DVM)

Android berjalan di dalam DVM bukan pada Java Virtual Machine (JVM) yang dikira selama ini [13]. Banyak kesamaan antara DVM dan JVM, namun DVM memiliki feature yang lebih baik dibandingkan dengan JVM untuk perangkat mobile. DVM adalah register bases sementara JVM adalah stack based, DVM didesain dan ditulis oleh Dan Bornsten dan beberapa engineers Google lainnya. Dalam mengatasi fungsionalitas tingkat rendah, DVM menggunakan kernel Linux untuk keamanan, threading, proses dan manajemen memori. Itu memungkinan kita menggunakan bahasa C/C++ dalam membuat aplikasi sama halnya dengan OS Linux kebanyakan. Oleh karena itu kita harus kita harus memahami arsitektur dan proses dari kernel Linux yang digunakan dalam Android tersebut. Para pengembang tidak perlu khawatir bila ia tidak memiliki device Android, karena Android memiliki virtual machine untuk eksekusi aplikasi. DVM mengeksekusi


executeable file, artinya sebuah format yang dioptimalkan untuk memastikan memori yang digunakan sangatlah kecil. Mengapa bisa seperti itu? Karena executeable file mengubah kelas bahasa Java dan dikompilasi dengan menggunakan tools yang sudah ada.

2.5.4 Android SDK (Software Development Kit)

Android SDK merupakan sebuah tools yang diperlukan untuk mengembangkan aplikasi berbasis Android menggunakan bahasa pemrograman Java [13]. Pada saat ini Android SDK telah menjadi alat bantu dan API (Application Programming Interface) untuk mengembangkan aplikasi bebasis Android. Android SDK dapat Anda lihat dan unduh pada situs resminya, yaitu http://www.developer.android.com/. Android SDK bersifat gratis dan bebas Anda distribusikan karena Android bersifat open source.

2.5.5 Versi Android

2.5.5.1 Android versi awal (2007 – 2008)

Pada September 2007, Google mengajukan hak paten aplikasi telepon seluler. Google mengenalkan Nexus One, salah satu jenis telepon pintar GSM yang menggunakan Android pada sistem operasinya. Telepon seluler ini diproduksi oleh HTC Corporation dan tersedia di pasaran pada 5 Januari 2010. Pada 9 Desember 2008, diumumkan anggota baru yang bergabung dalam program kerja Android ARM Holdings, Atheros Communications, diproduksi oleh Asustek Computer Inc, Garmin Ltd, Softbank, Sony Ericsson, Toshiba Corp, dan Vodafone Group Plc. Seiring pembentukan Open Handset Alliance, OHA mengumumkan produk perdana mereka, Android, perangkat bergerak (mobile) yang merupakan modifikasi kernel Linux 2.6. Sejak Android dirilis telah dilakukan berbagai pembaruan berupa perbaikan bug dan penambahan fitur baru. Smartphone yang memakai sistem operasi Android adalah HTC Dream, yang dirilis


pada 22 Oktober 2008. Pada penghujung tahun 2009 diperkirakan di dunia ini paling sedikit terdapat 18 jenis telepon seluler yang menggunakan Android.

2.5.5.2 Android versi 1.1

Pada 9 Maret 2009, Google merilis Android versi 1.1. Android versi ini dilengkapi dengan pembaruan estetis pada aplikasi, jam alarm, voice search (pencarian suara), pengiriman pesan dengan Gmail, dan pemberitahuan email.

2.5.5.3 Android versi 1.5 ( Cupcake )

Pada pertengahan Mei 2009, Google kembali merilis telepon seluler dengan menggunakan Android dan SDK (Software Development Kit) dengan versi 1.5 (Cupcake). Terdapat beberapa pembaruan termasuk juga penambahan beberapa fitur dalam seluler versi ini yakni kemampuan merekam dan menonton video dengan modus kamera, mengunggah video ke Youtube dan gambar ke Picasa langsung dari telepon, dukungan Bluetooth A2DP, kemampuan terhubung secara otomatis ke headset Bluetooth, animasi layar, dan keyboard pada layar yang dapat disesuaikan dengan sistem.

2.5.5.4 Android versi 1.6 ( Donut )

Donut (versi 1.6) dirilis pada September 2009 dengan menampilkan proses pencarian yang lebih baik dibanding sebelumnya, penggunaan baterai indikator dan kontrol applet VPN. Fitur lainnya adalah galeri yang memungkinkan pengguna untuk memilih foto yang akan dihapus; kamera, camcorder dan galeri yang dintegrasikan; CDMA/EVDO, 802.1x, VPN, Gestures, dan Text-to-speech engine; kemampuan dial kontak; teknologi text to change speech (tidak tersedia pada semua ponsel; pengadaan resolusi VWGA.


2.5.5.5 Android versi 2.0 / 2.1 ( Éclair )

Pada 3 Desember 2009 kembali diluncurkan ponsel Android dengan versi 2.0/2.1 (Eclair). Perubahan yang dilakukan adalah pengoptimalan hardware, peningkatan Google Maps 3.1.2, perubahan UI dengan browser baru dan dukungan HTML5, daftar kontak yang baru, dukungan flash untuk kamera 3,2 MP, digital Zoom, dan Bluetooth 2.1. Untuk bergerak cepat dalam persaingan perangkat generasi berikut, Google melakukan investasi dengan mengadakan kompetisi aplikasi mobile terbaik (killer apps - aplikasi unggulan). Kompetisi ini berhadiah $25,000 bagi setiap pengembang aplikasi terpilih. Kompetisi diadakan selama dua tahap yang tiap tahapnya dipilih 50 aplikasi terbaik. Dengan semakin berkembangnya dan semakin bertambahnya jumlah handset Android, semakin banyak pihak ketiga yang berminat untuk menyalurkan aplikasi mereka kepada sistem operasi Android. Aplikasi terkenal yang diubah ke dalam sistem operasi Android adalah Shazam, Backgrounds, dan WeatherBug. Sistem operasi Android dalam situs Internet juga dianggap penting untuk menciptakan aplikasi Android asli, contohnya oleh MySpace dan Facebook.

2.5.5.6 Android versi 2.2 (Froyo : Frozen Yoghurt)

Pada 20 Mei 2010, Android versi 2.2 (Froyo) diluncurkan. Perubahan-perubahan umumnya terhadap versi-versi sebelumnya antara lain dukungan Adobe Flash 10.1, kecepatan kinerja dan aplikasi 2 sampai 5 kali lebih cepat, intergrasi V8 JavaScript engine yang dipakai Google Chrome yang mempercepat kemampuan rendering pada browser, pemasangan aplikasi dalam SD Card, kemampuan WiFi Hotspot portabel, dan kemampuan auto update dalam aplikasi Android Market.

2.5.5.7 Android versi 2.3 ( Gingerbread )

Pada 6 Desember 2010, Android versi 2.3 (Gingerbread) diluncurkan. Perubahanperubahan umum yang didapat dari Android versi ini antara lain peningkatan


kemampuan permainan (gaming), peningkatan fungsi copy paste, layar antar muka (User Interface) didesain ulang, dukungan format video VP8 dan WebM, efek audio baru (reverb, equalization,headphone virtualization, dan bass boost), dukungan kemampuan Near Field Communication (NFC), dan dukungan jumlah kamera yang lebih dari satu.

2.5.5.8 Android versi 3.0/3.1 ( Honeycomb )

Android Honeycomb dirancang khusus untuk tablet. Android versi ini mendukung ukuran layar yang lebih besar. User Interface pada Honeycomb juga berbeda karena sudah didesain untuk tablet. Honeycomb juga mendukung multi prosesor dan juga akselerasi perangkat keras (hardware) untuk grafis. Tablet pertama yang dibuat dengan menjalankan Honeycomb adalah Motorola Xoom.

2.5.5.9 Android versi 4.0 (Ice Cream Sandwich)

Android versi 4.0 akan dirilis akhir tahun 2011. Setelah kita ketahui versi Android ini perlu diketahui bahwa nama lain dari versi-versi tersebut diambil oleh Google dari nama makanan penutup.

2.5.6 Komponen Aplikasi Android

Ada 4 macam komponen aplikasi yang merupakan titik masuk di mana aplikasi Android bisa berjalan. Keempat komponen tersebut memiliki fungsi dan daur hidup yang berbeda yang menentukan bagaimana masing-masing komponen dibuat dan dihancurkan. Keempat tipe komponen aplikasi tersebut adalah: 1. Activities 2. Services 3. Content providers 4. Broadcast receivers


2.6 Eclipse

Dalam pengembangan aplikasi Android biasanya para pengembang (developer Android) menggunakan Eclipse sebagai Integrated Development Environment (IDE) [12]. IDE merupakan program komputer yang memiliki beberapa fasilitas yang diperlukan dalam pembangunan perangkat lunak. Eclipse tersedia secara bebas untuk merancang dan mengembangkan aplikasi Android. Eclipse merupakan IDE terpopuler di kalangan developer Android, karena Eclipse memiliki Android plug-in lengkap yang tersedia untuk mengembangkan aplikasi Android. Selain itu, Eclipse juga mendapat dukungan langsung dari Google untuk menjadi IDE pengembangan Android, membuat project Android di mana source software langsung dari situs resminya Google. Selain Eclipse, dapat pula menggunakan IDE Netbeans untuk pengembangan aplikasi Android. Sampai saat ini Eclipse memiliki 5 versi package, yaitu: Indigo Package, Helios Package, Galileo Package, Ganymade Package dan Europa Package. Dari total download pada situs resmi Eclipse yaitu http://www.eclipse.org/ sebanyak 988,945 pengunduh Eclipse Classic Indigo pertanggal 20 Agustus 2011. Aplikasi Android dapat dikembangkan pada sistem operasi, diantaranya: •

Windows XP, Vista dan 7

•

Mac OS X atau lebih baru

•

Linux

2.7 Waterfall Model

Waterfall Model adalah model yang muncul pertama kali yaitu sekitar tahun 1970 [10]. Waterfall Model merupakan model yang paling banyak digunakan dalam pembuatan program. Model ini disebut waterfall karena tahap demi tahap yang dilalui harus menunggu selesainya tahap sebelumnya dan berjalan berurutan. Terdapat beberapa tahapan pada model Waterfall. Berikut adalah penjelasan dari tahap-tahap yang di lakukan di dalam model ini: a) Communication


Pemodelan ini diawali dengan komunikasi dengan konsumen untuk mencari kebutuhan dari keseluruhan sistem yang akan diaplikasikan ke dalam bentuk software. Hal ini sangat penting, mengingat software harus dapat berinteraksi dengan elemen-elemen yang lain seperti hardware, database, dsb. b) Planning Setelah proses communication, kita menetapkan rencana untuk pengerjaan software yang meliputi tugas-tugas teknis yang akan dilakukan, resiko yang mungkin terjadi, sumber-sumber yang dibutuhkan, hasil yang akan dibuat, dan jadwal pengerjaan. c) Modeling Pada proses modeling ini akan menerjemahkan syarat kebutuhan ke sebuah perancangan software yang dapat diperkirakan sebelum dibuat coding. Proses ini berfokus pada rancangan struktur data, arsitektur software, representasi interface, dan detail (algoritma) prosedural. Tahapan ini akan menghasilkan dokumen yang disebut software requirement. d) Construction Construction merupakan proses membuat kode. Coding atau pengkodean merupakan penerjemahan desain dalam bahasa yang bisa dikenali oleh komputer. Programmer akan menerjemahkan transaksi yang diminta oleh user. Tahapan inilah yang merupakan tahapan secara nyata dalam mengerjakan suatu software, artinya penggunaan komputer akan dimaksimalkan dalam tahapan ini. Setelah pengkodean selesai maka akan dilakukan testing terhadap sistem yang telah dibuat. Tujuan testing adalah menemukan kesalahan-kesalahan terhadap sistem tersebut untuk kemudian bisa diperbaiki. e) Deployment Tahapan ini bisa dikatakan final dalam pembuatan sebuah software atau sistem. Setelah melakukan analisis, desain dan pengkodean maka sistem yang sudah jadi akan digunakan user. Kemudian software yang telah dibuat harus dilakukan pemeliharaan secara berkala.


Sumber : Pressman, Roger S.[10] Model ini menjadi terkenal karena pengaplikasian yang mudah, dan ketika semua kebutuhan sistem dapat didefinisikan secara utuh, eksplisit, dan benar di awal proyek, maka pembuatan program dapat berjalan dengan baik dan tanpa masalah. Akan tetapi karena model ini melakukan pendekatan secara terurut maka ketika ada suatu tahap yang terhambat maka tahap berikutnya akan ikut terhambat juga.

2.8 Penelitian Terdahulu

Penelitian terdahulu merupakan penelitian yang telah dilakukan oleh pengarang sebelumnya sebagai sumber tinjauan pustaka guna menguatkan penulisan tinjauan pustaka dari sumber yang terpercaya. Berikut ini adalah beberapa penelitian yang telah dilakukan sebelumnya: 1. Penelitian yang dilakukan oleh Agus Leksono dengan judul Algoritma Ant Colony Optimization (ACO) Untuk Menyelesaikan Travelling Salesman Problem (TSP). Dalam penelitian ini, peneliti menjelaskan dan membandingkan 4 jenis Algoritma Ant Colony Optimization (ACO) dalam menyelesaikan masalah Travelling Salesman Problem (TSP). 4 jenis Algoritma Ant Colony Optimization (ACO) yang dibandingkan adalah Algoritma Ant System, Elitist Ant System, Rank Based Ant System, Max-Min Ant System, dan Ant Colony System. Dari hasil perbandingan, maka diketahui bahwa Ant Colony System memiliki hasil yang paling optimal [7]. 2. Penelitian yang dilakukan oleh Satria Prasamya dengan judul Penentuan Jalur Terpendek Menggunakan Teknologi Google Maps Mashups Dengan Mobile System


Android. Dalam penelitian ini, peneliti membangun sebuah aplikasi untuk menentukan rute terpendek pada Platform Android dengan menggunakan Google Maps dan Algoritma Ant Colony Optimization. Aplikasi ini mengharuskan user untuk memasukkan lokasi user serta lokasi yang ingin dituju oleh user sendiri. Aplikasi ini memiliki dua fitur, yaitu fitur one way trip dan fitur round trip. Fitur one way trip akan mencari rute terpendek dimana lokasi yang pertama diinputkan adalah lokasi awal dan lokasi terakhir menjadi lokasi tujuan sedangkan fitur round trip akan mencari rute terpendek yang dapat ditempuh untuk kembali ke lokasi awal [9]. 3. Penelitian yang dilakukan oleh Eko Verdianto dengan judul Perancangan Sistem Penentuan Rute Terpendek Jalur Evakuasi Tsunami dengan Algoritma Ant Colony (Studi Kasus : Belawan). Dalam penelitian ini, peneliti membangun sebuah aplikasi berbasis desktop untuk mencari rute terpendek dengan bantuan Arcview GIS. Algoritma yang digunakan adalah Algoritma Ant Colony System. Aplikasi ini berguna untuk mencari rute terpendek jalur evakuasi apabila terjadi tsunami di Belawan [11].


BAB 2 LANDASAN TEORI

Recommend Documents