design and analysis algorithm pertemuan 08 · penyelesaian: t(n) = cn + t(n ... dalam menjawab soal...
Embed Size (px)
TRANSCRIPT
Design and Analysis Algorithm
Ahmad Afif Supianto, S.Si., M.Kom
Pertemuan 08
Contents
Insertion and Selection Sort 2
Decrease and Conguer 3 1
DFS and BFS 3 3
Binary Search Tree 4
2
Decrease and conquer
1. Mengurangi permasalahan menjadi lebih kecil
pada permasalahan yang sama
2. Selesaikan permasalahan yang lebih kecil
tersebut
3. Kembangkan permasalahan yang lebih kecil
itu sehingga menyelesaikan permasalahan
sebenarnya
4. Dapat dilakukan dengan dengan metode top
down atau bottom up
3
Variasi decrease and conquer
Decrease by a constant (Mengurangi secara
konstan atau tetap)
The size of a problem instance is reduced by
the same constant factor (usually two) on each
iteration of the algorithm (dikurangi secara
faktar konstan yang sama)
A size reduction pattern varies from one
iteration to another (Ukuran pengurangan
bervariasi dari satu iterasi ke iterasi lainnya).
4
Decrease by a constant (usually by 1):
insertion sort graph traversal algorithms (DFS and BFS) topological sorting algorithms for generating permutations, subsets
Decrease by a constant factor (usually by half)
binary search and bisection method exponentiation by squaring multiplication à la russe
Variable-size decrease
Euclid’s algorithm selection by partition Nim-like games
Biasanya menggunakan algoritma rekursif.
5
Permasalahan eksponensial: Hitung xn
Brute Force:
Divide and conquer:
Decrease by one:
Decrease by
constant factor:
n-1 multiplications
T(n) = 2*T(n/2) + 1
= n-1
T(n) = T(n-1) + 1 = n-1
T(n) = T(n/a) + a-1
= (a-1) n
= when a = 2
logan2log
6
Insertion sort
To sort array A[0..n-1], sort A[0..n-2] recursively and then insert A[n-1] in its proper place among the sorted A[0..n-2]
Usually implemented bottom up (non-recursively)
Example: Sort 6, 4, 1, 8, 5 6 | 4 1 8 5
4 6 | 1 8 5 1 4 6 | 8 5 1 4 6 8 | 5 1 4 5 6 8
7
Pseudo code Insertion sort
8
9
10
Kompleksitas waktu algoritma Insertion Sort:
Penyelesaian:
T(n) = cn + T(n – 1)
= cn + { c ⋅ (n – 1) + T(n – 2) }
= cn + c(n – 1) + { c ⋅ (n – 2) + T(n – 3) }
= cn + c ⋅ (n – 1) + c ⋅ (n – 2) + {c(n – 3) + T(n – 4) }
= ...
= cn+c⋅(n–1)+c(n–2)+c(n–3)+...+c2+T(1)
= c{ n + (n – 1) + (n – 2) + (n – 3) + ... + 2 } + a
= c{ (n – 1)(n + 2)/2 } + a
= cn2/2+cn/2 +(a–c)
= O(n2)
11
Selection sort
12
13
• Misalkan tabel A berisi elemen-elemen berikut:
• Langkah-langkah pengurutan dengan Selection Sort:
14
Kompleksitas waktu algoritma:
Penyelesaian (seperti pada Insertion Sort):
15
Depth-First Search (DFS)
Mengunjungi vertex-vertex pada grafik dengan selalu bergerak dari vertex yang terakhir dikunjungi ke vertex yang belum dikunjungi, lakukan backtrack apabila tidak ada vertex tetangga yang belum dikunjungi.
Rekursif atau menggunakan stack Vertex di-push ke stack ketika dicapai untuk pertama
kalinya
Sebuah vertex di-pop off atau dilepas dari stack ketika vertex tersebut merupakan vertex akhir (ketika tidak ada vertex tetangga yang belum dikunjungi)
“Redraws” atau gambar ulang grafik dalam bentuk seperti pohon (dengan edges pohon dan back edges untuk grafik tak berarah/undirected graph)
16
Pseudo code DFS
17
Example: DFS traversal of undirected graph
a b
e f
c d
g h
DFS traversal stack: DFS tree:
a b
e f
c d
g h
a ab abf abfe abf ab abg abgc abgcd abgcdh abgcd …
Red edges are tree edges and black edges are back edges.
1 2
5 4
6
3
7
8
18
Notes on DFS
Time complexity of DFS is O(|V|). Why?
each edge (u, v) is explored exactly once,
All steps are constant time.
19
Breadth-first search (BFS)
Mengunjungi vertex-vertex grafik dengan berpindah ke
semua vertex tetangga dari vertex yang terakhir
dikunjungi
BFS menggunakan queue
Mirip dengan level ke level dari pohon merentang
“Redraws” atau gambar ulang grafik dalam bentuk
seperti pohon (dengan edges pohon dan back edges
untuk grafik tak berarah/undirected graph)
20
Example of BFS traversal of undirected
graph
BFS traversal queue:
a b
e f
c d
g h
BFS tree:
a b
e f
c d
g h
a bef efg fg g ch hd d
Red edges are tree edges and black edges are cross edges.
1
3
2 6
4 7 5
8
21
Pseudo code BFS
22
Notes on BFS
Asumsi: setiap simpul dapat membangkitkan b buah
simpul baru.
Misalkan solusi ditemukan pada aras ke-d
Jumlah maksimum seluruh simpul:
1+b+b2 +b3 +...+bd =(bd+1 –1)/(b–1)
T(n) = O(bd)
Kompleksitas ruang algoritma BFS = sama dengan
kompleksitas waktunya, karena semua simpul daun dari
pohon harus disimpan di dalam memori selama proses
pencarian.
23
Breadth First Search (grafik berarah)
s
2
5
4
7
8
3 6 9
24
Breadth First Search
s
2
5
4
7
8
3 6 9
0
Undiscovered
Discovered
Finished
Queue: s
Top of queue
2
1 Shortest path
from s
25
Breadth First Search
s
2
5
4
7
8
3 6 9
0
Queue: s 2
3
1
1
Undiscovered
Discovered
Finished
Top of queue
26
Breadth First Search
s
2
5
4
7
8
3 6 9
0
Queue: s 2 3
5
1
1
1
Undiscovered
Discovered
Finished
Top of queue
27
Breadth First Search
s 5 7
8
3 6 9
0
Queue: s 2 3 5
1
1
1
Undiscovered
Discovered
Finished
Top of queue
4 2
28
Breadth First Search
s
2
5
4
7
8
3 6 9
0
Queue: 2 3 5
4
1
1
1
2
Undiscovered
Discovered
Finished
Top of queue
29
Breadth First Search
s
2
5
4
7
8
3 6 9
0
Queue: 2 3 5 4
1
1
1
2
5 already discovered:
don't enqueue
Undiscovered
Discovered
Finished
Top of queue
30
Breadth First Search
s
2
5
4
7
8
3 6 9
0
Queue: 2 3 5 4
1
1
1
2
Undiscovered
Discovered
Finished
Top of queue
31
Breadth First Search
s
2
5
4
7
8
3 6 9
0
Queue: 3 5 4
1
1
1
2
Undiscovered
Discovered
Finished
Top of queue
32
Breadth First Search
s
2
5
4
7
8
3 6 9
0
Queue: 3 5 4
1
1
1
2
6
2
Undiscovered
Discovered
Finished
Top of queue
33
Breadth First Search
s
2
5
4
7
8
3 6 9
0
Queue: 3 5 4 6
1
1
1
2
2
Undiscovered
Discovered
Finished
Top of queue
34
Breadth First Search
s
2
5
4
7
8
3 6 9
0
Queue: 5 4 6
1
1
1
2
2
Undiscovered
Discovered
Finished
Top of queue
35
Breadth First Search
s
2
5
4
7
8
3 6 9
0
Queue: 5 4 6
1
1
1
2
2
Undiscovered
Discovered
Finished
Top of queue
36
Breadth First Search
s
2
5
4
7
8
3 6 9
0
Queue: 4 6
1
1
1
2
2
Undiscovered
Discovered
Finished
Top of queue
37
Breadth First Search
s
2
5
4
7
8
3 6 9
0
Queue: 4 6
1
1
1
2
2
8
3
Undiscovered
Discovered
Finished
Top of queue
38
Breadth First Search
s
2
5
4
7
8
3 6 9
0
Queue: 4 6 8
1
1
1
2
2
3
Undiscovered
Discovered
Finished
Top of queue
39
Breadth First Search
s
2
5
4
7
8
3 6 9
0
Queue: 6 8
1
1
1
2
2
3
7
3
Undiscovered
Discovered
Finished
Top of queue
40
Breadth First Search
s
2
5
4
7
8
3 6 9
0
Queue: 6 8 7
1
1
1
2
2
3
9
3
3
Undiscovered
Discovered
Finished
Top of queue
41
Breadth First Search
s
2
5
4
7
8
3 6 9
0
Queue: 6 8 7 9
1
1
1
2
2
3
3
3
Undiscovered
Discovered
Finished
Top of queue
42
Breadth First Search
s
2
5
4
7
8
3 6 9
0
Queue: 8 7 9
1
1
1
2
2
3
3
3
Undiscovered
Discovered
Finished
Top of queue
43
Breadth First Search
s
2
5
4
7
8
3 6 9
0
Queue: 7 9
1
1
1
2
2
3
3
3
Undiscovered
Discovered
Finished
Top of queue
44
Breadth First Search
s
2
5
4
7
8
3 6 9
0
Queue: 7 9
1
1
1
2
2
3
3
3
Undiscovered
Discovered
Finished
Top of queue
45
Breadth First Search
s
2
5
4
7
8
3 6 9
0
Queue: 7 9
1
1
1
2
2
3
3
3
Undiscovered
Discovered
Finished
Top of queue
46
Breadth First Search
s
2
5
4
7
8
3 6 9
0
Queue: 7 9
1
1
1
2
2
3
3
3
Undiscovered
Discovered
Finished
Top of queue
47
Breadth First Search
s
2
5
4
7
8
3 6 9
0
Queue: 9
1
1
1
2
2
3
3
3
Undiscovered
Discovered
Finished
Top of queue
48
Breadth First Search
s
2
5
4
7
8
3 6 9
0
Queue: 9
1
1
1
2
2
3
3
3
Undiscovered
Discovered
Finished
Top of queue
49
Breadth First Search
s
2
5
4
7
8
3 6 9
0
Queue: 9
1
1
1
2
2
3
3
3
Undiscovered
Discovered
Finished
Top of queue
50
Breadth First Search
s
2
5
4
7
8
3 6 9
0
Queue:
1
1
1
2
2
3
3
3
Undiscovered
Discovered
Finished
Top of queue
51
Breadth First Search
s
2
5
4
7
8
3 6 9
0
Level Graph
1
1
1
2
2
3
3
3
52
Latihan: Gunakan algoritma BFS dan DFS untuk
menemukan pohon merentang (spanning tree) dari graf
G di bawah ini jika traversalnya dimulai dari simpul e.
Dalam menjawab soal ini, perlihatkan traversal
BFS/DFS sebagai pohon berakar dengan e sebagai
akarnya.
53
Binary Search Tree
Several algorithms on BST
requires recursive processing of
just one of its subtrees, e.g.,
Searching
Insertion of a new key
Finding the smallest (or the
largest) key
k
<k >k
54
Binary Search Tree
A binary search tree Not a binary search tree
55
56
Searching (Find)
Find X: return a pointer to the node that has key X, or
NULL if there is no such node
Time complexity: O(height of the tree)
BinaryNode * BinarySearchTree::Find(const float &x, BinaryNode *t) const
{
if (t == NULL)
return NULL;
else if (x < t->element)
return Find(x, t->left);
else if (t->element < x)
return Find(x, t->right);
else
return t; // match
}
57
Algorithm BST(x, v)
//Searches for node with key equal to v in BST rooted at node x
if x = NIL return -1
else if v = K(x) return x
else if v < K(x) return BST(left(x), v)
else return BST(right(x), v)
Efficiency
worst case: C(n) = n
average case: C(n) ≈ 2ln n ≈ 1.39log2 n, if the BST was built from n random keys and v is chosen randomly.
58
Aplikasi DFS dan BFS
Search Engine (google, yahoo, altavista).Komponen search engine: Web Spider : program penjelajah web (web surfer)
Index: basisdata yang menyimpan kata-kata penting pada setiap halaman web
Query: pencarian berdasarkan string yang dimasukkan oleh pengguna (end- user)
Secara periodik (setiap jam atau setiap hari), spider menjejalahi internet untuk mengunjungi halaman-halaman web, mengambil kata-kata penting di dalam web, dan menyimpannya di dalam index. Query dilakukan terhadap index, bukan terhadap website yang aktual.
59
60
61
Bagaimana spider menjelajahi (surfing) web?
Halaman web dimodelkan sebagai graf berarah
Simpul menyatakan halaman web (web page)
Sisi menyatakan link ke halaman web
Bagaimana teknik menjelajahi web? Secara
DFS atau BFS
Dimulai dari web page awal, lalu setiap link
ditelusuri secara DFS sampai setiap web page
tidak mengandung link.
Pada setiap halaman web, informasi di
dalamnya dianalisis dan disimpan di dalam
basisdata index. 62
Click to edit subtitle style