algoritma brute force

Algoritma Algoritma Brute ForceBrute Force

Strategi Algoritma Strategi Algoritma

Universitas Ahmad Dahlan Universitas Ahmad Dahlan

Definisi Definisi Brute ForceBrute Force

Brute forceBrute force adalah sebuah pendekatan yang adalah sebuah pendekatan yang lempang (lempang (straightforwardstraightforward) untuk memecahkan ) untuk memecahkan suatu masalah, biasanya didasarkan pada suatu masalah, biasanya didasarkan pada pernyataan masalah (pernyataan masalah (problem statementproblem statement) dan ) dan definisi konsep yang dilibatkan. definisi konsep yang dilibatkan.

Algoritma Algoritma brute forcebrute force memecahkan masalah memecahkan masalah dengan sangat sederhana, langsung dan dengan sangat sederhana, langsung dan dengan cara yang jelas (dengan cara yang jelas (obvious wayobvious way).).

Contoh-contoh Contoh-contoh Brute ForceBrute Force

1.1. Menghitung Menghitung aann ( (aa > 0, > 0, nn adalah adalah bilangan bulat tak-negatif)bilangan bulat tak-negatif) aann = = aa x x aa x … x x … x aa ( (nn kali) , jika kali) , jika nn > 0 > 0 = 1 = 1 , jika , jika nn = 0 = 0

Algoritma: kalikan 1 dengan Algoritma: kalikan 1 dengan aa sebanyak sebanyak nn kali kali

2. 2. Menghitung Menghitung nn! (! (nn bilangan bulat tak- bilangan bulat tak-negatif)negatif)

nn! = 1 × 2 × 3 × … × ! = 1 × 2 × 3 × … × nn , jika , jika nn > 0 > 0

= 1= 1 , jika , jika nn = 0 = 0

Algoritma: kalikan Algoritma: kalikan nn buah bilangan, yaitu buah bilangan, yaitu 1, 2, 3, …, 1, 2, 3, …, nn, bersama-sama, bersama-sama

3.3. Mengalikan dua buah matrik yang Mengalikan dua buah matrik yang berukuran berukuran nn × × nn..

Misalkan Misalkan CC = = AA × × BB dan elemen-elemen matrik dan elemen-elemen matrik dinyatakan sebagai dinyatakan sebagai ccijij, , aaijij, dan , dan bbijij

Algoritma: hitung setiap elemen hasil perkalian Algoritma: hitung setiap elemen hasil perkalian satu per satu, dengan cara mengalikan dua satu per satu, dengan cara mengalikan dua vektor yang panjangnya vektor yang panjangnya nn..

n

kkjiknjinjijiijbabababac

12211

procedure PerkalianMatriks(input A, B : Matriks, input n : integer, output C : Matriks) { Mengalikan matriks A dan B yang berukuran n × n, menghasilkan matriks C yang juga berukuran n × n

Masukan: matriks integer A dan B, ukuran matriks n Keluaran: matriks C } Deklarasi i, j, k : integer Algoritma for i1 to n do for j1 to n do C[i,j]0 { inisialisasi penjumlah } for k 1 to n do C[i,j]C[i,j] + A[i,k]*B[k,j] endfor endfor endfor

Adakah algoritma perkalian matriks yang lebih mangkus daripada brute force?

4.4. Menemukan semua faktor dari Menemukan semua faktor dari bilangan bulat bilangan bulat nn selain dari 1 dan selain dari 1 dan nn itu itu sendiri. sendiri.

Definisi: Bilangan bulat Definisi: Bilangan bulat aa adalah faktor adalah faktor dari bilangan bulat dari bilangan bulat bb jika jika aa habis habis membagi membagi bb..

procedure CariFaktor(input n : integer) { Mencari faktor dari bilangan bulat n selain 1 dan n itu sendiri. Masukan: n Keluaran: setiap bilangan yang menjadi faktor n dicetak. } Deklarasi k : integer Algoritma: k1 ketemu false for k2 to n - 1 do if n mod k = 0 then write(k) endif endfor

Adakah algoritma pemfaktoran yang lebih baik daripada brute force?

5.5. Mencari elemen terbesar (atau Mencari elemen terbesar (atau terkecil)terkecil)

PersoalanPersoalan: Diberikan sebuah himpunan yang : Diberikan sebuah himpunan yang beranggotakan beranggotakan nn buah bilangan bulat. buah bilangan bulat. Bilangan-bilangan bulat tersebut dinyatakan Bilangan-bilangan bulat tersebut dinyatakan sebagai sebagai aa11, , aa22, …, , …, aann. Carilah elemen terbesar . Carilah elemen terbesar

di dalam himpunan tersebut.di dalam himpunan tersebut.

procedure CariElemenTerbesar(input a1, a2, ..., an : integer, output maks : integer) { Mencari elemen terbesar di antara elemen a1, a2, ..., an. Elemen terbesar akan disimpan di dalam maks. Masukan: a1, a2, ..., an Keluaran: maks } Deklarasi k : integer Algoritma: maksa1 for k2 to n do if ak > maks then maksak endif endfor

Kompleksitas algoritma ini adalah O(n).

6.6. Sequential SearchSequential Search

PersoalanPersoalan: Diberikan : Diberikan nn buah bilangan bulat buah bilangan bulat yang dinyatakan sebagai yang dinyatakan sebagai aa11, , aa22, …, , …, aann. Carilah . Carilah

apakah x terdapat di dalam himpunan apakah x terdapat di dalam himpunan bilangan bulat tersebut. Jika bilangan bulat tersebut. Jika xx ditemukan, ditemukan, maka lokasi (indeks) elemen yang bernilai maka lokasi (indeks) elemen yang bernilai xx disimpan di dalam peubah disimpan di dalam peubah idxidx. Jika . Jika xx tidak tidak terdapat di dalam himpunan tersebut, maka terdapat di dalam himpunan tersebut, maka idxidx diisi dengan nilai 0. diisi dengan nilai 0.

procedure PencarianBeruntun(input a1, a2, ..., an : integer, x : integer, output idx : integer) { Mencari x di dalam elemen a1, a2, ..., an. Lokasi (indeks elemen) tempat x ditemukan diisi ke dalam idx. Jika x tidak ditemukan, maka idx diisi dengan 0. Masukan: a1, a2, ..., an Keluaran: idx } Deklarasi k : integer Algoritma: k1 while (k < n) and (ak x) do k k + 1 endwhile { k = n or ak = x } if ak = x then { x ditemukan } idxk else idx 0 { x tidak ditemukan } endif

Kompleksitas algoritma ini adalah O(n). Adakah algoritma pencarian elemen yang lebih mangkus daripada brute force?

7.7. Bubble SortBubble Sort

• Apa metode yang paling lempang dalam Apa metode yang paling lempang dalam memecahkan masalah pengurutan? memecahkan masalah pengurutan? Jawabnya adalah algoritma pengurutan Jawabnya adalah algoritma pengurutan bubble sortbubble sort. .

• Algoritma Algoritma bubble sortbubble sort mengimplementasikan teknik mengimplementasikan teknik brute forcebrute force dengan jelas sekali. dengan jelas sekali.

procedure BubbleSort (input/output L : TabelInt, input n : integer) { Mengurutkan tabel L[1..N] sehingga terurut menaik dengan metode pengurutan bubble sort.

Masukan : Tabel L yang sudah terdefenisi nilai-nilainya. Keluaran: Tabel L yang terurut menaik sedemikian sehingga L[1] L[2] … L[N]. } Deklarasi

i : integer { pencacah untuk jumlah langkah } k : integer { pencacah,untuk pengapungan pada setiap langkah } temp : integer { peubah bantu untuk pertukaran } Algoritma: for i 1 to n - 1 do for k n downto i + 1 do if L[k] < L[k-1] then {pertukarkan L[k] dengan L[k-1]} temp L[k] L[k] L[k-1] L[k-1] temp endif endfor endfor

Kompleksitas algoritma ini adalah O(n2). Adakah algoritma pengurutan elemen elemen yang lebih mangkus daripada brute force?

8. Uji keprimaan8. Uji keprimaan

PersoalanPersoalan: Diberikan sebuah bilangan bilangan : Diberikan sebuah bilangan bilangan bulat positif. Ujilah apakah bilangan tersebut bulat positif. Ujilah apakah bilangan tersebut merupakan bilangan prima atau bukan. merupakan bilangan prima atau bukan.

function Prima(input x : integer)boolean { Menguji apakah x bilangan prima atau bukan. Masukan: x Keluaran: true jika x prima, atau false jika x tidak prima. } Deklarasi k, y : integer test : boolean Algoritma: if x < 2 then { 1 bukan prima } return false else if x = 2 then { 2 adalah prima, kasus khusus } return true else y x testtrue while (test) and (y 2) do if x mod y = 0 then testfalse else yy - 1 endif endwhile { not test or y < 2 } return test endif endif

Adakah algoritma pengujian bilangan prima yang lebih mangkus daripada brute force?

9.9. Menghitung nilai polinomMenghitung nilai polinom secarasecara brute forcebrute force

Persoalan: Hitung nilai polinom Persoalan: Hitung nilai polinom

pp((xx) = ) = aannxxnn + + aann-1-1xxnn-1-1 + … + + … + aa11x + x + aa00

pada titik pada titik xx = = xx00..

function polinom(input x0 : real)real { Menghitung nilai p(x) pada x = x0. Koefisien-koefisein polinom sudah disimpan di dalam tabel a. Derajat polinom (n) juga sudah terdefinisi. Masukan: x0 Keluaran: nilai polinom pada x = x0. } Deklarasi i, j : integer p, pangkat : real Algoritma: p0 for in downto 0 do pangkat1 for j1 to i do {hitung xi } pangkatpangkat * x0 endfor pp + ai * pangkat endfor return p

Kompleksitas algoritma ini adalah O(n2).

Perbaikan (Perbaikan (improveimprove):): function polinom2(input x0 : real)real { Menghitung nilai p(x) pada x = x0. Koefisien-koefisein polinom sudah disimpan di dalam tabel a. Derajat polinom (n) juga sudah terdefinisi. Masukan: x0 Keluaran: nilai polinom pada x = x0. } Deklarasi i, j : integer p, pangkat : real Algoritma: pa0 pangkat1 for i1 to n do pangkatpangkat * x0 pp + ai * pangkat endfor return p

Kompleksitas algoritma ini adalah O(n). Adakah algoritma perhitungan nilai polinom yang lebih mangkusdaripada brute force?

Karakteristik AlgoritmaKarakteristik AlgoritmaBrute ForceBrute Force

1.1. Algoritma Algoritma brute forcebrute force umumnya tidak “cerdas” dan umumnya tidak “cerdas” dan tidak mangkus, karena ia membutuhkan jumlah tidak mangkus, karena ia membutuhkan jumlah langkah yang besar dalam penyelesaiannya. Kadang-langkah yang besar dalam penyelesaiannya. Kadang-kadang algoritma kadang algoritma brute forcebrute force disebut juga algoritma disebut juga algoritma naif (naif (naïve algorithmnaïve algorithm). ).

2.2. Algoritma Algoritma brute forcebrute force seringkali merupakan pilihan seringkali merupakan pilihan yang kurang disukai karena ketidakmangkusannya yang kurang disukai karena ketidakmangkusannya itu, tetapi dengan mencari pola-pola yang mendasar, itu, tetapi dengan mencari pola-pola yang mendasar, keteraturan, atau trik-trik khusus, biasanya akan keteraturan, atau trik-trik khusus, biasanya akan membantu kita menemukan algoritma yang lebih membantu kita menemukan algoritma yang lebih cerdas dan lebih mangkus.cerdas dan lebih mangkus.

3.3. Untuk masalah yang ukurannya kecil, Untuk masalah yang ukurannya kecil, kesederhanaan kesederhanaan brute forcebrute force biasanya biasanya lebih diperhitungkan daripada lebih diperhitungkan daripada ketidakmangkusannya. ketidakmangkusannya.

Algoritma Algoritma brute forcebrute force sering digunakan sering digunakan sebagai basis bila membandingkan sebagai basis bila membandingkan beberapa alternatif algoritma yang beberapa alternatif algoritma yang mangkus. mangkus.

4.4. Algoritma Algoritma brute forcebrute force seringkali lebih seringkali lebih mudah diimplementasikan daripada mudah diimplementasikan daripada algoritma yang lebih canggih, dan karena algoritma yang lebih canggih, dan karena kesederhanaannya, kadang-kadang kesederhanaannya, kadang-kadang algoritma algoritma brute forcebrute force dapat lebih dapat lebih mangkus (ditinjau dari segi mangkus (ditinjau dari segi implementasi).implementasi).

Referensi Referensi Rinaldi Munir, 2010, Rinaldi Munir, 2010, Diktat Kuliah Strategi Algoritma Diktat Kuliah Strategi Algoritma

ITBITB Gilles Brassard, 1996, Gilles Brassard, 1996, Fundamental Of AlgoritmhFundamental Of Algoritmh, ,

Prentice Hall, New JerseyPrentice Hall, New Jersey Cormen et al, 2009, Introduction to Algorithms : thrid Cormen et al, 2009, Introduction to Algorithms : thrid

edition, MITedition, MIT