11/3/2016
Bab 4: Decrease-and-Conquer
Analisis Algoritma:
Agenda.
Anany Levitin, Introduction to Design and Analysis of Algorithm, 3rd Edition, Pearson Education, Inc., Addison-Wesley
• • • •
Definition Three Major Varian of Decrease-and-Conquer Insertion Sort Topological Sort
Fakultas Teknologi dan Desain 1-1 Informatika Program Studi Teknik
Analisis Algoritma |
Definition
2
Three Major Varian of Decrease-and-Conquer
• Decrease-and-conquer, sebuah teknik yang berdasar pada relasi antara solusi untuk suatu kasus dan solusi untuk bagian yang lebih kecil dari kasus tersebut.
Decrease by Constant Variation.
• Pendekatan yang digunakan: top-down-approach atau bottom-upapproach (incremental approach)
• Pada umumnya nilai konstantanya adalah 1.
• Ukuran kasus diperkecil (reduce) dengan nilai konstanta yang sama pada setiap iterasi sebuah algoritma.
• 3 bentuk variasi dari teknik decrease-and-conquer: 1. decrease by constant; 2. decrease by constant factor; 3. variable size decrease
• Contoh kasus: Decrease by constant. 89 12 57 8 16 25 11 Problem: Urutkan deret bilangan acak di atas menggunakan metode selection sort yang mengakomodir decrease-by-constant!
Analisis Algoritma |
3
Analisis Algoritma |
4
1
11/3/2016
Three Major Varian of Decrease-and-Conquer Latihan 1.
Three Major Varian of Decrease-and-Conquer Insertion Sort.
Kasus: Decrease by constant.
• Insertion sort menggunakan metode deacrese-by-constant untuk melakukan proses pengurutan suatu deret. • Contoh kasus: Insertion sort.
U – N – I –V – E – R – S – I –T–A– S Problem 1: Tunjukkan penerapan decrease-by-constant untuk mengurutkan alphabet acak di atas menggunakan metode selection sort!
Analisis Algoritma |
Problem: Tentukan prosedur pengurutan deret secara ascending menggunakan metode sorting insertion sort!
5
Insertion Sort Latihan 2. Kasus: Insertion Sort Problem: Urutkan deret bilangan di bawah ini menggunakan metode sorting insertion sort!
Analisis Algoritma |
6
Three Major Varian of Decrease-and-Conquer Decrease by a Constant Factor Variation. • Ukuran kasus diperkecil (reduce) dengan nilai faktor konstanta yang sama pada setiap iterasi sebuah algoritma. • Pada umumnya nilai faktor konstantanya adalah 2.
89 12 57 16 25 11 75
• Beberapa algoritma variasi decrese-and-conquer ini adalah: • binary search; dan • russian peasant multification.
Analisis Algoritma |
7
Analisis Algoritma |
8
2
11/3/2016
Three Major Varian of Decrease-and-Conquer
Analisis Algoritma:
Decrease by a Constant Factor Variation.
Anany Levitin, Introduction to Design and Analysis of Algorithm, 3rd Edition, Pearson Education, Inc., Addison-Wesley
Binary Search. • Binary search adalah sebuah algoritma yang digunakan untuk mencari nilai tertentu, baik pada suatu deret bilangan yang acak atau telah terurut. • Contoh kasus: Prosedur pencarian bilangan sembarang tertentu. Problem: Tentukan prosedur untuk melakukan pencarian suatu bilangan pada suatu deret terurut tertentu.
Analisis Algoritma |
9
Three Major Varian of Decrease-and-Conquer Latihan 3.
Fakultas Teknologi dan Desain 1-10 Informatika Program Studi Teknik
Three Major Varian of Decrease-and-Conquer Russian Peasant Multiplication.
Kasus: Pencarian bilangan tertentu sembarang.
12 20 34 41 80 89 100 Problem 1: Tentukan pseudocode untuk melakukan pencarian bilangan 80 pada deret terurut diatas.
• Russian peasant multiplication adalah algoritma yang digunakan untuk mencari hasil perkalian 2 buah bilangan bulat positif, baik bilangan positif genap maupun ganjil. • Terdapat 2 formula yang digunakan dalam algoritma ini berdasarkan jenis bilangan 𝒏: • Jika 𝒏 merupakan bilangan genap
Analisis Algoritma |
11
Analisis Algoritma |
12
3
11/3/2016
Three Major Varian of Decrease-and-Conquer
Three Major Varian of Decrease-and-Conquer
• Jika 𝒏 merupakan bilangan ganjil
• Contoh kasus: Russian peasant multiplication.
50 * 65 Problem: Selesaikan operasi perkalian diatas menggunakan algoritma russian peasant multiplication.
Analisis Algoritma |
13
Three Major Varian of Decrease-and-Conquer
Analisis Algoritma |
Topological Sorting
• Ukuran kasus berkurang (size-reduction) dari operasi algoritma sebelumnya.
• Topological sorting (toposort): “merupakan suatu urutan linear setiap simpul dimana setiap 𝒖𝒗 yang saling terhubung secara langsung (direct), simpul 𝒖 muncul sebelum simpul 𝒗 dalam suatu urutan.”
• Algoritma yang menggunakan varian decrese-and-conquer ini adalah Euclid’s algorithm. 𝒈𝒄𝒅(𝒎, 𝒏) = 𝒈𝒄𝒅(𝒏, 𝒎 𝒎𝒐𝒅 𝒏)
• Topological sorting menerapkan algoritma traversal yang diterapkan pada metode searching DFS (depth first search) dan disajikan dalam bentuk digraph/direct graph.
Variable Size Deacrease Variation.
14
• Untuk merepresantiskan digraph, maka digunakan adjacency matrix dan adjacency list. Analisis Algoritma |
15
Analisis Algoritma |
16
4
11/3/2016
Topological Sorting • Adjacency matrix, menggambarkan hubungan antar simpul dalam bentuk matriks.
Topological Sorting • Gambar digraph disamping dapat diuraikan menjadi:
Contoh digraph.
• • • •
• Adjacency list, menggambarkan hubungan antar simpul yang diwakili oleh edge. • Adjacency matrix dan adjacency list merupakan dasar dari algoritma DFS untuk digraph.
tree edges (ab, bc, de) back edges (ba) forward edges (ac) cross edges (dc)
• Penerapan algoritma DFS untuk graph pada umumnya dalam bentuk stack penelusuran dan pohon DFS. Analisis Algoritma |
17
Analisis Algoritma |
Topological Sorting • Contoh kasus: DFS algorithm d
c
Topological Sorting Latihan 4. Problem: Tentukan pohon DFS, adjacency matrix dan adjacency list 2 buah graph di bawah ini!
f
f
b
a
18
b
c
a
g
e
c d
Problem 1: Tentukan adjacency matrix, adjacency list dan stack penelusuran graph di atas!
a
(a) Analisis Algoritma |
19
e
b d
e
f
g
(b) Analisis Algoritma |
20
5
11/3/2016
Topological Sorting
Topological Sorting • Pada digraph, algoritma DFS digunakan untuk menentukan stack penelusuran (traversal stack) untuk menentukan popping-order.
Problem 2: Terapkan algoritma DFS pada graph di bawah ini untuk menentukan stack penelusuran dan pohon DFS!
• Popping-order digunakan untuk menentukan topological sorting yang dihasilkan. f
d
a
c
b
d
• Contoh kasus: Topology sorting & source-removel algorithm Problem: Tentukan topology sorted list digraph di samping!
e Analisis Algoritma |
21
Analisis Algoritma |
Topological Sorting • Contoh kasus: Topology sorting & source-removel algorithm
22
Topological Sorting Latihan 4.
Problem 1: Tentukan topology sorted list digraph di samping! 1). DFS 2). popping-off order
Problem 1: Tentukan topology sorted list digraph dan urutkan simpulsimpul berikut berdasarkan source-removel algorithm!
Problem 2: Dengan menerapkan algoritma source-removel algorithm, urutkan simpul-simpul tersebut!
Analisis Algoritma |
23
Analisis Algoritma |
24
6
11/3/2016
Analisis Algoritma: Anany Levitin, Introduction to Design and Analysis of Algorithm, 3rd Edition, Pearson Education, Inc., Addison-Wesley
1-25
7
