ANALISIS PERBANDINGAN ALGORITMA GREEDY & BRUTE FORCE DALAM PENCARIAN KARTU TERTINGGI PADA KARTU REMI
SKRIPSI
ANTON GUMALA PUTRA 091401018
PROGRAM STUDI S1 ILMU KOMPUTER FAKULTAS ILMU KOMPUTER DAN TEKNOLOGI INFORMASI UNIVERSITAS SUMATERA UTARA MEDAN 2014
Universitas Sumatera Utara
ANALISIS PERBANDINGAN ALGORITMA GREEDY & BRUTE FORCE DALAM PENCARIAN KARTU TERTINGGI PADA KARTU REMI
SKRIPSI Diajukan untuk melengkapai tugas akhir dan memenuhi syarat mencapai gelar Sarjana Komputer
ANTON GUMALA PUTRA 091401018
PROGRAM STUDI S1 ILMU KOMPUTER FAKULTAS ILMU KOMPUTER DAN TEKNOLOGI INFORMASI UNIVERSITAS SUMATERA UTARA MEDAN 2014
Universitas Sumatera Utara
PERNYATAAN
ANALISIS PERBANDINGAN ALGORITMA GREEDY DAN BRUTE FORCE DALAM PENCARIAN KARTU TERTINGGI PADA KARTU REMI
SKRIPSI
Saya mengakui bahwa skripsi ini adalah hasil karya saya sendiri, kecuali beberapa kutipan dan ringkasan yang masing-masing disebutkan sumbernya.
Medan, Februari 2014
Anton Gumala Putra 091401018
Universitas Sumatera Utara
PENGHARGAAN
Alhamdulillahirrabbil’alamin, penulis ucapkan rasa syukur yang tiada hentinya kehadirat Allah Subhanahuwata’ala yang telah memberikan rahmat dan karunia-Nya sehingga penulis dapat menyelesaikan skripsi ini. Shalawat beriring salam juga tak lupa teruntuk baginda Nabi Muhammad SAW beserta keluarganya, para sahabat, syuhada dan pengikutnya yang setia. Dengan segala kerendahan hati, pada kesempatan ini penulis menyampaikan terima kasih kepada semua pihak yang telah membantu penyelesaian skripsi ini. Penulis mengucapkan terima kasih kepada : 1. Bapak Prof. Dr. Syahril Pasaribu, DTMH, MSc(CTM), SpA(K) sebagai Rektor Universitas Sumatera Utara (USU) 2. Bapak Dr. Muhammad Zarlis sebagai Dekan Fakultas Ilmu Komputer dan Teknologi Informasi Universitas Sumatera Utara 3. Bapak Dr. Poltak Sihombing, M.Kom sebagai Ketua Program Studi S1 Ilmu Komputer dan sekaligus sebagai Dosen Pembimbing I. 4. Ibu Dian Rachmawati, S.Si, M.Kom sebagai Dosen Pembimbing II dan sekaligus sebagai Dosen di Program Studi S1 Ilmu Komputer Fasilkom-TI USU. 5. Bapak Drs. Marihat Situmorang, M.Kom sebagai Dosen Pembanding I dan sekaligus sebagai Dosen di Program Studi S1 Ilmu Komputer Fasilkom-TI USU. 6. Bapak M. Andri Budiman, ST,M.Comp.Sc,MEM sebagai Pembanding II dan sekaligus sebagai Dosen di Program Studi S1 Ilmu Komputer Fasilkom-TI USU.
Universitas Sumatera Utara
7. Seluruh Dosen serta staf Pegawai di Program Studi S1 Ilmu Komputer Fasilkom-TI USU. 8. Kedua Orang tua penulis tercinta Ibunda Dra. Gusniar dan Ayahanda Zakaria, adik-adik di rumah Dwiky.S. Permana dan M. Reksy Setiawan. Semoga bisa menjadi orang-orang yang sukses. 9. Abangda Arie Yudha Nugraha yang masih terus membimbing penulis dan teman-teman untuk belajar. 10. Para sohibul Basrah Nasution, S.Kom, Mhd.Arisandy .P, Zuwarbi .W dan Budi .S yang selalu memberikan semangat dan dorongan yang kuat sehingga penulis selesai mengerjakan Skripsi ini. 11. Kepada Akhi/Ukhti di UKMI Al-Khuwarizmi Fasilkom-TI USU, Fadhil Akbar, Azizah, Yayang.K, Ikhsan Okto, Tito.H, Retry, Aisyah, Nurul, Lestari, Zulfikri, Akhiruddin dan semuanya yang telah memberikan banyak pelajaran dan ukhuwah yang kuat.. 12. Kepada teman-teman ikatan daerah Imapaliko, Zuhdi mahendra, S.T, Medi,S.Hut, Bayu S Pratama, Annisa Ikhsan, SE, Reviana Revitasari, Suci Intan. F, S.Ked, Bg David Satria, S.T, Kak Millaty.F, S.Ked dan adik-adik semuanya yang tidak dapat disebutkan satu-persatu. 13. Kepada teman-teman seperjuangan stambuk 2009 serta abang-abang dan kakak-kakak senior yang ada di Program Studi S1 Ilmu Komputer yang telah memberikan dukungan moril maupun materil kepada penulis dalam penyusunan skripsi ini. 14. Dan juga Kepada teman-teman satu kost, Bang Ono Suharsono, S.Kom, Bang Zainuddin Siregar, Bang Muhammad Syukur, ST, Bang Irfan Antoni Siregar, S.Kom, Suyono dan Hendriadi, yang selalu memberikan dukungan penuh kepada penulis. Sekali lagi penulis mengucapkan terima kasih kepada semua pihak yang membantu dalam penyelesaian skripsi ini yang tidak dapat disebutkan satu persatu, terima kasih atas ide, saran dan motivasi yang diberikan. Semoga Allah Subhanahuwata’ala memberikan limpahan karunia kepada semua pihak yang telah
Universitas Sumatera Utara
memberikan bantuan, perhatian, kasih sayang serta dukungan kepada penulis dalam menyelesaikan skripsi ini. Penulis menyadari bahwa skripsi ini masih jauh dari kesempurnaan karena kesempurnaan hanyalah milik Allah Subhanahuwata’ala semata. Oleh karena itu penulis menerima kritik dan saran dari semua pihak yang bersifat membangun dan menyempurnakan skripsi ini. Penulis berharap semoga skripsi ini bermanfaat bagi penulis sendiri pada khususnya dan pembaca pada umumnya.
Medan, Februari 2014
Penulis, Anton Gumala Putra
Universitas Sumatera Utara
ABSTRAK
Kartu bridge merupakan objek yang bisa dijadikan sampel untuk membandingkan kinerja sebuah algoritma. Berdasarkan aturan permainan poker kartu ini memiliki tingkatan berdasarkan nilai dan corak. Nilai kartu tertinggi dimulai dari As, K, Q,…2. Sedangkan pada corak dimulai dari sekop, hati, keriting dan wajik. Dalam analisis algoritma, sebuah algoritma akan semakin mangkus jika optimal dan cepat. Sebanyak 52 kartu dengan urutan berbeda yaitu ascending, descending dan random dilakukan pengujian dalam pencarian kartu tertinggi dengan algoritma berbeda. Hasil pencarian kartu tertinggi ini sudah pasti sama. Tapi metode pencarian berbeda. Pencarian menggunakan algoritma Greedy dan Brute Force. Pada Greedy pencarian dilakukan dengan mengambil nilai terbesar sampai terkecil secara selection sort. Sedangkan Brute Force dengan cara langsung mencapai tujuan yaitu kartu tertinggi tanpa mempertimbangkan apapun. Dengan menggunakan kedua algoritma ini akan diketahui perbandingan kecepatan dalam mencari kartu tertinggi. Kata Kunci : Greedy, Brute Force, Selection Sort, Big Theta.
Universitas Sumatera Utara
ABSTRACT
Bridge card is an object that can be used as a sample to compare the performance of the algorithm. Under the rules of the card game of poker has tiers based on value and style. The highest card value starting from As, K, Q,…2. While the highest value on the pattern starts from shovels, liver, curly and diamonds. In the analysis of algorithms, an algorithm will be more efeective if optimal and fast. A total of 52 cards with different sequences are ascending, descending and random testing in the search for the highest card with different algorithms. The highest card of the search results will definitely produce the same card. But in a somewhat different search method. The highest card search using the Greedy algorithm and Brute Force. Application of Greedy algorithms are implemented on the highest card is the quest to take the biggest to the smallest value in selection sort. While Brute Force with a direct way achieve the goal of highest card without any consideration. By using this algorithm will be known to both the speed comparison in searching for the highest card .. Keywords : Greedy, Brute Force, Selection Sort, Big Theta.
Universitas Sumatera Utara
DAFTAR ISI
Halaman Persetujuan Pernyataan Penghargaan Abstrak Abstract Daftar Isi Daftar Tabel Daftar Gambar Bab 1
Bab 2
Pendahuluan 1.1 Latar Belakang 1.2 Rumusan Masalah 1.3 Batasan Masalah 1.4 Tujuan Penelitian 1.5 Manfaat Penelitian 1.6 Metode Penelitian 1.7 Sistematika Penulisan
ii iii iv vi vii viii x xi 1 2 2 2 2 3 4
Tinjauan Pustaka 2.1 Konsep Dasar Algoritma 2.2 Defenisis dan Analisis Algoritma 2.3 Kompleksitas Waktu Algoritma Dan Masalah 2.3.1 Big-O(O) 2.3.2 Big Omega (Ω) 2.3.3 Big Theta (ɵ) 2.4 Algoritma Greedy 2.5 Algoritma Brute Force
5 6 7 8 9 9 10 11
Bab 3 Analisis Dan Perancangan Sistem 3.1 Analisis Sistem 3.1.1 Analisis Masalah 3.1.2 Analisis Kebutuhan Sistem 3.1.2.1 Kebutuhan Fungsional Sistem 3.1.2.2 Kebutuhan Non-Fungsional Sistem
14 14 15 15 16
3.2 Pemodelan 3.2.1 Flowchart Gambaran Umum Sistem
16 16
Universitas Sumatera Utara
3.2.1.1 Flowchart Algoritma Greedy 3.2.1.2 Flowchart Algoritma Brute Force
Bab 4
16 18
3.2.2 Unified Modeling Language (UML) 3.2.2.1 Use Case Diagram 3.2.2.1.1 Use Case Greedy dan Brute Force 3.2.2.2 Activity Diagram
19 19 20 21
3.2.3 Pseudocode 3.2.3 Pseudocode Proses Algoritma Greedy 3.2.3 Pseudocode Proses Algoritma Brute Force
21 22 23
3.3 Proses Pencarian Kartu Tertinggi 3.3.1 Proses Pencarian Kartu Tertinggi Greedy 3.3.2 Proses Pencarian Kartu Tertinggi Brute Force
24 24 24
3.4 Perancangan Antarmuka (Interface)
25
Implementasi dan Pengujian Sistem 4.1 Implementasi Sistem 4.2 Spesifikasi Perangkat Keras 4.3 Spesifikasi Perangkat Lunak
28 28 28
4.4 Tampilan Antarmuka(Interface) 4.4.1 Tampilan Pemilihan Urutan Kartu 4.4.2 Tampilan Inputan Kartu 4.4.2.1 Ascending 4.4.2.2 Descending 4.4.2.3 Random
28 30 30 30 31 31
4.4.3 Tampilan Pencarian Kartu Tertinggi 4.4.3.1 Tampilan Pencarian Kartu Tertinggi Greedy 4.4.3.1.1 Ascending 4.4.3.1.2 Descending 4.4.3.1.3 Random 4.4.2.2 Tampilan Pencarian Kartu Tertinggi Brute Force 4.2.1.2.1 Ascending 4.2.1.2.2 Descending 4.2.1.2.3 Random 4.3 Pengujian Sistem 4.3.1 Pengujian Pencarian Kartu Tertinggi Greedy 4.3.1.1 Ascending
31 32 32 40 42 34 34 34 35 35 36 36
Universitas Sumatera Utara
4.3.1.2 Descending 4.3.1.3 Random 4.3.1.4 Kasus Terbaik dan Terburuk
40 42 45
4.3.2 Pengujian Pencarian Kartu Tertinggi Brute Force 4.3.1.1 Ascending 4.3.1.2 Descending 4.3.1.3 Random 4.3.1.4 Kasus Terbaik dan Terburuk Bab 5
Kesimpulan Dan Saran 5.1 Kesimpulan 5.2 Saran
46 46 49 51 53 55 56
Daftar Pustaka
57
LAMPIRAN A: Listing Program
A-1
Universitas Sumatera Utara
DAFTAR TABEL
Halaman 3.1 Use Case Pencarian Kartu Tertinggi
20
4.1 Hasil Kartu Tertinggi Greedy secara Ascending
37
4.2 Waktu Pencarian Greedy Secara Ascending
38
4.3 Perhitungan Big Theta Greedy
39
4.4 Hasil Kartu Tertinggi Greedy Secara Descending
41
4.5 Waktu Pencarian Greedy Secara Descending
42
4.6 Hasil Kartu Tertinggi ke-1 Greedy Seacara Random
43
4.7 Hasil Kartu Tertinggi ke-2 Greedy Seacara Random
43
4.8 Hasil Kartu Tertinggi ke-3 Greedy Seacara Random
44
4.9 Waktu Pencarian Greedy Secara Random
44
4.10 Hasil Kartu Tertinggi Brute Force Secara Ascending
46
4.11 Waktu Pencarian Brute Force Secara Ascending
47
4.12 Perhitungan Big Theta Brute Force
47
4.13 Hasil Kartu Tertinggi Brute Force Secara Descending
49
4.14 Waktu Pencarian Brute Force Secara Descending
50
4.15 Hasil Kartu Tertinggi ke-1 Brute Force Secara Random
51
4.16 Hasil Kartu Tertinggi ke-2 Brute Force Secara Random
52
4.17 Hasil Kartu Tertinggi ke-3 Brute Force Secara Random
52
4.18 Waktu Pencarian Brute Force Secara Random
53
Universitas Sumatera Utara
DAFTAR GAMBAR
Halaman 3.1. Diagram Ishikawa untuk Analisis Masalah Sistem
15
3.2 Flowchart pencarian kartu tertinggi dengan Greedy
17
3.3 Flowchart pencarian kartu tertinggi dengan Brute Force
18
3.4 Use Case Dagram Sistem Pencarian Kartu Tertinggi
19
3.5 Activity Dagram Sistem Pencarian Kartu Tertinggi
21
3.6. Pengambilan Kartu Random Greedy
24
3.7 Pengurutan Secara Selection sort
24
3.8 Pemilihan Kartu Tertinggi
24
3.9. Pengambilan Kartu Random Brute Force
25
3.10 Proses Membandingkan Mencari Kartu Tertinggi
25
3.11 Rancangan Interface Sistem
26
4.1 Interface sistem pencarian kartu tertinggi
29
4.2 Pemilihan urutan kartu
30
4.3 Inputan ascending
30
4.4 Inputan descending
31
4.5 Inputan random
31
4.6 Pencarian kartu tertinggi ascending dengan Greedy
32
4.7 Pencarian kartu tertinggi descending dengan Greedy
32
4.8 Pencarian kartu tertinggi random dengan Greedy
33
4.9 Pencarian kartu tertinggi ascending dengan Brute Force
34
4.10 Pencarian kartu tertinggi descending dengan Brute Force
34
4.11 Pencarian kartu tertinggi random dengan Brute Force
35
4.12 Interface sistem secara umum
36
4.13 Inputan 7 kartu pertama sistem
37
4.14 Kasus Terbaik Greedy
45
Universitas Sumatera Utara
4.15 Kasus Terburuk Greedy
45
4.16 Kasus Terbaik Brute Force
53
4.17 Kasus Terburuk Brute Force
54
Universitas Sumatera Utara
