MAKALAH IMPLEMENTASI ALGORITMA DALAM PEMOGRAMAN

MAKALAH IMPLEMENTASI ALGORITMA DALAM PEMOGRAMAN

“IMPLEMENTASI ALGORITMA GREEDY UNTUK PENYELESAIAN BEBERAPA MASALAH”

Disusun Oleh :

Annisa Fajrita Yuandari (21070114120059)

Muhammad Fakhri Gusti (21070114130121)

Nadiya Pramudian Kurniawati (21070114120021)

Surya Nugrahadi (21070114130071)

PROGRAM STUDI TEKNIK INDUSTRI

FAKULTAS TEKNIK UNIVERSITAS DIPONEGORO

SEMARANG

2014

KATA PENGANTAR

Alhamdulillah, puji syukur kami sampaikan atas kehadirat ALLAH SWT. Sehingga atas rahmat dan karunia-Nya kami dapat menyelesaikan makalah tugas pendahuluan pratikum Teknologi Informatika.

Dalam makalah yang berjudul Implementasi Algoritma dalam Pemrograman ini, kami akan membahas mengenai pengertian algoritma, pengertian algoritma greedy serta beberapa implementasi dari algoritma greedy.

Kami menyadari bahwa dalam penyusunan makalah ini masih banyak terdapat kekurangan. Oleh karena itu atas segala dukungan dan bimbingan dari berbagai pihak yang sifatnya membangun, pada kesempatan ini kami ingin ucapkan terimakasih.

Besar harapan kami semoga tugas ini dapat memberi manfaat bagi kami sendiri serta para pembaca.

Semarang, 8 November 2014

Kelompok 39

DAFTAR ISI

KATA PENGANTAR...........................................................................................    2

DAFTAR ISI.........................................................................................................     3

BAB I PENDAHULUAN.....................................................................................    4

1.1.   Latar Belakang Masalah...........................................................................  4

1.2.   Rumusan Masalah....................................................................................   4

1.3.   Tujuan.......................................................................................................     4

BAB II ISI.............................................................................................................    5

2.1.   Pengertian Algoritma................................................................................  5

2.2.   Pengertian Algoritma Greedy...................................................................     5

2.3.   Implementasi Algoritma Greedy pada Taksi Wisata Berbasis Web........   5

2.4.   Implementasi Algoritma Greedy pada Pemesanan Tiket Konser............   6

2.5.   Implementasi Algoritma Greedy pada Pengaturan Lampu

Lalu Lintas Sederhana..............................................................................     7

 BAB III PENUTUP..............................................................................................    10       

3.1.   Kesimpulan...............................................................................................     10

DAFTAR PUSTAKA........................................................................................... 11

BAB I

PENDAHULUAN

1.1  Latar Belakang

Di zaman yang serba canggih seperti saat ini, komputer merupakan kebutuhan dasar di bidang kehidupan manusia. Komputer erat kaitannya dengan pemrograman komputer. Di dalam pemrograman komputer itulah kita akan mengenal algoritma. Algoritma diartikan sebagai langkah-langkah yang logis untuk memecahkan suatu permasalahan yang ingin diselesaikan oleh program. Untuk itu, algoritma dan pemrograman merupakan satu kesatuan yang saling mempengaruhi sehingga membentuk suatu sistem yang terintegrasi.

1.2  Rumusan Masalah

1.2.1.      Apa yang dimaksud dengan algoritma?

1.2.2.      Apa yang dimaksud dengan algoritma greedy?

1.2.3.      Bagaimana implementasi dari algoritma greedy?

1.3  Tujuan

1.3.1.      Mengidentifikasi pengertian algoritma.

1.3.2.      Mengidentifikasi pengertian algoritma greedy.

1.3.3.      Mengidentifikasi implementasi dari algoritma greedy.

BAB II

ISI

2.1 Pengertian Algoritma

Algoritma merpakan suatu urutan atau langkah-langkah yang logis untuk menyelesaikan suatu masalah. Algoritma pertama kali dikembangkan oleh ahli matematika Arab bernama Abu Ja’far Muhammad Ibnu Musa Al-Khuwarizmi melalui bukunya yang berjudul Kitab Al-Jabar Wal-Muqabala (Pemugaran dan Pengurangan). Al-Khuwarizmi kemudian dibaca oleh orang barat sebagai Algorism. Inilah yang menjadi dasar kata algorithm atau yang dalam bahasa Indonesia diserap menjadi algoritma.

2.2 Pengertian Algoritma Greedy

Algoritma greedy merupakan jenis algoritma yang mencari solusi menggunakan nilai maksimum untuk menyelesaikan suatu masalah dengan tujuan mempersingkat waktu walaupun terkadang hasilnya tidak optimal. Secara bahasa, greedy berarti rakus, tamak, loba, dan sebagainya. Ini menunjukan karakteristiknya sebagai suatu model penyelesaian masalah yang cepat namun terkadang hasilnya tidak optimal.

2.3 Implementasi Algoritma Greedy pada Taksi Wisata Berbasis Web

            Algoritma greedy dapat digunakan untuk membuat sistem taksi wisata berbasis web, cara yang akan digunakan yakni menawarkan informasi tempat wisata yang dapat dikunjungi dan menginformasikan biaya pada customer dimana biaya ini mencakup biaya parkir, tiket masuk, biaya makan, dan tarif taksi sesuai dengan jarak tempuh. Algoritma greedy pada layanan taksi wisata ini berfungsi untuk menginformasikan mengenai urutan-urutan tempat wisata yang akan dikunjungi. Dengan mengimplementasikan algoritma greedy pengguna dapat mendapatkan informasi yang optimal mengenai jarak tempuh dan biaya yang dikeluarkan. Algoritma greedy bagus digunakan jika tempat yang dikunjungi kurang dari sepuluh, karena algoritma greedy memiliki hasil optimasi yang lebih bagus dan hasil komputasi yang lebih cepat dengan cakupan data yang relatif kecil. Waktu dan biaya yang harus diperhitungkan apabila seseorang akan melakukan perjalanan taksi wisata, dalam menentukannya menggunakan algoritma greedy. Fungsinya untuk mengoptimalkan kunjungan wisata dengan mencari jalur terpendek antara setiap node dan menempatkannya pada solusi yang disediakan. Konsep dari algoritma greedy melalui penentuan jalur terdekat diantara tempat yang telah dikunjungi dan tempat yang akan dikunjungi. Jadi, dari penjelasan diatas algoritma greedy dapat mengoptimalkan apa yang kurang efektif menjadi efektif.

Untuk implementasi algoritma greedy itu sendiri, yang pertama ditekankan kepada sistem, tahapan awalnya membuat web interface. Disini diperlukan database, gunanya untuk menangani interaksi dari berbagai informasi yang ada di web, seperti tujuan wisatanya. Kemudian diterapkan algoritma greedy yang fungsinya mengoptimalkan tujuan yang telah dipilih sebelumnya. Lalu, kita membuat sms gateaway yang berperan sebagai sistem pemberitauan dan komunikasi bagi para server dengan supir taksi yang sedang tidak bertugas.  Yang kedua ditekankan kepada pengujian yang gunanya mengetahui kualitas dari sistem yang dibuat. Setelah membuat sms gateaway perlu dilalukan beberapa pengujian seperti, pengujian sms gateaway, pengujian perbandingan metode saving dan pengujian waktu komputasi. Pengujian-pengujian ini perlu dilakukan untuk mengetahui performa dari sistem yang telah dibuat. Kesimpulannya, metode algoritma greedy dapat diimplementasikan pada kasus travelling salesmen problem, karena dibandingkan dengan algoritma lain waktu komputasi yang dibutuhkan algoritma greedy dalam memecahkan masalah ini lebih cepat.

2.4 Implementasi Algoritma Greedy pada Pemesanan Tiket Konser

            Algoritma greedy juga dapat digunakan untuk memecahkan masalah reservasi tiket konser dengan sistem tempat duduk yang diberi nomer. Jadi pada saat diselenggarakannya konser, penonton sudah mengerti dimana nomer tempat duduk saat nanti konser berlangsung.

Penonton tentunya akan memilih posisi tempat duduk yang paling nyaman dan berdekatan dengan teman-temannya yang menonton konser bersama. Kendalanya, dari banyaknya sisa pilihan kursi, para penonton tidak memilihnya karena masalah tempat duduk yang tidak berdekatan dan sisa kursi tersebut berada di tempat yang tidak meng-enakan, yang terkadang tertinggal satu di tengah.

            Maka digunakanlah algorithma greedy untuk menyelesaikan permasalahan diatas. Pembeli yang memesan lebih cepat akan mendapat tempat duduk yang lebih enak dan penjual tiketpun dapat cepat mengatur tempat duduk konser karena pembeli tiket telah memasrahkan pemilihan tempat duduk pada si penjual. Reservasi tiket pun harus mempertimbangakan keinginan penonton seperti, posisi tempat duduk yang enak, kursi untuk beberapa orang, keadilan penempatan, dan keadilan penjualan. Dengan tidak menghilangkan keinginan penyelenggara tentang tujuan umum penjualan tiket seperti, tujuan merangkul publik dan tujuan komersil dengan penjualan tiket perkelas seperti VIP, VVIP, atau reguler. Terdapat aturan yang mempengaruhi pemosisian yang digunakan dalam implementasi seperti penomoran kursi, jumlah tiket yang dapat dibeli perorang,  dan perubahan tempat duduk.

Implementasi algorithma greedy disini ada dua, pertama adanya kuasa penuh penjual tiket untuk memilihkan tempat duduk  yang diusahakan berdekatan sesuai tiket yang dibeli tanpa menyisakan kursi tepencil, atau pembeli memilih sendiri tempat duduknya namun diusahakan membeli nomor tempat duduk yang berdekatan tanpa menyisakan kursi terpencil.

Elemen-elemen yang terdapat di algorithma greedy untuk memecahkannya terdapat: 1. Himpunan kandidat C yang tidak semua kursi dapat dibeli, 2. Himpunan solusi yang reservasi hanya dapat dilakukan jika memesan dengan posisi berdekatan minimal 2 kursi berderet tanpa menyisakan kursi terpencil,  3. Fungsi seleksi dengan menggunakan list kombinasi kursi sederet duaderet tanpa menyisakan kursi terpencil, 4. Fungsi kelayakan yang dapat  disaring kembali kursi yang belum dipesan untuk dijual kepada pembeli selanjutnya, 5. Fungsi obyektif yaitu fungsi bebas.

2.5 Implementasi Algoritma Greedy pada  Pengaturan Lampu Lalu Lintas Sederhana

Seiring dengan jumlah kendaraan yang terus meningkat di seluruh dunia terutama di kota-kota besar, sistem pengaturan lalu lintas yang baik sangatlah diperlukan agar aliran kendaraan di jalan-jalan bisa tetap lancar dan jumlah kemacetan dapet diminimalisir. Lampu lalu lintas berperan sangat penting dalam mengatur persimpangan jalan, lampu lalu lintas berperan mengatur arah dan aliran kendaraan pada persimpangan jalan. Persimpangan jalan sering menjadi titik kemacetan, dengan sistem pengaturan lampu lalu lintas yang baik maka kemacetan akan berkurang dan secara keseluruhan kelancaran jalan akan meningkat, salah satu cara untuk meningkatkan kinerja sistem pengaturan lampu lalu lintas adalah dengan mengoptimalkan waktu siklus lampu merah-kuning-hijau. Namun pengoperasian lampu lalu lintas masih memiliki masalah pada pembagian waktu siklus waktu lampu lalu lintas, saat ini kebanyakan masih diatur secara konstan dan manual.  Contoh dari masalah ini seperti lampu lalu lintas yang tidak menyesuaikan lamanya delay dengan kepadetan kendaraan terus berubah sepanjang hari, walaupun arus lalu lintas pada suatu jalan sedang sepi, lamanya delay waktu siklus lampu lalu lintas tidak berbeda pada saat jalan tersebut sedang ramai. Seharusnya pada jalur jalan yang kepadatan arus kendaraannya tinggi, lampu warna hijau harusnya memiliki delay yang lebih lama di bandingkan dengan jalur yang memiliki kepadatan kendaraan yang rendah. Hal ini sangan bermanfaat karena memberikan kesempatan yang lebih banyak kepada kendaraan-kendaraan yang melewati lampu lalu lintas pada jalur yang lebih padat. Sistem pengaturan siklus waktu lampu lalu lintas yang dapat mengatur waktus siklusnya secara otomatis akan menjadi suatu hal yang sangat penting di masa yang mendatang. Hal ini kegunaannya akan sangat terasa pada saat kepadatan pada lalu lintas pada persimpangan terjadi, dengan menerapkan sistem ini waktu siklus lampu lalu lintas merah-kuning-hijau akan menjadi efektif dan efisien. Untuk memecahkan masalah optimalisasi lampu lalu lintas dapat menggunakan sistem algoritma greedy. Untuk memecahkan persoalan menggunakan algoritma greedy diperlukan elemen-elemen sebagai berikut: himpunan kandidat C (himpunan  berisi elemen pembentuk solusi), himpunan solusi S(berisi kandidat yang terpilih sebagai solusi persoalan, fungsi seleksi( fungsi yang memilih kandidat yang paling memungkinkan mencapai solusi optimal), fungi kelayakan( pemeriksaan ke efektifan dari suatu kandidat yang di pilih), dan fungsi objektif( memaksimumkan atau meminimumkan nilai funsi). Urutan langkah-langkah algoritma greedy untuk menyelesaikan permasalahan ini yang sesuai dengan skema umum algoritma greedy dapat di jelaskan sebagai berikut:

1.      Buat himpunan kandidat S yang memungkinkan untuk menjadi solusi dari masalah ini

2.      Inisialisasi himpunan solusi  menjadi himpunan kosong

3.      Ambil salah satu solusi untuk di uji oleh fungsi objektif

4.      Hasil dari fungsi objektif adalah selisih rata-rata(SR)

5.      Lakukan fungsi kelayakan dan fungsi seleksi terhadap solusi sementara

6.      Ulangi proses 3,4,5 dan 6 sampai semua kandidat sudah di proses

7.      Nilai yang terdapat pada himpunan solusi adalah solusi optimal dari masalah ini

Dengan menggunakan suatu sistem optimalisasi yang implementasinya menggunakan algoritma greedy, maka akan ditemukan solusi delay lampu lalu lintas yang efektif untuk setiap lampu lalu lintas pada persimpangan.

BAB III

PENUTUP

3.1 Kesimpulan

Salah satu pembagian dari algoritma ialah algoritma greedy. Algoritma greedy ini bisa diimplementasikan pada Taksi Wisata Berbasis Web, Pemesanan Tiket Konser dan Pengaturan Lampu Lalu Lintas Sederhana.

Pada taksi wisata berbasis web, metode yang digunakan adalah mencari solusi optimum dari yang kurang efektif menjadi efektif. Karena pada metode ini waktu yang diperlukan relatif singkat.

Pada pemesanan tiket konser, algoritma greedy  digunakan untuk pemecahan masalah yang butuh optimasi dalam reservasi tiket konser dengan menggunakan penomoran kursi yang tujuannya untuk mengurangi penempatan yang tidak memuaskan bagi penonton. Algorithma greedy ini juga dapat mengurangi hal yang tidak diinginkan, seperti adanya kursi terpencil dengan  mempertimbangkan keinginan pembeli yang tidak bisa dipaksakan.

Pada pengaturan lampu lalu lintas sederhana, penggunaan algoritma greedy mampu menemukan solusi delay lampu lalu lintas yang optimal. Sehingga para pengguna jalan raya dan pengguna lampu lalu lintas mendapat waktu tunggu yang seimbang.

DAFTAR PUSTAKA

https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&cad=rja&uact=8&ved=0CBsQFjAA&url=http%3A%2F%2Frepo.eepis-its.edu%2F503%2F1%2F1292.pdf&ei=n8deVJftHpSpuQTqwIC4CQ&usg=AFQjCNGXwrrgTRtXnd6ceC8hkYagBnzniw&sig2=-rwvJZSfoRXKtOhkIdlcPA&bvm=bv.79189006,d.c2E

https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&cad=rja&uact=8&ved=0CBsQFjAA&url=http%3A%2F%2Finformatika.stei.itb.ac.id%2F~rinaldi.munir%2FStmik%2F2011-2012%2FMakalah2011%2FMakalahIF3051-2011-001.pdf&ei=X8ZeVIenL8meugTtv4GIDQ&usg=AFQjCNGEcBZq4VeuTvI4D1w_W6Z1cgre3g&sig2=Vhb9D8A6x_xBHkxme-i_0Q&bvm=bv.79189006,d.c2E

https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&cad=rja&uact=8&ved=0CBsQFjAA&url=http%3A%2F%2Finformatika.stei.itb.ac.id%2F~rinaldi.munir%2FStmik%2F2005-2006%2FMakalah2006%2FMakalahStmik2006-48.pdf&ei=6sdeVKStKZafugTTm4KoAw&usg=AFQjCNFib2GaG5Cy0NzeTWTMQBlb8c5m2A&sig2=TVW5LwCeVnnXOgJ5jMUjoA&bvm=bv.79189006,d.c2E