Giáo trình Thiết kế & Đánh giá thuật toán - Bài giảng 4: 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