3IA18 - Kel4 - Algoritma Brute Force [PDF]

Citation preview

MAKALAH ALGORITMA BRUTE FORCE Ditulis untuk memenuhi tugas kelompok Peranc. & Analisa Algoritma



Dosen Pembimbing Dessy Tri Anggraeni



Disusun oleh : Damara Syaidil F



(51418626)



Kagin Mikail H. K



(53418575)



TEKNIK INFORMATIKA FAKULTAS TEKNOLOGI INDUSTRI UNIVERSITAS GUNADARMA 2020



DAFTAR ISI



DAFTAR ISI ....................................................................................................... i KATA PENGANTAR ........................................................................................ ii BAB I – PENDAHULUAN ................................................................................ 1 1.1



Latar Belakang....................................................................................... 1



1.2



Rumusan Masalah.................................................................................. 1



1.3



Tujuan Penulisan ................................................................................... 1



BAB II – PEMBAHASAN ................................................................................. 2 2.1



Pengertian Algoritma Brute Force .......................................................... 2



2.2



Kelebihan dan Kelemahan Algoritma Brute Force ................................. 2



2.3



Karakteristik Algoritma Brute Force ...................................................... 3



2.4



Menyelesaikan Exhaustive Search dengan Brute Force .......................... 4



2.5



Cara Kerja Algoritma Brute Force ......................................................... 6



2.6



Contoh Penerapan Algoritma Brute Force .............................................. 7



BAB III – PENUTUP ....................................................................................... 10 3.1



Kesimpulan.......................................................................................... 10



3.2



Saran ................................................................................................... 10



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



i



KATA PENGANTAR Segala puji syukur kami panjatkan kepada Tuhan Yang Maha Esa. Atas rahmat dan karunia-Nya, kami dapat menyelesaikan tugas penulisan makalah mata kuliah Peranc. & Analisa Algoritma tepat waktu. Tidak lupa shalawat serta salam tercurah kepada Rasulullah SAW yang syafa’atnya kita nantikan kelak. Penulisan makalah berjudul “Algoritma Brute Force ” dapat diselesaikan karena bantuan banyak pihak. Kami berharap makalah ini dapat menjadi referensi bagi pihak yang tertarik pada bidang pemrograman. Selain itu, kami juga berharap agar pembaca mendapatkan sudut pandang baru setelah membaca makalah ini. Penulis menyadari makalah ini masih memerlukan penyempurnaan, terutama pada bagian isi. Kami menerima segala bentuk kritik dan saran pembaca demi penyempurnaan makalah. Apabila terdapat banyak kesalahan pada makalah ini, kami memohon maaf. Demikian yang dapat kami sampaikan. Akhir kata, semoga makalah kelompok kami ini dapat bermanfaat.



Bekasi, 6 Oktober 2020



Penulis



ii



BAB I - PENDAHULUAN 1.1



Latar Belakang Dalam matematika dan komputasi, algoritma merupakan kumpulan perintah untuk menyelesaikan suatu masalah. Perintah-perintah ini dapat diterjemahkan secara bertahap dari awal hingga akhir. Masalah tersebut dapat berupa apa saja, dengan syarat untuk setiap permasalahan memiliki kriteria kondisi awal yang harus dipenuhi sebelum menjalankan sebuah algoritma. Algoritma akan selalu berakhir untuk semua kondisi awal yang memenuhi criteria, hal ini berbeda dengan heuristik. Algoritma juga memiliki pengulangan proses (iterasi), dan juga memiliki keputusan hingga keputusan selesai. Kompleksitas dari suatu algoritma merupakan ukuran seberapa banyak komputasi yang diterapkan algoritma tersebut untuk menyelesaikan permasalahannya. Secara informal, algoritma yang dapat menyelesaikan permasalahan dalam waktu yang relative singkat memiliki tingkat kompleksitas yang rendah, semetara algoritma yang menyelesaikan permasalahan dalam waktu yang lebih lama memiliki tingkat kompleksitas yang lebih tinggi pula.



1.2



Rumusan Masalah 1. Apa itu Algoritma Brute Force? 2. Apa saja kelebihan dan kelemahan Algoritma Brute Force? 3. Bagaimana karakteristik Algoritma Brute Force? 4. Bagaimana cara kerja Algoritma Brute Force? 5. Apa saja contoh penerapan Algoritma Brute Force?



1.2 Tujuan Penulisan 1. Mengetahui apa itu Algoritma Brute Force 2. Mengetahui kelebihan dan kelemahan Algoritma Brute Force 3. Mengetahui karakterisitik Algoritma Brute Force 4. Mengetahui bagaimana cara kerja Algoritma Brute Force 5. Mengetahui contoh – contoh penerapan Algoritma Brute Force



1



BAB II – PEMBAHASAN 2.1 Pengertian Algoritma Brute Force Brute Force (Rinaldi Munir, 2004, p. 2) adalah sebuah pendekatan langsung (straight forward) untuk memecahkan suatu masalah, yang biasanya didasarkan pada pernyataan masalah (problem statement) dan definisi konsep yang dilibatkan. Pada dasarnya algoritma Brute Force adalah alur penyelesaian suatu permasalahan dengan cara berpikir yang sederhana dan tidak membutuhkan suatu permikiran yang lama. Sebenarnya, algoritma Brute Force merupakan algoritma yang muncul karena pada dasarnya alur pikir manusia adalah Brute Force (langsung/to the point). Jadi, Algoritma Brute Force merupakan algoritma pencocokan string yang ditulis tanpa memikirkan peningkatan performa. Algoritma ini sangat jarang dipakai dalam praktik, namun berguna dalam studi pembanding dan studi-studi lainnya. Banyak yang mengatakan bahwa algoritma brute force merupakan jenis algoritma yang sifatnya straight, lurus atau bisa juga disebut sebagai algoritma yang lempeng. Algoritma brute force merupakan bentuk algoritma yang sangat kompleks, karena untuk dapat menyelesaikan masalah dengan teknik straight forward atau lempeng ini, dibutuhkan banyak masukan dan juga pertimbangan secara logis, sehingga dapat diperoleh sebuah keputusan pemecahan masalah yang langsung mengacu atau menuju kepada hasil yang diinginkan.



2.2 Kelebihan dan Kelemahan Algoritma Brute Force 2.2.1 Kelebihan Algoritma Brute Force Karena merupakan sebuah algoritma yang memecahkan masalah secara jelas, dan melalui banyak opini atau pilihan, maka algoritma brute force merupakan sebuah metode pemecahan masalah logis yang memiliki kemampuan untuk memperoleh pemecahan masalah dengan baik. Dengan mempertimbangan banyak opsi, metode algoritma brute force mampu untuk menyaring satu dari sekian banyak solusi atau opsi 2



yang ditawarkan, sehingga proses pemecahan masalah yang dilakukan akan menjadi lebih baik dan juga lebih optimal. Hampir semua masalah yang dipecahkan dengan menggunakan metode algoritma brute force ini berjalan dengan baik. 2.2.2 Kelemahan Algoritma Brute Force Namun demikian, meskipun memiliki kelebihan berupa pemecahan masalah yang mampu berjalan dengan baik dan juga sempurna, algoritma brute force sangat sulit untuk digunakan pada kebutuhan pemecahan masalah yang cepat. Hal ini disebabkan karena algoritma brute force membutuhkan kumpulan banyak opsi terlebih dahulu sebulu dieksekusi. Hal ini membuat pertimbangan dalam memilih opsi akan menjadi lebih lambat.



2.3 Karakteristik Algoritma Brute Force Beberapa karakteristik dari algoritma Brute Force dijelaskan sebagai berikut : a. Algoritma brute force sebenarnya bukanlah algoritma yang cerdas dan mangkus (efisien), karena ia membutuhkan jumlah langkah yang besar atau banyak dalam penyelesaiannya dan tentu saja membutuhkan waktu yang berbanding lurus dengan jumlah langkah penyelesaiannya. Kadang-kadang algoritma brute force disebut juga algoritma naif (naïve algorithm). b. Algoritma brute force seringkali merupakan pilihan yang kurang disukai karena ketidak mangkusannya itu, tapi kalau mencari pola - pola dasar, keteraturan, atau trik - trik khusus, biasanya dapat membantu untuk menemukan algoritma yang lebih cerdas dan lebih mangkus lagi. c. Untuk persoalan - persoalan yang kecil, kesederhanaan brute force lebih diperhitungkan daripada ketidakmangkusannya. Algoritma brute force sering digunakan sebagai basis bila membandingkan beberapa alternatif algoritma yang mangkus. d. Meskipun brute force bukan merupakan teknik pemecahan masalah yang mangkus, namun teknik brute force dapat diterapkan pada sebagian besar persoalan. Bayangkan, sangat sulit menemukan masalah yang tidak dapat



3



dipecahkan dengan teknik brute force, tapi ada masalah yang hanya dapat dipecahkan secara brute force. e. Algoritma brute force sering digunakan sebagai basis bila membandingkan beberapa alternatif algoritma yang mangkus. f. Algoritma brute force seringkali lebih mudah diimplementasikan daripada algoritma yang lebih canggih, dan karena kesederhanaannya, kadangkadang algoritma brute force dapat lebih mangkus (ditinjau dari segi implementasi). Dalam beberapa kasus tertentu algoritma Brute Force hampir sama dengan Exhaustive Search. Exhausitve Search yang merupakan teknik pencarian solusi secara Brute Force pada masalah yang melibatkan pencarian elemen dengan sifat khusus.



2.4 Menyelesaikan Exhaustive Search dengan Brute Force Exhaustive search adalah teknik pencarian solusi secara brute force untuk masalah yang melibatkan pencarian elemen dengan sifat khusus. Biasanya elemen tersebut berada di antara objek-objek kombinatorik seperti permutasi, kombinasi, atau himpunan bagian dari sebuah himpunan. Berdasarkan definisi ini, maka dapat ditarik kesimpulan bahwa Exhaustive Search adalah Brute Force juga. Oleh karena itu Exhaustive Search adalah salah satu implementasi dari Brute Force dalam kasus pencarian. Masalah–masalah dalam Exhaustive Search dengan penerapan algoritma Brute Force dapat dirumuskan langkah langkahnya sebagai berikut: a. Enumerasi setiap solusi yang mungkin dengan cara yang sistematis. b. Evaluasi setiap kemungkinan solusi yang ditemukan satu per satu, meskipun terdapat beberapa kemungkinan ditemukannya solusi yang tidak layak atau bahkan terdapat kemungkinan–kemungkinan solusi terbaik yang telah ditemukan dan dievaluasi. c. Bila pencarian sudah sampai pada tujuan, maka pilih solusi yang terbaik. Jika diamati, langkah-langkah algoritma ini mirip dengan metode pencarian Generate and Test. Generate and Test akan memeriksa satu per satu seluruh 4



solusi yang mungkin kemudian menentukan solusi mana yang terbaik. Kelemahan metode ini adalah besarnya cost dan time yang diperlukan untuk data kompleks. Kali ini, pembahasan bukan pada teori algoritma exhautive search. Langsung fokus ke implementasi algoritma exhautive search untuk rekomendasi jadwal rapat. Sebagai studi kasus, dilakukan pencarian rekomendasi jadwal rapat untuk dosen. Hal ini menarik karena algoritma harus menentukan solusi terbaik jadwal rapat yang tidak bentrok dengan jadwal mengajar dosen. Atau jika bentrok dengan jadwal mengajar dosen, sistem harus mencari solusi terbaik dengan tingkat bentrok yang paling minimum. Mengapa harus menggunakan sistem untuk atur jadwal rapat dosen? Coba bayangkan, seandainya di suatu prodi hanya ada 6 dosen dan puluhan jadwal mengajar, mungkin saja mampu menentukan jadwal rapat secara manual. Bagaimana jika sebaliknya, ada puluhan dosen dan ratusan jadwal mengajar. Apa kaprodinya tidak pusing menentukan jadwal rapat?



5



2.5 Cara Kerja Algoritma Brute Force Secara sistematis, langkah-langkah yang dilakukan algoritma brute force pada saat mencocokkan string adalah: 1) Algoritma brute force mulai mencocokkan pattern pada awal teks. 2) Dari kiri ke kanan, algoritma ini akan mencocokkan karakter per karakter pattern dengan karakter di teks yang bersesuaian, sampai salah satu kondisi berikut dipenuhi: a. Karakter di pattern dan di teks yang dibandingkan tidak cocok (mismatch). b. Semua karakter di pattern cocok. Kemudian algoritma akan memberitahukan penemuan di posisi ini. 3) Algoritma kemudian terus menggeser pattern sebesar satu ke kanan, dan mengulangi langkah ke-2 sampai pattern berada di ujung teks. Berikut adalah Algoritma brute force yang sedang bekerja mencari string:



Gambar 1. Langkah Brute Force mencari string



6



Dengan menggunakan Pseudocode algoritma brute force ini: procedure BruteForceSearch( input m, n : integer, input P : array[0..n-1] of char, input T : array[0..m-1] of char, output ketemu : array[0..m-1] of boolean ) Deklarasi: i, j: integer Algoritma: for (i:=0 to m-n) do j:=0 while (j < n and T[i+j] = P[j]) do j:=j+1 endwhile if(j >= n) then ketemu[i]:=true; endif endfor



Jadi secara keselurhuan cara kerjanya yaitu: 



Enumerasi (list) setiap solusi yang mungkin dengan cara yang sistematis.







Evaluasi setiap kemungkinan solusi satu per satu dan simpan solusi terbaik yang ditemukan sampai sejauh ini (the best solusi found so far).







Bila pencarian solusi berakhir, umumkan solusi terbaik (the winner).



2.6 Contoh Penerapan Algoritma Brute Force Berikut ini adalah contoh-contoh penerapan algoritma Brute Force pada perhitungan matematika biasa. 1. Menghitung an (a > 0, n adalah bilangan bulat tak-negatif) an = a x a x … x a (n kali) , jika n > 0 =1



, jika n = 0



Algoritma: kalikan 1 dengan a sebanyak n kali.



7



2. Menghitung n! (n bilangan bulat tak-negatif) n! = 1 × 2 × 3 × … × n , jika n > 0 =1



, jika n = 0



Algoritma: kalikan n buah bilangan, yaitu 1, 2, 3, …, n, sekaligus. 3. Mengalikan dua buah matrik yang berukuran n × n. Misalkan C = A × B dan elemen-elemen matrik dinyatakan sebagai cij, aij, dan bij. Algoritma: hitung setiap elemen hasil perkalian satu per satu, dengan cara mengalikan dua vektor baris dan kolom yang panjangnya n. 4. Menemukan semua faktor dari bilangan bulat n selain dari 1 dan n itu sendiri. Definisi: Bilangan bulat a adalah faktor dari bilangan bulat b jika a habis membagi b. 5. Mencari elemen terbesar (atau terkecil) Diberikan sebuah himpunan yang beranggotakan n buah bilangan bulat. Bilangan-bilangan bulat tersebut dinyatakan sebagai a1, a2, …, an. Carilah elemen terbesar di dalam himpunan tersebut. 6. Sequential Search Diberikan n buah bilangan bulat yang dinyatakan sebagai a1, a2, …, an. Carilah apakah x terdapat di dalam himpunan bilangan bulat tersebut. Jika x ditemukan, maka lokasi (indeks) elemen yang bernilai x disimpan di dalam peubah idx. Jika x tidak terdapat di dalam himpunan tersebut, maka idx diisi dengan nilai 0. 7. Bubble Sort Algoritma Bubble Sort mengimplementasikan teknik Brute Force dengan jelas sekali. Karena algoritma tersebut yang paling simple, baik dalam hal pengertian maupun penerapannya. Ide dari algoritma ini adalah mengulang proses pembanding antara tiap – tiap elemen array dan



8



menukarnya apabila urutannya salah. Pembandingan elemen – elemen ini akan terus diulang hingga tidak perlu dilakukan penukaran lagi. Algoritma ini termasuk dalam golongan algoritma comparison sort, karena menggunakan perbandingan dalam operasi antar elemennya. Berikut ini adalah gambaran dari algoritma bubble sort. Misalkan kita mempunyai sebuah array dengan elemen “4 2 5 3 9”. Proses yang akan terjadi apabila menggunakan algoritma bubble sort adalah sebagai berikut.



8. Menghitung nilai polinom secara Brute Force Algoritma Brute Force pada penyelesaian masalah Knapsack dilakukan dengan menghitung satu per satu keuntungan yang diperoleh dari semua kemungkinan pemilihan barang yang ada. Banyaknya kemungkinan pemilihan barang tersebut dapat dirumuskan sebagai: 2n. Adapun n adalah jumlah dari barang yang akan dikirim. Jadi, seandainya banyak barang yang akan dikirm 5 buah, maka untuk mencari solusi optimal diperlukan 25 = 32 kemungkinan. Memang, akan didapatkan hasil yang sangat optimal mengingat akan ditelusuri satu per satu kemungkinan yang ada, tetapi akan sangat membutuhkan waktu yang sangat lama (perhitungan manual) dan memori yang besar (jika menggunakan program komputer) untuk jumlah barang yang ada sangat banyak.



9



BAB III - PENUTUP 3.1 Kesimpulan Algoritma merupakan langkah atau cara untuk menyelesaikan suatu masalah. Algoritma juga sangat dekat dengan kehidupan sehari – hari manusia. Pada kasus ini yang dibahas adalah Algoritma Brute Force dimana algoritma ini merupakan alur penyelesaian suatu permasalahan dengan cara berpikir yang sederhana dan tidak membutuhkan suatu pemikiran yang lama. Dan Algoritma Brute Force ini juga banyak memiliki jenis algoritma yang berbeda – beda sesuai dengan masalah yang dihadapi program atau yang dibutuhkan untuk menyelesaikan sebuah masalah dengan program. Algoritma Brute Force cocok untuk menyelesaikan permasalahan pencarian tingkat kemiripan. Untuk ukuran citra yang lebih besar, proses penentuan tingkat kemiripan akan lebih lambat,sehingga diperlukan algoritma yang lebih efektif.



3.2 Saran Diperlukan penelitian lebih lanjut dengan menggunakan algoritma lainnya sehingga proses dapat lebih efektif lagi.



10



DAFTAR PUSTAKA Afif, N., 2018. Implementasi Algoritma Brute Force Dalam Perancangan Aplikasi Penelusuran Skripsi. Jurnal INSTEK, Volume 3, p. 10. Aryo Pinandito, S. M., 2017. Chisiki No Yama. [Online] Available at: http://aryo.lecture.ub.ac.id/files/2013/03/DAA-III-Brute-Force.pptx [Accessed 05 10 2020]. Budiasa, R. M., 2009. Aplikasi Sederhana Pattern Matching dengan Algoritma Brute Force. Volume 1. Butarbutar, R. V., 2014. Penerapan Algoritma Brute Force pada perancangan Aplikasi Kamusta Bahasa Indonesia - Inggris berbasis Android, Medan: s.n. Munir, R., 2004. Makalah Algoritma Brute Force Departmen Teknik Informatika, s.l.: Institusi Teknologi Bandung. Wicaksana, A. P., 2014. Marvin Project. [Online] Available at: http://marvinproject.sourceforge.net/download/Makalah-IF30512012-025.pdf [Accessed 03 10 2020].



11