Bài giảng Thiết kế và đánh giá thuật toán - Chia đẻ trị - Lê Nguyên Khôi

Thiết Kế & Đánh Giá Thuật Toán
Chia Để Trị
TS. Lê Nguyên Khôi
Trường Đại Học Công Nghệ - ĐHQGHN
Nội Dung

 Kỹ thuật thiết kế

 Sắp xếp gộp

 Tính lũy thừa

 Tìm kiếm nhị phân

 Tính số Fibonacci

 Tháp Hanoi

 Nhân ma trận

 Thuật toán Strassen
1
Kỹ Thuật Thiết Kế Chia Để Trị

 Chia bài toán lớn thành các bài toán nhỏ

 Bài toán nhỏ đơn giản, giải trực tiếp

 Nếu không tiếp tục chia nhỏ bài toán con

 Gộp lời giải của các bài toán con
2
Sắp Xếp Gộp (Merge Sort)

 Chia: chia đôi mảng

 Trị: Sử dụng đệ quy sắp xếp 2 mảng con

 Gộp: gộp 2 mảng với thời gian tuyến tính
MergeSort (, 1, )
1 if  = 1 return
2 MergeSort (, 1, /2 )
3 MergeSort (, /2 + 1, )
4 Merge (, 1, /2 , /2 + 1, )
() 	= 	2(/2) 	+ 	Θ()
3
độ lớn bài toán con# bài toán con
chia và gộp
Định Lý Tổng Quát – (nhắc lại)
  =  / + ()
1. Nếu   ∈ ( ) với hằng số  > 0
  ∈ ( )
2. Nếu   ∈ ( )
  ∈ (  log )
3. Nếu   ∈ "( #) với hằng số  > 0
và   thỏa mãn  / ≤ %() với % < 1
  ∈ (())
Sắp xếp gộp:  = 2,  = 2 ⇒   = ( ) = 
⇒ trường hợp 2 ⇒ () ∈ ( log )
4
Tính Lũy Thừa
Tính *, với  ∈ ℕ
Thuật toán đơn giản: ()
Thuật toán áp dụng chia để trị:
* = ,	*/)× */)	  chẵn(*0)/) × (*0)/) ×  	 lẻ
() 	= (/2) 	+ 	(1) ⇒ () ∈ (log )
5
Tính Lũy Thừa
Thuật toán áp dụng chia để trị:
* = ,	*/)× */)	  chẵn(*0)/) × (*0)/) ×  	 lẻ
PowerN(, )
1 if  = 0 return 1
2 if 	%	2 = 0
3 return PowerN , *) ×PowerN(,
*
))
4 else
5 return PowerN(, *0) ) ×PowerN(,
*0
) ) × 
() 	= 2(/2) 	+ 	(1) ⇒ () ∈ () ⇒ SAI !!!!
6
Tính Lũy Thừa
Thuật toán áp dụng chia để trị:
* = ,	*/)× */)	  chẵn(*0)/) × (*0)/) ×  	 lẻ
PowerN(, )
1 if  = 0 return 1
2 if 	%	2 = 0
3 2 ← PowerN , *)
4 return 2 × 2
5 else
6 2 ← PowerN(, *0) )
7 return 2 × 2	 × 
() 	= (/2) 	+ 	(1) ⇒ () ∈ (log )
7
Tìm Kiếm Nhị Phân
Tìm một phần tử trong dãy đã sắp xếp

 Chia: Kiểm tra phần tử chính giữa

 Trị: Sử dụng đệ quy tìm kiếm trên 1 mảng
con tương ứng

 Gộp: hiển nhiên
Ví dụ: Tìm 9
3 5 7 8 9 12 15
8
Tìm Kiếm Nhị Phân – Phân Tích
() 	= 1(/2) 	+ 	(1)
Áp dụng Định Lý Tổng Quát
  = ( 0 = 4 = 1
⇒ trường hợp 2
⇒   ∈    log  = (log )
9
độ lớn bài toán con
# bài-toán-con chia và gộp
Tính Số Fibonacci
5* = ,		=	0,15*0+5*)		 ≥ 2
0 1 1 2 3 5 8 13 21 
Thuật toán đệ quy: 7(8*) (thời gian hàm mũ), 
với 8 = (1 + 5)/2 – golden ratio
10
Tính Số Fibonacci
Thiết kế Bottom-up: 

 Tính lần lượt 54, 50, 5), , 5* theo thứ tự, số
sau bằng tổng hai số trước

 Thời gian chạy: ()
5* = 8*/ 5 làm tròn

 Tính lũy thừa: (log )

 Tuy nhiên cách này không đáng tin cậy, do dễ có lỗi
làm tròn khi tính toán với số thực.
11
Tháp Hanoi

 Chuyển chồng đĩa từ A sang B sử dụng C 
trung gian. Đĩa to luôn ở dưới đĩa nhỏ
move(, , ;, <)
1 if  = 1
2 chuyển đĩa A sang B
3 else
4 move( = 1, , <, ;)
5 chuyển đĩa A sang B
6 move( = 1, <, ;, )
() 	= 2( = 1)	
 	(1)
12
Nhân Ma Trận

 Input:  = >? , ; = >?

 Output: ? =  ∙ ;
với A, B = 	1, 2,  ,  và
%>? = C>D ∙ D?
*
DE0
13
Nhân Ma Trận – Mã Giả
for A ← 1 to  do
for B ← 1 to  do
%>? ← 0
for F ← 1 to  do
%>? ← %>? + >D ∙ D?
Thời gian chạy (G)
14
Nhân Ma Trận – Chia-Để-Trị
Ý tưởng:
 ×  MT = 2 × 2 MT của (/2) × (/2) MT-con
H I
J K =
 
% L ∙
M 
N ℎ
< =  ∙ ;
H = M + N
I =  + ℎ 8 nhân (*)) × (
*
)) MT-con
J = %M + LN 4 cộng (*)) × (
*
)) MT-con
K = % + Lℎ
15
Nhân Ma Trận – Phân Tích
() 	= 8(/2) 	+ 	())
  = ( Q = G
⇒ trường hợp 1
⇒ () ∈ (G)
Không tốt hơn !!!
16
độ lớn bài toán con
# bài-toán-con chia và gộp
Nhân Ma Trận – Thuật Toán Strassen

 Nhân 2 × 2 ma trận với 7 phép nhân
R0 =  · (– ℎ) H = RU + RV–R) + RW
R) = ( + ) · ℎ I = R0 + R)
RG = (% + L) · M J = RG + RV
RV = L · (N– M) K = RU + R0–RG–RX
RU = ( + L) · (M + ℎ)
RW = (–L) · (N + ℎ)
RX = (– %) · (M + 	)
17
7 nhân, 18 cộng/trừ.
Nhân Ma Trận – Thuật Toán Strassen

 Chia: Chia  và ; thành (/2) × (/2)
ma trận con.

 Trị: Thực hiên đệ quy 7 phép nhân
(/2) × (/2) ma trận

 Gộp: Tạo ma trận < sử dụng + và – trên 
(/2) × (/2) ma trận con
() 	= 7(/2) 	+ 	())
18
Thuật Toán Strassen – Phân Tích
() 	= 7(/2) 	+ 	())
  = ( X = ).Q0 ⇒ () ∈ ( X)
log 7 = 2.81 trông không nhỏ hơn 3 là mấy.
Tuy nhiên, nên nhớ sự khác biệt là số mũ.
Do đó thời gian chạy sẽ bị ảnh hưởng rất nhiều.
Trên thực thế, thuật toán Strassen’s tốt hơn
thuật toán nhân ma trận thông thường với
 ≥ 32
19
Tổng Kết

 Chia để trị chỉ là một trong những
phương pháp thiết kế thuật toán.

 Thuật toán chia để trị có thể được phân
tích dựa trên quy nạp và phương pháp
định lý tổng quát.

 Thông thường phương pháp chia để trị
khá hiệu quả.
20