Top Banner
Algoritma Algoritma Brute Force Brute Force
22

Algoritma Brute Force. Definisi Brute Force Brute force adalah sebuah pendekatan yang lempang (straightforward) untuk memecahkan suatu masalah, biasanya.

Dec 14, 2015

Download

Documents

Rizqi Subagyo
Welcome message from author
This document is posted to help you gain knowledge. Please leave a comment to let me know what you think about it! Share it to your friends and learn new things together.
Transcript
Page 1: Algoritma Brute Force. Definisi Brute Force  Brute force adalah sebuah pendekatan yang lempang (straightforward) untuk memecahkan suatu masalah, biasanya.

Algoritma Algoritma Brute ForceBrute Force

Page 2: Algoritma Brute Force. Definisi Brute Force  Brute force adalah sebuah pendekatan yang lempang (straightforward) untuk memecahkan suatu masalah, biasanya.

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).).

Page 3: Algoritma Brute Force. Definisi Brute Force  Brute force adalah sebuah pendekatan yang lempang (straightforward) untuk memecahkan suatu masalah, biasanya.

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

Page 4: Algoritma Brute Force. Definisi Brute Force  Brute force adalah sebuah pendekatan yang lempang (straightforward) untuk memecahkan suatu masalah, biasanya.

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

Page 5: Algoritma Brute Force. Definisi Brute Force  Brute force adalah sebuah pendekatan yang lempang (straightforward) untuk memecahkan suatu masalah, biasanya.

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

Page 6: Algoritma Brute Force. Definisi Brute Force  Brute force adalah sebuah pendekatan yang lempang (straightforward) untuk memecahkan suatu masalah, biasanya.

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?

Page 7: Algoritma Brute Force. Definisi Brute Force  Brute force adalah sebuah pendekatan yang lempang (straightforward) untuk memecahkan suatu masalah, biasanya.

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..

Page 8: Algoritma Brute Force. Definisi Brute Force  Brute force adalah sebuah pendekatan yang lempang (straightforward) untuk memecahkan suatu masalah, biasanya.

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?

Page 9: Algoritma Brute Force. Definisi Brute Force  Brute force adalah sebuah pendekatan yang lempang (straightforward) untuk memecahkan suatu masalah, biasanya.

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.

Page 10: Algoritma Brute Force. Definisi Brute Force  Brute force adalah sebuah pendekatan yang lempang (straightforward) untuk memecahkan suatu masalah, biasanya.

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).

Page 11: Algoritma Brute Force. Definisi Brute Force  Brute force adalah sebuah pendekatan yang lempang (straightforward) untuk memecahkan suatu masalah, biasanya.

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.

Page 12: Algoritma Brute Force. Definisi Brute Force  Brute force adalah sebuah pendekatan yang lempang (straightforward) untuk memecahkan suatu masalah, biasanya.

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?

Page 13: Algoritma Brute Force. Definisi Brute Force  Brute force adalah sebuah pendekatan yang lempang (straightforward) untuk memecahkan suatu masalah, biasanya.

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.

Page 14: Algoritma Brute Force. Definisi Brute Force  Brute force adalah sebuah pendekatan yang lempang (straightforward) untuk memecahkan suatu masalah, biasanya.

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?

Page 15: Algoritma Brute Force. Definisi Brute Force  Brute force adalah sebuah pendekatan yang lempang (straightforward) untuk memecahkan suatu masalah, biasanya.

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.

Page 16: Algoritma Brute Force. Definisi Brute Force  Brute force adalah sebuah pendekatan yang lempang (straightforward) untuk memecahkan suatu masalah, biasanya.

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?

Page 17: Algoritma Brute Force. Definisi Brute Force  Brute force adalah sebuah pendekatan yang lempang (straightforward) untuk memecahkan suatu masalah, biasanya.

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..

Page 18: Algoritma Brute Force. Definisi Brute Force  Brute force adalah sebuah pendekatan yang lempang (straightforward) untuk memecahkan suatu masalah, biasanya.

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).

Page 19: Algoritma Brute Force. Definisi Brute Force  Brute force adalah sebuah pendekatan yang lempang (straightforward) untuk memecahkan suatu masalah, biasanya.

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?

Page 20: Algoritma Brute Force. Definisi Brute Force  Brute force adalah sebuah pendekatan yang lempang (straightforward) untuk memecahkan suatu masalah, biasanya.

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.

Page 21: Algoritma Brute Force. Definisi Brute Force  Brute force adalah sebuah pendekatan yang lempang (straightforward) untuk memecahkan suatu masalah, biasanya.

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.

Page 22: Algoritma Brute Force. Definisi Brute Force  Brute force adalah sebuah pendekatan yang lempang (straightforward) untuk memecahkan suatu masalah, biasanya.

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).