1/4/2016
Bab 6: Transform-and-Conquer
Analisis Algoritma:
Agenda.
Anany Levitin, Introduction to Design and Analysis of Algorithm, 3rd Edition, Pearson Education, Inc., Addison-Wesley
• • • •
Fakultas Teknologi dan Desain 1-1 Informatika Program Studi Teknik
Introduction Instance Simplification Representation Change Problem Reduction
Analisis Algoritma |
Introduction
2
Introduction • Terdapat tiga variasi utama yang membedakan pengubahan (transform) yang dilakukan untuk setiap kasus:
Transform-and-conquer: teknik yang digunakan dalam perancangan algoritma yang akan mengubah (to transform) sebuah kasus menjadi bentuk lain, kemudian menentukan solusi (to conquer) dari bentuk baru kasus tersebut.
• Instance simplification: menyederhankan kasus ke dalam bentuk yang lebih sederhana agar mudah diselesaikan. • Representation change: mengubah representasi kasus ke dalam bentuk representasi yang lebih sederhana agar lebih efisien. • Problem reduction: mengubah ukuran problem ke dalam ukuran problem yang lebih mudah untuk diselesaikan.
Analisis Algoritma |
3
Analisis Algoritma |
4
1
1/4/2016
Instance Simplification
Instance Simplification • Computing the mode • Checking if all elements are distinct (element uniqueness) • Finding repeated elements
Presorting. • Presorting merupakan metode pengurutan (sorting) yang dilakukan sebelum waktu aktualnya (ahead of time) untuk mengefisiensikan penyelesaian kasus.
• Contoh kasus 1: Searching with presorting. Problem: Tentukan banyaknya tahapan yang harus dilalui untuk dapat menentukan lokasi elemen dengan nilai terkecil pada deret berikut.
• Beberapa permasalahan yang terkait dengan list akan lebih mudah jika list dalam keadaan terurut:
18 34 26 9 75 10
• Searching • Computing the median
Analisis Algoritma |
5
Analisis Algoritma |
Instance Simplification • Contoh kasus 2: Element uniqueness with presorting.
6
Instance Simplification Latihan 1. Kasus: Finding repeated elements
Problem: Tentukan banyaknya tahapan yang harus dilalui untuk dapat menentukan elemen yang sama yang saling berpasangan deret di bawah ini.
Problem 1: Tentukan prosedur untuk menemukan elemen dengan kemunculan terbanyak pada deret berikut menggunakan metode presorting.
18 34 12 9 24 12 40 20
34 18 34 9 26 9 75 34
Analisis Algoritma |
7
Analisis Algoritma |
8
2
1/4/2016
Representation Change
Representation Change
Binary Search Tree.
Heapsort.
• Binary search tree merupakan salah satu metode pencarian elemen yang mengakomodir teknik representation change.
• Heaps merupakan sebuah binary tree dimana nilai elemen root lebih besar dari elemen child
• Mengubah representasi (tampilan) kasus menjadi bentuk lainnya untuk memudahkan pencarian. • Contoh kasus: Binary search tree. Problem: Temukan element 35 pada deret bilangan berikut menggunakan binary search tree.
18 62 12 9 24 35 40 20 Analisis Algoritma |
• Heapsort adalah teknik pengurutan elemen bilangan yang mengadopsi heaps.
9
Analisis Algoritma |
Representation Change • Contoh kasus: Heapsort.
10
Problem Reduction • Problem Reduction: sebuah teknik yang digunakan dalam menemukan suatu solusi dengan cara mereduksi problem ke problem lainnya yang telah diketahui solusi untuk penyelesaiannya.
Problem: Urutkan deret bilangan berikut menggunakan heapsort.
18 62 12 9 24 35 2 Latihan 2. Kasus: Heapsort. Problem 1: Urutkan deret bilangan berikut menggunakan heapsort.
• Beberapa algoritma yang didasari oleh strategi ini adalah:
4 18 31 25 26 9 75 40
• Computing the Least Common Multiple • Counting Path in a Graph Analisis Algoritma |
11
Analisis Algoritma |
12
3
1/4/2016
Problem Reduction
Problem Reduction Penyelesaian.
Computing the Least Common Multiple. • Least Common Multiple (LCM): sebuah metode perkalian untuk menentukan bilangan bulat (integer) terkecil yang memungkinkan untuk setiap nilai 𝒎 dan 𝒏. • Contoh kasus: Least Common Multiple.
lcm(24, 60) = (2 . 2 . 3) . 2 . 5 = 120 2). lcm(10, 5) 10 = 2 . 5 = 10 5=5 lcm(10, 5) = (2 . 5) . 5 = 50
Problem: Tentukan lcm(24, 60) dan lcm(10, 5).
• Contoh kasus di atas dapat diselesaikan dengan perkalian sederhana antara bilangan faktorisasi prima 𝒎 dan 𝒏. Analisis Algoritma |
1). lcm(24, 60) 24 = 2 . 2 . 2 . 3 = 24 60 = 2 . 2 . 2 . 3 . 5 = 60
13
Analisis Algoritma |
Problem Reduction Latihan 3. Kasus: Least Common Multiple.
14
Problem Reduction Counting Path in Graph. • Menentukan banyaknya jalur/path dalam sebuah graph (directed atau undirected).
Problem 1: Tentukan lcm(280, 630)!
• Problem ini dapat diselesaikan dengan memperhatikan nilai eksponen yang mewakili notasi setiap adjacency matrix.
Problem 2: Tentukan lcm untuk nilai 𝒎 dan 𝒏, jika nilai 𝒎 dan 𝒏 pada problem 1 direduksi menjadi 1/3 bagian!
• Contoh kasus: Counting path in a graph. Problem: Tentukan banyaknya jalur yang memungkinkan dari graph ini.
Analisis Algoritma |
15
Analisis Algoritma |
16
4
1/4/2016
Problem Reduction
Problem Reduction Latihan 4.
Penyelesaian. 1). lcm(24, 60) 24 = 2 . 2 . 2 . 3 = 24
Kasus: Counting path in a graph. Problem: Tentukan banyaknya jalur yang memungkinkan dari graph yang ditunjukkan oleh adjacency metrics berikut.
Penyelesaian. Untuk graph A terdapat 3 jalur (path) dengan jarak 2 yang menghubungkan antara simpul a dan kembali lagi ke a, yaitu a – b – a, a – d – a, dan a – c – a, sedangkan untuk graph A2, terdapat hanya 1 path dengan jarak 2, yaitu a – d – c. Analisis Algoritma |
17
Analisis Algoritma |
18
Analisis Algoritma: Anany Levitin, Introduction to Design and Analysis of Algorithm, 3rd Edition, Pearson Education, Inc., Addison-Wesley
1-19
5
