›

Bài giảng Thiết Kế & Đánh Giá Thuật Toán - Chia để trị - Lê Nguyên Khôi

pdf 21 trang huongle 7540
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Thiết Kế & Đánh Giá Thuật Toán - Chia để trị - Lê Nguyên Khôi", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfbai_giang_thiet_ke_danh_gia_thuat_toan_chia_de_tri_le_nguyen.pdf

Nội dung text: Bài giảng Thiết Kế & Đánh Giá Thuật Toán - Chia để trị - Lê Nguyên Khôi

  1. ế ế ậ aể ị ườ ạ ọ ệ
  2. ộ  K thu t thi t k  Sp xp gp  Tính ly th a  Tìm kim nh phân  Tính s Fibonacci  Tháp Hanoi  Nhân ma tr n  Thu t toán Strassen 1
  3. ỹ ậ ế ế aể ị  Chia bài toán ln thành các bài toán nh  Bài toán nh ơ n gi n, gi i tr c ti p  Nu không ti p tc chia nh bài toán con  Gp li gi i ca các bài toán con 2
  4. ắ ế ộ ee  Chia: chia ôi mng  Tr : S dng quy sp xp 2 mng con  Gp: gp 2 mng vi th i gian tuy n tính MergeSort (, 1, ) 1 if return = 1 2 MergeSort (, 1, /2 ) 3 MergeSort (, /2 + 1, ) 4 Merge (, 1, /2 , /2 + 1, ) ()= 2(/2)+ Θ() chia và gp # bài toán con ln bài toán con 3
  5. ị ổ ắ ạ = / + () 1. Nu ∈ ( ) vi hng s > 0 ∈ ( ) 2. Nu ∈ ( ) ∈ ( log ) 3. Nu ∈ ( ) vi hng s > 0 và th a mãn / ≤ () v i < 1 ∈ (()) Sp xp gp: = 2, = 2 ⇒ = = ⇒ tr ng hp 2 ⇒ () ∈ (log) 4
  6. ừa Tính , v i ∈ ℕ Thu t toán ơ n gi n: () Thu t toán áp dng chia tr : / / ch = × ẵn ()/ × ()/ × l ()= (/2)+(1) ⇒ () ∈ (log) 5
  7. ừa Thu t toán áp dng chia tr : / / ch = × ẵn ()/ × ()/ × l PowerN (, ) 1 if return 1 = 0 2 if %2 = 0 3 return PowerN PowerN , × (, ) 4 else 5 return PowerN PowerN (, ) × (, ) × SAI !!!! ()=2(/2)+(1) ⇒ ()∈() ⇒ 6
  8. ừa Thu t toán áp dng chia tr : / / ch = × ẵn ()/ × ()/ × l PowerN (, ) 1 if return 1 = 0 2 if %2 = 0 3 PowerN ← , 4 return × 5 else 6 PowerN ← (, ) 7 return × × ()= (/2)+(1) ⇒ () ∈ (log) 7
  9. ế ị Tìm mt ph n t trong dãy ã sp xp  Chia: Ki m tra ph n t chính gi a  Tr : S dng quy tìm ki m trên 1 mng con tơ ng ng  Gp: hi n nhiên Ví d: Tìm 9 3 5 7 8 9 12 15 8
  10. ế ị ()= 1(/2)+ (1) # bài-toán-con chia và gp ln bài toán con Áp dng nh Lý Tng Quát = = = 1 ⇒ tr ng hp 2 ⇒ ∈ log =(log) 9
  11. ố a =0,1 = + ≥ 2 0 1 1 2 3 5 8 13 21 Thu t toán quy: () (th i gian hàm m), vi = (1 + 5)/2 – golden ratio 10
  12. ố a Thi t k Bottom-up:  Tính ln l t , , , , theo th t, s sau bng tng hai s tr c  Th i gian ch y: () làm tròn = / 5  Tính ly th a: (log )  Tuy nhiên cách này không áng tin cy, do d có li làm tròn khi tính toán vi s th c. 11
  13. a  Chuy n ch ng a t A sang B s dng C trung gian. a to luôn d i a nh move ( ) 1 if = 2 chuy n a A sang B 3 else 4 move () 5 chuy n a A sang B 6 move () ()= ( )() 12
  14. a ậ  Input: , = =  Output: = = ∙ vi , =1,2, , và = ∙ 13
  15. a ậ ả for to do ← 1 for to do ← 1 ← 0 for to do ← 1 ← + ∙ Th i gian ch y () 14
  16. a ậ aể ị Ý t ng: × MT = 2 × 2 MT ca (/2) × (/2) MT-con = ∙ ℎ = ∙ = + 8 nhân MT-con = + ℎ () × () 4 cng MT-con = + () × () = + ℎ 15
  17. a ậ ()= 8(/2)+ () # bài-toán-con chia và gp ln bài toán con = = ⇒ tr ng hp 1 ⇒ () ∈ () Không tt hơn !!! 16
  18. a ậ ậ ae  Nhân 2 × 2 ma tr n vi 7 phép nhân =·(–ℎ) = + – + =(+)·ℎ = + =(+)· = + =·(–) = + – – =(+)·(+ℎ) =(–)·(+ℎ) 7 nhân, 18 cng/tr . = (–)·(+) 17
  19. a ậ ậ ae  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  Gp: To ma tr n s dng + và – trên (/2) × (/2) ma tr n con ()= (/2)+ () 18
  20. ậ ae () = 7(/2)+ () = = . ⇒ () ∈ ( ) log 7 = 2.81 trông không nh hơn 3 là my. 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 rt nhi u. Trên th c th , thu t toán Strassen’s tt hơn thu t toán nhân ma tr n thông th ng vi ≥ 32 19
  21. ổ ế  Chia tr ch là mt 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 da trên quy np và ph ơ ng pháp nh lý tng quát.  Thông th ng ph ơ ng pháp chia tr khá hi u qu . 20