Algoritma-Decrease-and-Conquer-2021-Bagian1.pptx

materi presentasi

1. Algoritma Decrease and Conquer 1 B y Rugaiyah Balqis 09012622529007

2. Definisi Decrease and Conquer 2 Decrease and conquer : metode perancangan algoritma dengan mereduksi persoalan menjadi dua sub - persoalan ( sub- problem ) yang lebih kecil, tetapi selanjutnya hanya memproses satu sub- persoalan saja. Berbeda dengan divide and conquer yang memproses semua sub - persoalan dan menggabung semua solusi setiap sub- persoalan . Di dalam literatur lama, semua algoritma yang membagi persoalan menjadi dua sub - persoalan yang lebih kecil dimasukkan ke kategori divide and conquer . Meskipun demikian, tidak kedua sub - persoalan hasil pembagian diselesaikan. Jika hanya satu sub - persoalan yang diselesaikan, maka tidak tepat dimasukkan sebagai algoritma divide and conquer . Mereka dikategorikan sebagai decrease and conquer

3. 3 Algoritma decrease and conquer terdiri dari dua tahapan: Decrease : mereduksi persoalan menjadi beberapa persoalan yang lebih kecil (biasanya dua sub - persoalan ). Conquer : memproses satu sub - persoalan secara rekursif. Tidak ada tahap combine dalam decrease and conquer , karena hanya satu sub - persoalan yang diselesaikan.

4. Tiga varian decrease and conquer : 4 Decrease by a constant : ukuran instans persoalan direduksi sebesar konstanta yang sama setiap iterasi algoritma. Biasanya konstanta = 1. insertion sort graph traversal algorithms (DFS and BFS) topological sorting algorithms for generating permutations, subsets 2. Decrease by a constant factor : ukuran instans persoalan direduksi sebesar faktor konstanta yang sama setiap iterasi algoritma. Biasanya faktor konstanta = 2. binary search and bisection method exponentiation by squaring multiplication à la russe

5. 3. Decrease by a variable size : ukuran instans persoalan direduksi bervariasi pada setiap iterasi algoritma . - Euclid’s algorithm - selection by partition - Nim-like games

6. Decrease by a Constant 5 Contoh persoalan: Perpangkatan a n Selection sort Insertion sort

7. 1. Persoalan perpangkatan a n 7 Dengan metode decrease and conquer : Bila diselesaikan: T(n) = T(n – 1) + 1 = …. = O(n) sama seperti algoritma brute-force .   T ( n  1)  1 , n  Kompleksitas waktu (berdasarkan jumlah operasi kali): , n  T ( n )     1 , n  a n  1  a , n  a n  

8. 8 function exp ( a : real ; n : integer )  real { memberikan hasil perpangkatan a n } Deklarasi k : integer Algoritma : if n = then return 1 E lse return exp( a , n – 1) * a endif

9. 2. Selection sort. 9 Selection Sort adalah pengurutan hard split/easy join dengan cara mempartisi larik menjadi dua buah sub larik , sub larik pertama hanya satu elemen, sedangkan sub larik kedua berukuran n – 1 elemen. 1 n – 1

10. 9 n 1 n – 1 1 n – 2 1 n – 3 ... 2 1 1 Pohon pembagian larik:

11. Proses partisi di dalam Selection Sort dilakukan dengan mencari elemen bernilai minimum (atau bernilai maksimum) di dalam larik A [ i. . j ] lalu elemen minimum ditempatkan pada posisi A [ i ] dengan cara pertukaran. Best case & worst case tetap O(n²) , karena kita masih harus mencari elemen minimum dalam setiap langkah . 10 i j A procedure SelectionSort ( input/output A : LarikInteger , input i , j : integer ) { Mengurutkan larik A[i..j] dengan algoritma Selection Sort Masukan: Larik A[i..j] yang sudah terdefinisi elemen-elemennya Luaran: Larik A[i..j] yang terurut } Deklarasi k : integer Algoritma: if i < j then { Ukuran(A) > 1 } Partisi3 ( A , i , j ) { Partisi menjadi 1 elemen dan n – 1 elemen } i SelectionSort ( A , i +1, j ) { Urut hanya sub larik A[i+1..j] dengan Selection Sort } endif i+1 j

12. 11 procedure Partisi3 ( input/output A : LarikInteger , input i , j : integer ) { Menmpartisi larik A[i..j] dengan cara mencari elemen minimum di dalam A[i..j], dan menempatkan elemen terkecil sebagai elemen pertama larik. Masukan: A[i..j] sudah terdefinisi elemen-elemennya Luaran: A[i..j] dengan A[i] adalah elemen minimum. } Deklarasi idxmin , k : integer Algoritma: idxmin  i for k  i +1 to j do if A [ k ] < A [ idxmin ] then idxmin  k endif endfor swap ( A [ i ], A [ idxmin ]) { pertukarkan A[i] dengan A[idxmin] } i j A

13. Contoh 1. Misalkan tabel A berisi elemen- elemen berikut: 1 21 5 2 1 21 5 2 4 21 5 2 4 21 5 12 4 21 5 12 4 12 3 9 Langkah- langkah pengurutan dengan Selection Sort : 4 12 3 9 1 12 3 9 1 2 3 9 1 2 3 9 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 9 21 5 12 5 21 9 12 5 9 12 21 5 9 12 21 5 9 12 21  terurut! 12

14. 13 Kompleksitas waktu algoritma Selection Sort :   T ( n  1)  cn T ( n )   , n  1 , n  1 a Penyelesaiannya sama seperti pada Insertion Sort : T ( n ) = O ( n 2 ).

15. Kompleksitas waktu algoritma Selection Sort: T ( n ) = waktu pembagian + waktu pemanggilan rekurens Selection Sort untuk bagian tabel kanan yang berukuran n elemen.   T ( n  1)  cn T ( n )   , n  1 , n  1 a Persamaan pada bagian rekurensi bila diselesaikan menghasilkan T ( n ) = O ( n 2 ). 14

16. Decrease by a Constant Factor 15 Contoh persoalan: Binary search Mencari koin palsu

17. 3. Binary search 17 Kondisi awal: larik A sudah terurut menaik K adalah nilai yang dicari di dalam larik i mid j ½ bagian kiri ½ bagian kanan Jika elemen tengah ( mid )  k , maka pencarian dilakukan hanya pada setengah bagian larik (kiri atau kanan) Ukuran persoalan selalu berkurang sebesar setengah ukuran semula. Hanya setengah bagain yang diproses, setengah bagian lagi tidak.

18. procedure binsearch ( input A : LarikInteger , i , j : integer ; K : integer ; output idx : integer ) { Mencari elemen bernilai K di dalam larik A[i..j]. Masukan: larik A sudah terurut menaik , K sudah terdefinisi nilainya Luaran: indek lariks sedemikian sehingga A[idx] = K } Deklarasi mid : integer Algoritma : if i > j then idx  –1 { ukuran larik sudah 0} { K tidak ditemukan } else mid  ( i + j )/2 if A ( mid ) = K then idx  mid { K ditemukan } { indeks elemen larik yang bernilai = K } else if A ( mid ) > K then binsearch ( A , i , mid – 1, K , idx ) else binsearch ( A , mid + 1, j , K , idx ) { cari di sub larik kiri, di dalam larik A[i..mid]} { cari di sub larik kanan, di dalam larik A[mid+1..j} endif endif endif Algoritma Binary Search (Kasus 1: Larik sudah terurut menaik) 18 i j A i mid mid+1 j A

19. procedure binsearch ( input A : LarikInteger , i , j : integer ; K : integer ; output idx : integer ) { Mencari elemen bernilai K di dalam larik A[i..j]. Masukan: larik A sudah terurut menurun , K sudah terdefinisi nilainya Luaran: indek lariks sedemikian sehingga A[idx] = K } Deklarasi mid : integer Algoritma : if i > j then idx  –1 { ukuran larik sudah 0} { K tidak ditemukan } else mid  ( i + j )/2 if A ( mid ) = K then idx  mid { K ditemukan } { indeks elemen larik yang bernilai = K } else if A ( mid ) < K then binsearch ( A , i , mid – 1, K , idx ) else binsearch ( A , mid + 1, j , K , idx ) { cari di sub larik kiri, di dalam larik A[i..mid]} { cari di sub larik kanan, di dalam larik A[mid+1..j} endif endif endif Algoritma Binary Search (Kasus 2: Larik sudah terurut menurun) 19 i j A i mid mid+1 j A

20. Contoh 3: Misalkan diberikan larik A dengan delapan buah elemen yang sudah terurut menurun seperti di bawah ini: 20 Nilai K yang dicari adalah K = 16. Langkah- Langkah pencarian: A [4]  16 A [4] < 16 ? Tidak, cari pada sub larik kanan

21. A [6]  16 A [4] < 16 ? Ya, cari pada sub larik kiri A [5] = 16 Pencarian ditemukan pada idx = 5 20

22. 22 Jumlah operasi perbandingan elemen- elemen larik: Relasi rekursens tersebut diselesaikan secara iteratif sbb (atau pakai Teorema Master): T(n) = 1 + T(n/2) = 1 + (1 + T(n/4)) = 2 + T(n/4) = 2 + (1 + T(n/8)) = 3 + T(n/8) = … = k + T(n/2 k ) Asumsi: ukuran larik adalah perpangkatan dua, atau n = 2 k  k = 2 log n T(n) = 2 log n + T(1) = 2 log n + (1 + T(0)) = 1 + 2 log n = O( 2 log n)   1  T ( n / 2) T ( n )   , n  , n 

23. 4. Mencari koin palsu 23 Diberikan n buah koin yang identik, satu diantaranya palsu. Asumsikan koin yang palsu mempunyai berat yang lebih ringan daripada koin asli. Untuk mencari yang palsu, disediakan sebuah timbangan yang teliti. Carilah koin yang palsu dengan cara penimbangan.

24. Algoritma decrease and conquer : Bagi himpunan koin menjadi dua sub - himpunan ( subset ), masing- masing  n /2  koin. Jika n ganjil, maka satu buah koin tidak dimasukkan ke dalam kedua sub - himpunan. Timbang kedua sub - himpunan dengan neraca. Jika beratnya sama, berarti satu koin yang tersisa adalah palsu. Jika beratnya tidak sama, maka ulangi proses untuk sub - himpunan yang beratnya lebih ringan (salah satu koin di dalamnya palsu). 24

25. 25 Ukuran persoalan selalu berkurang dengan faktor setengah dari ukuran semula. Hanya setengah bagian yang diproses, setengah bagian yang lain tidak diproses. Jumlah penimbangan yang dilakukan adalah: Penyelesaian relasi rekurens T(n) mirip seperti binary search , atau menggunakan Teorema Master: T(n) = 1 + T(  n/2  ) = …. = O( 2 log n)   1  T (  n / 2  ) T ( n )   , n  1 , n  1

26. 5. Persoalan Perkalian Petani Rusia 26 Perkalian Petani Rusia adalah metode perkalian yang menggunakan pembagian berulang dan penjumlahan . Digunakan dalam sistem komputasi awal karena hanya melibatkan operasi sederhana ( penjumlahan dan pergeseran bit). Prinsip Kerja Ambil dua bilangan yang akan dikalikan . Bagi bilangan pertama dengan 2 secara berulang hingga mencapai 1. Kalikan bilangan kedua dengan 2 pada setiap langkah . Abaikan baris di mana bilangan pertama bernilai genap . Jumlahkan hasil dari bilangan kedua yang sesuai .

27. Contoh: menghitung 18  2 5 dengan metode perkalian petani Rusia 27

28. function RussianPeasantMultiplication (a, b) result ← 0 while a > 0 do if a mod 2 ≠ 0 then result ← result + b end if a ← a // 2 # Bagi 2 b ← b * 2 # Kali 2 end while return result Jumlah iterasi maksimum: O(log n) Kompleksitas waktu : O(log n)

29. Decrease by a Variable Size Contoh 7 : Menghitung median dan Selection Problem . Selection problem : mencari elemen terkecil ke- k di dalam sebuah senarai beranggotan n elemen. Jika k = 1 → elemen paling kecil (minimum) Jika k = n → elemen paling besar (maksimum) Jika k = ⎡n/2⎤ → elemen median Bagaimana mencari median dari senarai yang tidak terurut namun tidak perlu mengurutkan senarai terlebih dahulu? 29

30. Algoritmanya : Lakukan partisi pada senarai seperti proses partisi pada algoritma Quick Sort. Partisi menghasilkan setengah elemen senarai lebih kecil atau sama dengan pivot p dan setengah bagian lagi lebih besar dari pivot p . Misalkan s adalah posisi pem-partisian . Jika s = ⎡n/2⎤, maka pivot p adalah nilai median yang dicari Jika s > ⎡n/2⎤, maka median terdapat pada setengah bagian kiri Jika s < ⎡n/2⎤, maka median terdapat pada setengah bagian kanan 30

31. Contoh : Temukan median dari 4, 1, 10, 9, 7, 12, 8, 2, 15. pada contoh ini, k = ⎡9/2⎤ = 5, sehingga persoalannya adalah mencari elemen terkecil ke-5 di dalam senarai. Partisi senarai dengan memilih elemen pertama sebagai pivot: 4 1 10 9 7 12 8 2 15 Hasil partisi: 2 1 4 9 7 12 8 10 15 Karena s = 3 < 5, kita memproses setengah bagian kanan: 9 7 12 8 10 15 8 7 9 12 10 15 Karena s = 6 > 5, kita memproses setengah bagian kiri: 8 7 7 8 31 Sekarang s = k = 5 → stop. Jadi median = 8

32. Kompleksitas algoritma: Solusi dari relasi rekurens tersebut adalah: T(n) = T(n/2) + cn = … = O(n) 32

33. Terima Kasih