DAA-PERTEMUAN 13-Metode Decrease and Conquer - 2021 [PDF]

Citation preview

1



DESAIN & ANALISIS ALGORITMA 19 May 2021



PERTEMUAN 13



3. Metode Decrease-and-Conquer 2











Teknik ini didasarkan pada ekploitasi hubungan antara solusi dari cuplikan sebuah permasalahan dengan solusi dari cuplikan yang lebih kecil dari permasalahan yang sama. Jika hubungan tersebut telah dibuat, maka dapat dieksploitasi dengan cara top-down (rekursif) atau bottomup (non-rekursif). Ada 3 variasi utama dari teknik ini:  







Decrease by a constant (ukuran berkurang dengan konstanta yang sama untuk tiap iterasi, biasanya berkurang 1) Decrease by a constant factor (berkurang dengan faktor konstan yg sama, biasanya 2  sehingga permasalahan mengecil hingga separuhnya) Variable size decrease (berkurang dengan nilai yang bervariasi, tiap iterasinya)



19 May 2021



3.1. Decrease by a Constant 3















Ukuran dari cuplikan permasalahan berkurang dengan konstanta yang sama pada tiap iterasi. Biasanya konstanta ini = 1. Contoh: masalah perhitungan eksponensial an untuk n bilangan integer positif. Hubungan antara solusi untuk permasalahan berukuran n dengan yg berukuran n-1 didapat dengan rumus: an = an-1. a



Sehingga fungsi f(n)=an dapat dihitung dengan cara “top-down” (pendekatan rekursif): f(n-1) . a



jika n >1



f(n) =



a



jika n = 1



atau dengan cara “bottom-up”, yakni dengan mengalikan a dengan dirinya sendiri sebanyak n-1 kali (pendekatan iteratif) 19 May 2021



Decrease by a Constant (lanjutan) 4



Problem of size n



Subproblem of size n-1



Solution to the subproblem



Solution to the original problem 19 May 2021



3.1.1. Insertion Sort 5











Merupakan algoritma sorting yang telah dibahas pada pertemuan ke-6 untuk mengurutkan array A[0…n-1]. Teknik ini mengasumsikan bahwa permasalahan yg berukuran lebih kecil (A[0…n-2]) sudah terurut, sehingga untuk mengurutkan seluruh elemen (A[0…n-1]) dilakukan dengan menyisipkan elemen A[n-1] ke posisi yang benar dengan menggunakan salah satu dari 3 cara berikut:  Mencari dari kiri ke kanan sampai ditemukan elemen yg ≥ A[n-1] dan memasukkan elemen A[n-1] di sisi kiri elemen tersebut.  Mencari dari kanan ke kiri sampai ditemukan elemen yg ≤ A[n-1] dan memasukkan elemen A[n-1] di sisi kanan elemen tersebut.  Menggunakan teknik binary search untuk mendapatkan posisi yang tepat untuk memasukkan elemen A[n-1].



19 May 2021



Insertion Sort (lanjutan) 6







Contoh:



Contoh sorting dengan Insertion Sort. Garis tebal memisahkan bagian yang sudah terurut dari elemen yang lain; elemen yang akan di-insert-kan adalah angka yg ditebalkan (bold) 19 May 2021



3.1.2. Depth-First Search (DFS) dan Breadth-First Search (BFS) 7







Depth-First Search  















Merupakan salah satu metode pencarian buta (blind search) terhadap vertex-vertex pada sebuah graph. DFS dimulai dengan memilih sebuah vertex sembarang dan menandai vertex tersebut sebagai “visited vertex” (vertex yg sudah dikunjungi). Pada setiap iterasi, DFS akan mengunjungi vertex yg “unvisited” (blm dikunjungi) yg ber-adjacent dengan vertex yg sekarang sedang dikunjungi. Lanjutkan proses sampai ditemui “dead end” (vertex dimana tidak ditemui lagi vertex lain yang beradjacent dan unvisited). Saat ini terjadi, maka yg dilakukan adalah mundur ke vertex sebelumnya dan mencoba melanjutkan mengunjungi vertex yg “unvisited” lain. Algoritma berhenti ketika sudah kembali lagi ke vertex awal setelah sebelumnya menemui “dead end”. Gunakan stack untuk mempermudah penelusuran operasi DFS. PUSH vertex ketika vertex tersebut pertama kali dikunjungi dan POP vertex ketika pada vertex tersebut menemui “dead end”. 19 May 2021



Depth-First Search (lanjutan) 8 



Berikut pseudocode untuk DFS:



ALGORITHM DFS(G) //Input: Graph G = (V, E)  Vertex dan Edge //Output: Graph G dengan vertex yg sudah dinomori sesuai urutan //penemuannya dengan penelusuran DFS Tandai tiap vertex pada V dengan 0 (berarti “unvisited”) count  0 for setiap vertex pada V do if v ditandai dengan 0 dfs(v) dfs(v) //mengunjungi scr rekursif semua vertex yg “unvisited” yg terhubung dgn // vertex v & menomorinya sesuai urutan kunjungan count  count + 1; beri nomor vertex v dgn count for tiap vertex w dalam V yg beradjacent dgn v do if w bernomor 0 dfs(w) 19 May 2021



9



PENELUSURAN DENGAN DFS 19 May 2021



Breadth-First Search (BFS) 10











Jika DFS bisa dianggap sebagai penelusuran bagi si “petualang pemberani” yang pergi sejauh mungkin dari kampung halamannya, maka BFS dapat dianggap sebagai penelusuran bagi si “petualang yang berhati-hati”. BFS menelusuri graph dengan cara mengunjungi semua vertex yang beradjacent dengan vertex awal, lalu melanjutkan penelusuran ke vertex “unvisited” lain yg berjarak 2 edge dari vertex yg sudah dikunjungi, dan seterusnya. 19 May 2021



Breadth-First Search (BFS) 11



Berikut pseudocode BFS: ALGORITHM BFS(G) //Input: Graph G = (V, E) //Output: Graph G dengan vertex yg sudah dinomori sesuai urutan penemuannya dgn BFS Tandai tiap vertex pada V dengan 0 (berarti “unvisited”) count  0 for setiap vertex pada V do if v ditandai dengan 0 bfs(v) bfs(v) //mengunjungi semua vertex yg “unvisited” yg terhubung dgn vertex v & menomorinya sesuai //urutan kunjungan count  count + 1; tandai v dengan nilai count dan inisialisasi queue dg v while queue tidak empty do for tiap vertex w dalam V yg beradjacent dg vertex awal do if w bernomor 0



count  count + 1; nomori w dengan count tambahkan vertex w ke queue hapus vertex awal dari queue



Penelusuran Graph dengan BFS. Nomor vertex menunjukkan urutan penelusuran graph dimulai dari root (1) 12



19 May 2021



Decrease and Conquer 13







Algoritma penelusuran graph DFS dan BFS dianggap menerapkan konsep decrease-andconquer karena:  Pada



setiap langkahnya, DFS dan BFS menandai vertex yang sudah dikunjungi dan melanjutkan proses ke vertex berikutnya (vertex tetangga)  Hal ini termasuk strategi decrease-by-one



30 May 2021



Latihan 14







Telusuri graph berikut dengan metode DFS dan BFS



19 May 2021



15



3.2. Decrease-by-a-ConstantFactor 







Merupakan teknik yang mengurangi permasalahan dengan faktor konstanta yg sama pada tiap iterasi, pada umumnya faktor konstanta ini = 2. BinarySearch juga termasuk dalam algoritma Decrease-by-a-Constant-Factor, karena BinarySearch mengurangi (sekaligus membagi) permasalahan menjadi setengahnya. 19 May 2021



Problem



of size n



Subproblem of size n/2



Solution to the subproblem



Solution to the original problem



Decrease-by-a-constant-factor 16



19 May 2021



17



3.2.1. Permasalahan Koin Palsu (Fake-Coin Problem) 











Terdapat n buah koin, diketahui salah satunya adalah koin palsu. Dengan menggunakan timbangan, dapat dibandingkan berat koin (misal koin yg palsu akan lebih ringan dari koin asli). Bagaimana algoritma untuk menentukan koin yang palsu tersebut? Cara yg paling natural adalah dengan membagi koin menjadi 2 tumpukan, masing2 berisi n / 2 koin, menyisakan 1 koin, jika n ganjil. Timbang kedua tumpukan, perhatikan hasilnya:  



Jika seimbang, berarti koin yg blm ditimbang adalah palsu. Jika tidak, lanjutkan penimbangan pada tumpukan yg lebih ringan 19 May 2021



Fake-Coin Problem 18











Walaupun kita membagi koin dalam 2 bagian, tetapi setelah satu penimbangan, kita dihadapkan pada problem yang berukuran setengah dari ukuran asal, sehingga ini termasuk teknik decrease-and-conquer. Relasi rekurensi untuk jumlah penimbangan yg dibutuhkan pada kasus worst case adalah: W (n)  W (n / 2)  1



untuk n>1, W(1)=0 19 May 2021



3.2.2. Josephus Problem 19 



Berasal dari nama sejarawan Yahudi, Flavius Josephus yang terlibat dalam revolusi Yahudi terhadap kerajaan Romawi (66-70). Sebagai jenderal, ia dapat menguasai kota Jotapata selama 47 hari, tetapi setelah kejatuhan kota tersebut, ia lari menyelamatkan diri bersama 40 pengikutnya ke sebuah gua. Disana, mereka bertekad untuk lebih baik mati daripada menyerah. Josephus menyarankan bahwa setiap orang, secara bergantian, harus membunuh rekan disebelahnya dengan menggunakan sebuah kapak dan menyerahkan kapak kepada rekan di sebelahnya lagi yang masih hidup, kemudian orang tsb juga membunuh rekan di sebelahnya, dan begitu seterusnya sampai semua orang terbunuh dan orang terakhir yang masih hidup harus bunuh diri. Josephus mendapat giliran terakhir, dan sebagai salah satu dari dua orang terakhir yang masih hidup, ia membunuh orang tersebut dan kemudian menyerahkan diri kepada bangsa Romawi.







Bagaimana strategi Josephus agar ia menjadi orang yg terakhir dan menjadi satu-satunya yg selamat? 19 May 2021



Josephus Problem (lanjutan) 20



19 May 2021



Josephus Problem (lanjutan) 21 



Permasalahannya adalah menentukan nomor urut yg “aman”, yaitu J(n). Misal: Jika n=6, maka yg tereliminasi pada putaran pertama adalah posisi 2, 4, dan 6. Sedangkan posisi 3 dan 1 akan tereliminasi pada putaran kedua, sehingga posisi yg selamat adalah 5, sehingga J(n) = 5.







Jika n=7, maka orang pada posisi 2, 4, 6, dan 1 tereliminasi pada putaran pertama. Pada putaran kedua, yg tereliminasi adalah posisi 5 dan 3, sehingga J(7) = 7.







Jika n genap (misal n=2k), maka iterasi pertama akan mengurangi ukuran permasalahan menjadi setengahnya. Perbedaannya hanya pada penomoran posisi; misal, orang pada nomor posisi awal 3 akan menjadi nomor 2 pada iterasi kedua, orang pada nomor posisi awal 5 akan menjadi nomor 3, dan seterusnya. (Perhatikan gambar berikut ini). 19 May 2021



Josephus Problem (lanjutan) 22



12 61



11 7



21



5



32 41 (a)



21



61



32 52



41 (b)



Contoh Josephus problem untuk (a) n=6 dan (b) n=7. Nilai subskrip menunjukkan iterasi dimana orang pada posisi tsb dieliminasi. Solusinya adalah J(6)=5 dan J(7)=7. 19 May 2021



Josephus Problem (lanjutan) 23







Untuk n genap:  Untuk



mendapatkan posisi awal seseorang, kalikan posisi baru dengan 2 dan kurangi dengan 1, sehingga: J(2k) = 2J(k) – 1







Untuk n ganjil:  Jika



n ganjil, maka n = 2k + 1. Iterasi pertama mengeliminasi semua orang pada posisi genap.  Untuk mendapatkan posisi awal seseorang, kalikan posisi baru dengan 2 dan tambahkan dengan 1, sehingga: J(2k+1) = 2J(k) + 1. 19 May 2021



Josephus Problem 24







Kembali permasalahan asal, berapakah J(41)?



19 May 2021



3.3. Variable-Size-Decrease 25 



Pada tipe ini, pengurangan pola bervariasi dari satu iterasi ke iterasi lain.







Contoh paling sederhana: algoritma Euclid untuk mencari Faktor Persekutuan Terbesar (FPB) dengan rumus: FPB(m, n) = FPB(n, m mod n).







Contoh lain: The Game of Nim (Nim’s Game): 



Permainan yang dimainkan oleh 2 orang. Ada setumpuk n kepingan dan 2 orang tersebut secara bergantian mengambil kepingan (minimal 1 dan maksimal m). Jumlah kepingan yg dapat diambil boleh bervariasi dalam tiap langkah pengambilannya, tetapi batas minimal & maksimalnya tetap. Pemenangnya adalah orang yg mengambil kepingan terakhir, sehingga lawannya tidak dapat melanjutkan permainan (kalah).







Bagaimana strategi untuk memenangkan permainan ini? Yaitu dengan mengambil n mod (m+1) kepingan pada tiap langkahnya.



26



Tugas Makalah: Dynamic Programming 1.



Tersedia topik-topik permasalahan Dynamic Programming berikut: https://www.geeksforgeeks.org/dynamic-programming/



2.



Untuk kategori Basic Problems, masing-masing mhs membuat makalah dengan nomor permasalahan sesuai dengan no urut pada daftar absensi kelas



3.



Kerangka isi makalah:



4.







Penjelasan dynamic programming (definisi, jenis permasalahan, teknik secara umum)







Penjelasan permasalahan dynamic programming sesuai tugas Anda di no. 2 (definisi, algoritma). Jika perlu, lampirkan gambar untuk menjelaskan permasalahan







Output dari source code yang dilampirkan untuk nomor permasalahan sesuai tugas, beserta penjelasannya







Kesimpulan







Daftar Pustaka (jika Anda menggunakan sumber tambahan selain website geeksforgeeks)



Waktu pengerjaan tugas: 1 minggu (dikumpulkan sebelum jam perkuliahan melalui e-learning Ilmu) 30 May 2021