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

T(n) = 7T(n/2) + Ө (n^2) n^log_b⁡a =n^log_2⁡7 = n^2.81 => T(n) ∈ Ө (n^log7) 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 n ≥ 32

pdf21 trang | Chia sẻ: thucuc2301 | Lượt xem: 937 | Lượt tải: 0download
Bạn đang xem trước 20 trang tài liệu 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, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
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

Các file đính kèm theo tài liệu này:

  • pdfthiet_ke_danh_gia_thuat_toanbaigiang04_chiadetri_3617_2032091.pdf