›

Thiết Kế và Đánh Giá Thuật Toán Phân Tích Thuật Toán - Lê Nguyên Khôi

pdf 29 trang huongle 3860
Download
Bạn đang xem 20 trang mẫu của tài liệu "Thiết Kế và Đánh Giá Thuật Toán Phân Tích Thuật Toán - 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:

  • pdfthiet_ke_va_danh_gia_thuat_toan_phan_tich_thuat_toan_le_nguy.pdf

Nội dung text: Thiết Kế và Đánh Giá Thuật Toán Phân Tích Thuật Toán - Lê Nguyên Khôi

  1. Thi ết Kế & Đánh Giá Thu ật Toán Phân Tích Thu ật Toán TS. Lê Nguyên Khôi Tr ườ ng Đại Học Công Ngh ệ - ĐHQGHN
  2. Nội Dung  Thu t toán  Bài toán sp xp  Sp xp chèn  Phân tích th i gian ch y sp xp chèn 1
  3. Thu ật Toán  Mt th tc tính toán c nh ngh a rõ ràng  Mt chu i các b c tính toán  Nh n mt tp các giá tr u vào  Tr mt tp các giá tr u ra  Tính úng n: vi tt c các tp giá tr u vào, thu t toán a ra tp giá tr u ra úng 2
  4. Bài Toán  Sp xp  Tìm ki m  Mng Internet ( nh tuy n d li u)  Th ơ ng mi in t  Doanh nghi p sn xu t  ng i ng n nh t  Chu i chung dài nh t  Vân vân 3
  5. Một Số Vấn Đề Khác  Cu trúc d li u  Cách lu tr và t ch c d li u to iu ki n truy cp và thay i mt cách d dàng  Hi u qu :  P: thu t toán có th ch y trong th i gian a th c  NP-complete: không th ch y trong kho ng th i gian hp lý  Song song:  Nhi u phép tính mi giây bng nhi u lõi 4
  6. Bài Toán Sắp Xếp  Input: mt dãy s , , ,  Output: t hp ca dãy trên sao , , , cho ≤ ≤ ⋯ ≤  Ví d:  Input: 8 2 4 9 3 6  Output: 2 3 4 6 8 9  Hi u qu :  Th i gian ch y ca thu t toán sp xp dãy s?  Thu t toán tt nh t (ch y nhanh nh t)? 5
  7. Thu ật Toán Sắp Xếp  Sp xp chèn (Insertion sort):  Sp xp tr n (Merge sort): log  Vi ; ; = 2 = 50 = 10.000.000  Sp xp chèn: / = 20.000giy ≈ 5,5giờ  Sp xp tr n: . . / ≈ 1.163giy < 20phút  Khi nào s.x. chèn nhanh hơn s.x. tr n? 6
  8. Sắp Xếp Chèn – Minh Họa 8 2 4 9 3 6 2 8 4 9 3 6 2 4 8 9 3 6 2 4 8 9 3 6 2 3 4 8 9 6 2 3 4 6 8 9 7
  9. Sắp Xếp Chèn – Mã Gi ả InsertionSort () 1 for ← 2 to . do 2 ← [] 3 ← − 1 4 while > 0 and > do 5 + 1 ← [] 6 ← − 1 7 +1 ← Mã gi xem tr.18, tr.20 – 22 8
  10. Sắp Xếp Chèn – Tính Đúng Đắn  Khái ni m tính bt bi n (loop invariant):  Bt u mi vòng lp for dãy con [1 − 1] chính là dãy ban u nh ng ã c sp xp.  Kh i to: úng tr c khi vòng for lp bt u  Duy trì: úng tr c mt ln lp thì úng tr c ln lp ti p theo  Kt thúc: tính bt bi n giúp ch ng minh thu t toán úng 9
  11. Ch ứng Minh Quy Nạp – Induction Proof  Tr ng hp cơ bn (base case)  Tr ng hp quy np (inductive case)  Ch ng minh tính “Duy trì” s dng ch ng minh quy np:  Cho rng [1 − 1] ã c sp xp  Ch ra [1 ] cng c sp xp  Xem ch ng minh tr.19 – 20 10
  12. Phân Tích Thu ật Toán – Gi ả Định  Ki n trúc Random Access Machine  X lý tu n t các phép toán  Các phép toán (thao tác) cơ bn =, +, -, *, /, %, , , load, store, copy, iu khi n, r nhánh,  Mi phép toán th c hi n trong th i gian c nh (cn trên)  D li u u vào c bi u di n log bit  Không b nh o, cache 11
  13. Phân Tích Thu ật Toán – Th ời Gian Ch ạy  Th i gian ch y ph thu c vào d li u u vào: dãy ã sp xp dãy ch a sp xp  Th i gian ch y ph thu c vào ln d li u u vào: dãy ng n dãy dài  Thông th ng xét cn trên (tr ng hp xu nh t) 12
  14. Phân Tích Thu ật Toán – Th ời Gian Ch ạy  Tr ng hp xu nh t: (thông th ng)  () = th i gian lâu nh t thu t toán ch y vi d li u u vào c bt k  Tr ng hp trung bình: ( ôi khi)  () = th i gian trung bình thu t toán ch y vi tt c d li u u vào  Cn gi thi t v hàm phân ph i xác xu t cho d li u u vào  Tr ng hp tt nh t: (hi m)  Li dng thu t toán ch m ch y nhanh vi mt s d li u u vào 13
  15. Sắp Xếp Chèn – Mã Gi ả InsertionSort () 1 for ← 2 to . do 2 ← [] 3 ← − 1 4 while > 0 and > do 5 + 1 ← [] 6 ← − 1 7 +1 ← Mã gi xem tr.18, tr.20 – 22 14
  16. Sắp Xếp Chèn – Phân Tích Th ời Gian InsertionSort () 1 for to do ← 2 . 2 − 1 ← [] 3 − 1 ← − 1 4 while and do > 0 > 5 − 1 + 1 ← [] 6 − 1 ← − 1 7 +1 ← 15
  17. Sắp Xếp Chèn – Phân Tích Th ời Gian  Tng th i gian: = + − 1 + − 1 + + − 1 + − 1 + − 1  : s ln lp vòng while 16
  18. Sắp Xếp Chèn – Phân Tích Th ời Gian  Tr ng hp tt nh t ( ): = 1 = + − 1 + − 1 + − 1 + − 1 = + + + + + = +  hàm tuy n tính  Khi mng ã sp xp tng dn 17
  19. Sắp Xếp Chèn – Phân Tích Th ời Gian  Tr ng hp xu nh t = + − 1 + − 1 + 1 − 1 + − 1 + 2 2 − 1 + + − 1 2 = + + = + +  hàm bc hai  Khi mng ã sp xp gi m dn 18
  20. Bài Tập  Exercise: 2.1-4 tr.22  Cng 2 s n-bit  Exercise: 2.2-2 tr.29  Sp xp la ch n (selection sort)  Problem: 2-2 tr.40  Sp xp ni bt (bubble sort) 19
  21. Bài Tập – Exercise 2.1-4 Cng 2 s n-bit:  Cho 2 s nguyên nh phân n-bit, lu trong 2 mng n-ph n t A & B. Tng 2 s này lu trong mng n+1-ph n t C d i dng nh phân.  Vi t mã gi cho thu t toán cng 2 s này.  Phân tích ph c tp ca thu t toán. 20
  22. Bài Tập – Exercise 2.1-4 BinaryAdder (, , , ) 1 ← 0 2 for ← downto 1 do 3 + 1 ← + + 4 ← + 1 div2 5 + 1 ← + 1 mod2 6 1 ← Th i gian ch y: = + + 1 + + + + = + + + + = + 21
  23. Bài Tập – Exercise 2.2-2 Sp xp la ch n (selection sort):  Sp xp n s trong mng A theo cách tìm ph n t nh nh t ca A và i ch vi A[1]. Tìm ph n t nh nh t th hai ca A và i ch vi A[2]. Ti p tc nh vy cho n-1 ph n t u tiên ca A.  Vi t mã gi cho thu t toán trên.  Tính bt bi n (loop invariant) ca thu t toán?  Ti sao ch cn ch y vi n-1 ph n t u tiên.  Phân tích ph c tp ca thu t toán (tr ng hp tt nh t & xu nh t) 22
  24. Bài Tập – Exercise 2.2-2 SelectionSort () 1 for ← 1 to . − 1 do 2 ← 3 for ← + 1 to . do 4 if < [] 5 ← 6 exchange with [] 23
  25. Bài Tập – Exercise 2.2-2 SelectionSort () Th i gian ch y: = + − 1 + + − 1 + − 1 + − 1 = + + = + + 24
  26. Bài Tập – Problem 2-2  Sp xp ni bt (bubble sort): 25
  27. Bài Tập – Problem 2-2 BubbleSort () 1 do 2 ← 3 for ← . downto 2 do 4 if < [ − 1] 5 exchange with − 1 6 ← 7 while ( = ) 26
  28. Bài Tập – Problem 2-2 BubbleSort () 1 for ← 1 to . − 1 do 2 for ← . downto + 1 do 3 if < [ − 1] 4 exchange with [ − 1] 27
  29. Tổng Kết  Phân tích th i gian ch y da trên ln d li u u vào  Phân tích th i gian ch y thu t toán trong tr ng hp xu nh t  Th i gian ch y ca sp xp chèn là hàm bc hai i vi ln d li u u vào 28