›

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

pdf 22 trang huongle 3600
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 - Lập trình động - 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_lap_trinh_dong_le_ngu.pdf

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

  1. ế ế ậ ậ ộ ườ ạ ọ ệ
  2. ộ  K thut thi t k d i lên (bottom-up)  Mt s bài toán tiêu bi u 1
  3. aể ị ắ ạ  K thu t thi t k thu t toán  Ý t ng  Thi t k trên xu ng (top-down design)  Chia bài toán ln thành bài toán nh không giao nhau  Gi i các bài toán nh (theo ph ơ ng pháp quy)  Gp li gi i bài toán nh thành li gi i bài toán ln  Ví d  Sp xp gp (merge sort)  Sp xp nhanh (quick sort)  Tính s Fibonacci 2
  4. ậ ộ  K thu t thi t k thu t toán  Ý t ng  Thi t k d i lên (bottom-up design)  Ln l t gi i bài toán t nh nh t n ln  Xây dng li gi i bài toán ln da trên li gi i bài toán nh  Ví d  Sp xp chèn (insertion sort)  Tính s Fibonacci 3
  5. ậ ộ  Bài toán có tính ch t  Các bài toán con gi nhau (overlapping)  Cu trúc con ti u (optimal structure)  Li gi i ti u ca bài toán con có th s dng xây dng li gi i ti u cho bài toán toàn cc 4
  6. ậ ộ  Áp dng cho bài toán ti u  Có nhi u li gi i kh thi  Mi li gi i có giá tr c tr ng  Tìm li gi i có giá tr c tr ng ti u  Có th có nhi u li gi i có cùng giá tr c tr ng ti u  Thi t k cu trúc (bng) lu kt qu 5
  7. ậ ộ  Da trên các b c sau 1. a ra cách tính nghi m c a các bài toán con 2. Tìm công th c xây d ng nghi m c a bài toán thông qua nghi m c a các bài toán con 3. Thi t k b ng l u nghi m c a các bài toán 4. Tính nghi m c a các bài toán t nh n l n 5. Xây d ng nghi m c a bài toán c n tìm t b ng 6
  8. aể ị ậ ộ  La ch n úng k thu t rt quan tr ng  Áp dng chia tr cho bài toán mà bài toán con gi nhau  Gi i li các bài toán con  Không hi u qu  Ví d: tính s Fibonacci 7
  9.  Dãy Fibonacci  H s nh th c  Dãy con tng dài nh t  Bài toán ba lô  Dãy con chung dài nh t  Ct dây 8
  10. a =0,1 = + ≥ 2  Chia tr  Bài toán con có giao nhau  Lp trình ng  Bng lu kt qu các giá tr ã tính 9
  11. ệ ố ị ứ − 1 − 1 , = = + − 1  Chia tr  Bài toán con có giao nhau  Lp trình ng  Bng lu kt qu các giá tr , ã tính 10
  12. ấ  Tìm dãy con tng dài nh t ca dãy s S  Ví d  S = { 14, 1, 17, 2, 16, 17, 3, 15, 4, 1, 5, 18, 13, 6, 7, 19, 8, 12, 1, 9, 10, 8 }  Dãy tng S’ = { 14, 1, 17, 2, 16, 17, 3, 15, 4, 1, 5, 18, 13, 6, 7, 19 , 8, 12, 1, 9, 10, 8 }  Dãy tng dài nh t S = { 14, 1, 17, 2, 16, 17, 3, 15, 4, 1, 5, 18, 13, 6, 7, 19, 8, 12, 1, 9, 10 , 8 } 11
  13. ấ  Bài toán con: Tìm dãy con t ng dài nh t kt thúc t i ph n t th k  Thu t toán  Nu t t c các ph n t tr c k u ln hơn ho c bng S[k], tr v dãy con ch ch a S[k]  Nu có t ph n t ng tr c k nh h ơn S[k], gi W là dãy dài nh t trong các dãy con t ng kt thúc t i các ph n t này. Tr v W ∪ S[k] 12
  14. ấ s1 14 {14} S = { 14, 1, 17, 2, 16, s2 1 {1} s3 17 {14|1, 17} 17, 3, 15, 4, 1, 5, 18, s4 2 {1, 2} s5 16 13, 6, 7, 19, 8, 12, 1, s6 17 s7 3 9, 10, 8 } s8 15 s9 4 s10 1 s11 5 S dng tt c các Si s12 18 s13 13 ã c xây dng s14 6 ti p tc xây dng Sj s15 7 s16 19 s17 8 s18 12 s19 1 s20 9 s21 10 s22 8 13
  15. ấ s1 14 {14} S = { 14, 1, 17, 2, 16, s2 1 {1} s3 17 {14|1, 17} 17, 3, 15, 4, 1, 5, 18, s4 2 {1, 2} s5 16 {1, 2, 16} 13, 6, 7, 19, 8, 12, 1, s6 17 {1, 2, 16, 17} s7 3 {1, 2, 3} 9, 10, 8 } s8 15 {1, 2, 3, 15} s9 4 {1, 2, 3, 4} s10 1 {1} s11 5 {1, 2, 3, 4, 5} S dng tt c các Si s12 18 {1, 2, 3, 4, 5, 18} s13 13 {1, 2, 3, 4, 5, 13} ã c xây dng s14 6 {1, 2, 3, 4, 5, 6} ti p tc xây dng Sj s15 7 {1, 2, 3, 4, 5, 6, 7} s16 19 {1, 2, 3, 4, 5, 6, 7, 19} s17 8 {1, 2, 3, 4, 5, 6, 7, 8} s18 12 {1, 2, 3, 4, 5, 6, 7, 8, 12} s19 1 {1} s20 9 {1, 2, 3, 4, 5, 6, 7, 8, 9} s21 10 {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} s22 8 {1, 2, 3, 4, 5, 6, 7, 8} 14
  16. a Có N vt, vt i có kh i l ng wi và giá tr ti 1 chi c ba lô có th mang c không quá M kg Tìm cách mang mt s vt tng giá tr ly c là ln nh t. Ví d N = 5, M = 10 i ABCDE wi 1 3 5 7 9 ti $100 $200 $301 $400 $500 15
  17. a for mi ô [x, y] if x = 0 và y = 0 then vt Kh i l ng Giá tr cell[x, y] = 0kg $0 {} A 1kg $100 else B 3kg $200 gi m là vt thêm vào ct y C 5kg $301 gi w là kh i l ng ca m D 7kg $400 if w > kh i l ng cc i ca hàng E 9kg $500 cell[x, y] = cell[x, y-1] else cell[x, y] = max {cell[x, y-1], (cell[x-w, y-1] U {m})} tp r ng A A/B A/B/C A/B/C/D A/B/C/D/E kg 0 0kg $0 {} 0kg $0 {} 0kg $0 {} ?kg $? {} ?kg $? {} ?kg $? {} kg 1 0kg $0 {} 1kg $100 {A} 1kg $100 {A} ?kg $? {} ?kg $? {} ?kg $? {} kg 2 0kg $0 {} 1kg $100 {A} 1kg $100 {A} ?kg $? {} ?kg $? {} ?kg $? {} kg 3 0kg $0 {} 1kg $100 {A} 3kg $200 {B} ?kg $? {} ?kg $? {} ?kg $? {} kg 4 0kg $0 {} 1kg $100 {A} 4kg $300 {A, B} ?kg $? {} ?kg $? {} ?kg $? {} kg 5 0kg $0 {} 1kg $100 {A} ?kg $? {} ?kg $? {} ?kg $? {} ?kg $? {} kg 6 0kg $0 {} 1kg $100 {A} ?kg $? {} ?kg $? {} ?kg $? {} ?kg $? {} kg 7 0kg $0 {} 1kg $100 {A} ?kg $? {} ?kg $? {} ?kg $? {} ?kg $? {} kg 8 0kg $0 {} 1kg $100 {A} ?kg $? {} ?kg $? {} ?kg $? {} ?kg $? {} kg 9 0kg $0 {} 1kg $100 {A} ?kg $? {} ?kg $? {} ?kg $? {} ?kg $? {} kg 10 0kg $0 {} 1kg $100 {A} ?kg $? {} ?kg $? {} ?kg $? {} ?kg $? {} 16
  18. a for mi ô [x, y] if x = 0 và y = 0 then vt Kh i l ng Giá tr cell[x, y] = 0kg $0 {} A 1kg $100 else B 3kg $200 gi m là vt thêm vào ct y C 5kg $301 gi w là kh i l ng ca m D 7kg $400 if w > kh i l ng cc i ca hàng E 9kg $500 cell[x, y] = cell[x, y-1] else cell[x, y] = max {cell[x, y-1], (cell[x-w, y-1] U {m})} tp r ng A A/B A/B/C A/B/C/D A/B/C/D/E kg 0 0kg $0 {} 0kg $0 {} 0kg $0 {} 0kg $0 {} 0kg $0 {} 0kg $0 {} kg 1 0kg $0 {} 1kg $100 {A} 1kg $100 {A} 1kg $100 {A} 1kg $100 {A} 1kg $100 {A} kg 2 0kg $0 {} 1kg $100 {A} 1kg $100 {A} 1kg $100 {A} 1kg $100 {A} 1kg $100 {A} kg 3 0kg $0 {} 1kg $100 {A} 3kg $200 {B} 3kg $200 {B} 3kg $200 {B} 3kg $200 {B} kg 4 0kg $0 {} 1kg $100 {A} 4kg $300 {A, B} 4kg $300 {A, B} 4kg $300 {A, B} 4kg $300 {A, B} kg 5 0kg $0 {} 1kg $100 {A} 4kg $300 {A, B} 5kg $301 {C} 5kg $301 {C} 5kg $301 {C} kg 6 0kg $0 {} 1kg $100 {A} 4kg $300 {A, B} 6kg $401 {A,C} 6kg $401 {A,C} 6kg $401 {A,C} kg 7 0kg $0 {} 1kg $100 {A} 4kg $300 {A, B} 6kg $401 {A,C} 6kg $401 {A,C} 6kg $401 {A,C} kg 8 0kg $0 {} 1kg $100 {A} 4kg $300 {A, B} 8kg $501 {B,C} 8kg $501 {B,C} 8kg $501 {B,C} kg 9 0kg $0 {} 1kg $100 {A} 4kg $300 {A, B} 9kg $601 {A, B, C} 9kg $601 {A, B, C} 9kg $601 {A, B, C} kg 10 0kg $0 {} 1kg $100 {A} 4kg $300 {A, B} 9kg $601 {A, B, C} 9kg $601 {A, B, C} 9kg $601 {A, B, C} 17
  19. ấ Cho 2 dãy [1. . ] và [1. . ], tìm dãy con chung dài nh t ca chúng. :ABCBDAB :BDCABA Dãy con chung: ? AB ? BCDB ? BCBA 18
  20. ấ Cho 2 dãy [1. . ] và [1. . ], tìm dãy con chung dài nh t ca chúng. :A BCB D A B : B D C A BA LCS( , ) = BCBA 19
  21. ấ  Ki m tra tt c các dãy con ca [1. . ] xem có ph i dãy con ca [1. . ] không  Phân tích  Ki m tra = cho mi dãy con.  Có 2 dãy con ca .  Th i gian ch y xu nh t = 2 , th i gian hàm m. 20
  22. ắ  c Mc 15.1 Tr.360 21