Top Banner
Design and Analysis Algorithm Ahmad Afif Supianto, S.Si., M.Kom Pertemuan 08
63

Design and Analysis Algorithm Pertemuan 08 · Penyelesaian: T(n) = cn + T(n ... Dalam menjawab soal ini, ... Halaman web dimodelkan sebagai graf berarah

Mar 19, 2019

Download

Documents

ngocong
Welcome message from author
This document is posted to help you gain knowledge. Please leave a comment to let me know what you think about it! Share it to your friends and learn new things together.
Transcript
Page 1: Design and Analysis Algorithm Pertemuan 08 · Penyelesaian: T(n) = cn + T(n ... Dalam menjawab soal ini, ... Halaman web dimodelkan sebagai graf berarah

Design and Analysis Algorithm

Ahmad Afif Supianto, S.Si., M.Kom

Pertemuan 08

Page 2: Design and Analysis Algorithm Pertemuan 08 · Penyelesaian: T(n) = cn + T(n ... Dalam menjawab soal ini, ... Halaman web dimodelkan sebagai graf berarah

Contents

Insertion and Selection Sort 2

Decrease and Conguer 3 1

DFS and BFS 3 3

Binary Search Tree 4

2

Page 3: Design and Analysis Algorithm Pertemuan 08 · Penyelesaian: T(n) = cn + T(n ... Dalam menjawab soal ini, ... Halaman web dimodelkan sebagai graf berarah

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

Page 4: Design and Analysis Algorithm Pertemuan 08 · Penyelesaian: T(n) = cn + T(n ... Dalam menjawab soal ini, ... Halaman web dimodelkan sebagai graf berarah

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

Page 5: Design and Analysis Algorithm Pertemuan 08 · Penyelesaian: T(n) = cn + T(n ... Dalam menjawab soal ini, ... Halaman web dimodelkan sebagai graf berarah

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

Page 6: Design and Analysis Algorithm Pertemuan 08 · Penyelesaian: T(n) = cn + T(n ... Dalam menjawab soal ini, ... Halaman web dimodelkan sebagai graf berarah

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

Page 7: Design and Analysis Algorithm Pertemuan 08 · Penyelesaian: T(n) = cn + T(n ... Dalam menjawab soal ini, ... Halaman web dimodelkan sebagai graf berarah

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

Page 8: Design and Analysis Algorithm Pertemuan 08 · Penyelesaian: T(n) = cn + T(n ... Dalam menjawab soal ini, ... Halaman web dimodelkan sebagai graf berarah

Pseudo code Insertion sort

8

Page 9: Design and Analysis Algorithm Pertemuan 08 · Penyelesaian: T(n) = cn + T(n ... Dalam menjawab soal ini, ... Halaman web dimodelkan sebagai graf berarah

9

Page 10: Design and Analysis Algorithm Pertemuan 08 · Penyelesaian: T(n) = cn + T(n ... Dalam menjawab soal ini, ... Halaman web dimodelkan sebagai graf berarah

10

Page 11: Design and Analysis Algorithm Pertemuan 08 · Penyelesaian: T(n) = cn + T(n ... Dalam menjawab soal ini, ... Halaman web dimodelkan sebagai graf berarah

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

Page 12: Design and Analysis Algorithm Pertemuan 08 · Penyelesaian: T(n) = cn + T(n ... Dalam menjawab soal ini, ... Halaman web dimodelkan sebagai graf berarah

Selection sort

12

Page 13: Design and Analysis Algorithm Pertemuan 08 · Penyelesaian: T(n) = cn + T(n ... Dalam menjawab soal ini, ... Halaman web dimodelkan sebagai graf berarah

13

Page 14: Design and Analysis Algorithm Pertemuan 08 · Penyelesaian: T(n) = cn + T(n ... Dalam menjawab soal ini, ... Halaman web dimodelkan sebagai graf berarah

• Misalkan tabel A berisi elemen-elemen berikut:

• Langkah-langkah pengurutan dengan Selection Sort:

14

Page 15: Design and Analysis Algorithm Pertemuan 08 · Penyelesaian: T(n) = cn + T(n ... Dalam menjawab soal ini, ... Halaman web dimodelkan sebagai graf berarah

Kompleksitas waktu algoritma:

Penyelesaian (seperti pada Insertion Sort):

15

Page 16: Design and Analysis Algorithm Pertemuan 08 · Penyelesaian: T(n) = cn + T(n ... Dalam menjawab soal ini, ... Halaman web dimodelkan sebagai graf berarah

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

Page 17: Design and Analysis Algorithm Pertemuan 08 · Penyelesaian: T(n) = cn + T(n ... Dalam menjawab soal ini, ... Halaman web dimodelkan sebagai graf berarah

Pseudo code DFS

17

Page 18: Design and Analysis Algorithm Pertemuan 08 · Penyelesaian: T(n) = cn + T(n ... Dalam menjawab soal ini, ... Halaman web dimodelkan sebagai graf berarah

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

Page 19: Design and Analysis Algorithm Pertemuan 08 · Penyelesaian: T(n) = cn + T(n ... Dalam menjawab soal ini, ... Halaman web dimodelkan sebagai graf berarah

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

Page 20: Design and Analysis Algorithm Pertemuan 08 · Penyelesaian: T(n) = cn + T(n ... Dalam menjawab soal ini, ... Halaman web dimodelkan sebagai graf berarah

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

Page 21: Design and Analysis Algorithm Pertemuan 08 · Penyelesaian: T(n) = cn + T(n ... Dalam menjawab soal ini, ... Halaman web dimodelkan sebagai graf berarah

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

Page 22: Design and Analysis Algorithm Pertemuan 08 · Penyelesaian: T(n) = cn + T(n ... Dalam menjawab soal ini, ... Halaman web dimodelkan sebagai graf berarah

Pseudo code BFS

22

Page 23: Design and Analysis Algorithm Pertemuan 08 · Penyelesaian: T(n) = cn + T(n ... Dalam menjawab soal ini, ... Halaman web dimodelkan sebagai graf berarah

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

Page 24: Design and Analysis Algorithm Pertemuan 08 · Penyelesaian: T(n) = cn + T(n ... Dalam menjawab soal ini, ... Halaman web dimodelkan sebagai graf berarah

Breadth First Search (grafik berarah)

s

2

5

4

7

8

3 6 9

24

Page 25: Design and Analysis Algorithm Pertemuan 08 · Penyelesaian: T(n) = cn + T(n ... Dalam menjawab soal ini, ... Halaman web dimodelkan sebagai graf berarah

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

Page 26: Design and Analysis Algorithm Pertemuan 08 · Penyelesaian: T(n) = cn + T(n ... Dalam menjawab soal ini, ... Halaman web dimodelkan sebagai graf berarah

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

Page 27: Design and Analysis Algorithm Pertemuan 08 · Penyelesaian: T(n) = cn + T(n ... Dalam menjawab soal ini, ... Halaman web dimodelkan sebagai graf berarah

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

Page 28: Design and Analysis Algorithm Pertemuan 08 · Penyelesaian: T(n) = cn + T(n ... Dalam menjawab soal ini, ... Halaman web dimodelkan sebagai graf berarah

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

Page 29: Design and Analysis Algorithm Pertemuan 08 · Penyelesaian: T(n) = cn + T(n ... Dalam menjawab soal ini, ... Halaman web dimodelkan sebagai graf berarah

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

Page 30: Design and Analysis Algorithm Pertemuan 08 · Penyelesaian: T(n) = cn + T(n ... Dalam menjawab soal ini, ... Halaman web dimodelkan sebagai graf berarah

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

Page 31: Design and Analysis Algorithm Pertemuan 08 · Penyelesaian: T(n) = cn + T(n ... Dalam menjawab soal ini, ... Halaman web dimodelkan sebagai graf berarah

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

Page 32: Design and Analysis Algorithm Pertemuan 08 · Penyelesaian: T(n) = cn + T(n ... Dalam menjawab soal ini, ... Halaman web dimodelkan sebagai graf berarah

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

Page 33: Design and Analysis Algorithm Pertemuan 08 · Penyelesaian: T(n) = cn + T(n ... Dalam menjawab soal ini, ... Halaman web dimodelkan sebagai graf berarah

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

Page 34: Design and Analysis Algorithm Pertemuan 08 · Penyelesaian: T(n) = cn + T(n ... Dalam menjawab soal ini, ... Halaman web dimodelkan sebagai graf berarah

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

Page 35: Design and Analysis Algorithm Pertemuan 08 · Penyelesaian: T(n) = cn + T(n ... Dalam menjawab soal ini, ... Halaman web dimodelkan sebagai graf berarah

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

Page 36: Design and Analysis Algorithm Pertemuan 08 · Penyelesaian: T(n) = cn + T(n ... Dalam menjawab soal ini, ... Halaman web dimodelkan sebagai graf berarah

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

Page 37: Design and Analysis Algorithm Pertemuan 08 · Penyelesaian: T(n) = cn + T(n ... Dalam menjawab soal ini, ... Halaman web dimodelkan sebagai graf berarah

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

Page 38: Design and Analysis Algorithm Pertemuan 08 · Penyelesaian: T(n) = cn + T(n ... Dalam menjawab soal ini, ... Halaman web dimodelkan sebagai graf berarah

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

Page 39: Design and Analysis Algorithm Pertemuan 08 · Penyelesaian: T(n) = cn + T(n ... Dalam menjawab soal ini, ... Halaman web dimodelkan sebagai graf berarah

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

Page 40: Design and Analysis Algorithm Pertemuan 08 · Penyelesaian: T(n) = cn + T(n ... Dalam menjawab soal ini, ... Halaman web dimodelkan sebagai graf berarah

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

Page 41: Design and Analysis Algorithm Pertemuan 08 · Penyelesaian: T(n) = cn + T(n ... Dalam menjawab soal ini, ... Halaman web dimodelkan sebagai graf berarah

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

Page 42: Design and Analysis Algorithm Pertemuan 08 · Penyelesaian: T(n) = cn + T(n ... Dalam menjawab soal ini, ... Halaman web dimodelkan sebagai graf berarah

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

Page 43: Design and Analysis Algorithm Pertemuan 08 · Penyelesaian: T(n) = cn + T(n ... Dalam menjawab soal ini, ... Halaman web dimodelkan sebagai graf berarah

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

Page 44: Design and Analysis Algorithm Pertemuan 08 · Penyelesaian: T(n) = cn + T(n ... Dalam menjawab soal ini, ... Halaman web dimodelkan sebagai graf berarah

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

Page 45: Design and Analysis Algorithm Pertemuan 08 · Penyelesaian: T(n) = cn + T(n ... Dalam menjawab soal ini, ... Halaman web dimodelkan sebagai graf berarah

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

Page 46: Design and Analysis Algorithm Pertemuan 08 · Penyelesaian: T(n) = cn + T(n ... Dalam menjawab soal ini, ... Halaman web dimodelkan sebagai graf berarah

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

Page 47: Design and Analysis Algorithm Pertemuan 08 · Penyelesaian: T(n) = cn + T(n ... Dalam menjawab soal ini, ... Halaman web dimodelkan sebagai graf berarah

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

Page 48: Design and Analysis Algorithm Pertemuan 08 · Penyelesaian: T(n) = cn + T(n ... Dalam menjawab soal ini, ... Halaman web dimodelkan sebagai graf berarah

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

Page 49: Design and Analysis Algorithm Pertemuan 08 · Penyelesaian: T(n) = cn + T(n ... Dalam menjawab soal ini, ... Halaman web dimodelkan sebagai graf berarah

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

Page 50: Design and Analysis Algorithm Pertemuan 08 · Penyelesaian: T(n) = cn + T(n ... Dalam menjawab soal ini, ... Halaman web dimodelkan sebagai graf berarah

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

Page 51: Design and Analysis Algorithm Pertemuan 08 · Penyelesaian: T(n) = cn + T(n ... Dalam menjawab soal ini, ... Halaman web dimodelkan sebagai graf berarah

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

Page 52: Design and Analysis Algorithm Pertemuan 08 · Penyelesaian: T(n) = cn + T(n ... Dalam menjawab soal ini, ... Halaman web dimodelkan sebagai graf berarah

Breadth First Search

s

2

5

4

7

8

3 6 9

0

Level Graph

1

1

1

2

2

3

3

3

52

Page 53: Design and Analysis Algorithm Pertemuan 08 · Penyelesaian: T(n) = cn + T(n ... Dalam menjawab soal ini, ... Halaman web dimodelkan sebagai graf berarah

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

Page 54: Design and Analysis Algorithm Pertemuan 08 · Penyelesaian: T(n) = cn + T(n ... Dalam menjawab soal ini, ... Halaman web dimodelkan sebagai graf berarah

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

Page 55: Design and Analysis Algorithm Pertemuan 08 · Penyelesaian: T(n) = cn + T(n ... Dalam menjawab soal ini, ... Halaman web dimodelkan sebagai graf berarah

Binary Search Tree

A binary search tree Not a binary search tree

55

Page 56: Design and Analysis Algorithm Pertemuan 08 · Penyelesaian: T(n) = cn + T(n ... Dalam menjawab soal ini, ... Halaman web dimodelkan sebagai graf berarah

56

Page 57: Design and Analysis Algorithm Pertemuan 08 · Penyelesaian: T(n) = cn + T(n ... Dalam menjawab soal ini, ... Halaman web dimodelkan sebagai graf berarah

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

Page 58: Design and Analysis Algorithm Pertemuan 08 · Penyelesaian: T(n) = cn + T(n ... Dalam menjawab soal ini, ... Halaman web dimodelkan sebagai graf berarah

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

Page 59: Design and Analysis Algorithm Pertemuan 08 · Penyelesaian: T(n) = cn + T(n ... Dalam menjawab soal ini, ... Halaman web dimodelkan sebagai graf berarah

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

Page 60: Design and Analysis Algorithm Pertemuan 08 · Penyelesaian: T(n) = cn + T(n ... Dalam menjawab soal ini, ... Halaman web dimodelkan sebagai graf berarah

60

Page 61: Design and Analysis Algorithm Pertemuan 08 · Penyelesaian: T(n) = cn + T(n ... Dalam menjawab soal ini, ... Halaman web dimodelkan sebagai graf berarah

61

Page 62: Design and Analysis Algorithm Pertemuan 08 · Penyelesaian: T(n) = cn + T(n ... Dalam menjawab soal ini, ... Halaman web dimodelkan sebagai graf berarah

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

Page 63: Design and Analysis Algorithm Pertemuan 08 · Penyelesaian: T(n) = cn + T(n ... Dalam menjawab soal ini, ... Halaman web dimodelkan sebagai graf berarah

Click to edit subtitle style