Bài giảng Phân tích thiết kế giải thuật: Thiết kế thuật toán - Chia để trị - GV. Hà Đại Dương

2/2/2017<br /> <br /> Phân tích và Thiết kế<br /> THUẬT TOÁN<br /> Hà Đại Dương<br /> duonghd@mta.edu.vn<br /> Web: fit.mta.edu.vn/~duonghd<br /> <br /> Bài 4 - Thiết kế thuật toán<br /> Chia để trị Divide&Conquer<br /> PHÂN TÍCH VÀ THIẾT KẾ THUẬ TOÁN<br /> <br /> NỘI DUNG<br /> I.<br /> II.<br /> III.<br /> IV.<br /> <br /> Giới thiệu<br /> Lược đồ chung<br /> Bài toán áp dụng<br /> Bài tập<br /> <br /> 1<br /> <br /> 2/2/2017<br /> <br /> I. Giới thiệu<br />  Là một phương pháp được áp dụng rộng rãi<br />  Ý tưởng chung là phân rã bài toán thành bài toán nhỏ hơn “độc lập”<br /> với nhau.<br />  Giải các bài toán con theo cùng 1 cách thức<br />  “Tổng hợp” lời các bài toán con để có được kết quả bài toán ban đầu.<br /> <br /> <br /> Tư tưởng chung của cách tiếp cận Chia để trị<br /> <br /> II. Lược đồ chung<br /> Chia:<br /> • Bằng cách nào đó chia tập hợp các đối tượng của bài toán thành bài toán con<br /> “độc lập”<br /> • Tiếp tục chia các bài toán con cho đến khi có thể giải trực tiếp (không cần,<br /> hoặc không thể chia nhỏ nữa)<br /> <br /> Trị:<br /> • Trên các bài toán con thực hiện cùng một cách thức: Chia nhỏ nếu cần hoặc<br /> giải trực tiếp<br /> <br /> Tổng hợp:<br /> • Khi mỗi bài toán con được giải, tổng hợp để có kết quả bài toán ban đầu.<br /> <br /> II. Lược đồ chung<br /> <br /> 2<br /> <br /> 2/2/2017<br /> <br /> III. Bài toán áp dụng<br /> 1. Tìm kiếm nhị phân<br /> The Manhattan phone<br /> book has 1,000,000+<br /> entries.<br /> How is it possible to<br /> locate a name by<br /> examining just a tiny, tiny<br /> fraction of those entries?<br /> <br /> III. Bài toán áp dụng<br /> 1. Tìm kiếm nhị phân<br /> <br /> Key idea of<br /> “phone book<br /> search”: repeated<br /> halving<br /> <br /> To find the page containing Pat Reed’s number…<br /> while (Phone book is longer than 1 page)<br /> Open to the middle page.<br /> if “Reed” comes before the first entry,<br /> Rip and throw away the 2nd half.<br /> else<br /> Rip and throw away the 1st half.<br /> end<br /> end<br /> <br /> III. Bài toán áp dụng<br /> 1. Tìm kiếm nhị phân<br /> <br /> What happens to the<br /> phone book length?<br /> <br /> Original:<br /> 3000<br /> After 1 rip: 1500<br /> After 2 rips: 750<br /> After 3 rips: 375<br /> After 4 rips: 188<br /> After 5 rips:<br /> 94<br /> :<br /> After 12 rips:<br /> 1<br /> <br /> pages<br /> pages<br /> pages<br /> pages<br /> pages<br /> pages<br /> page<br /> <br /> 3<br /> <br /> 2/2/2017<br /> <br /> III. Bài toán áp dụng<br /> 1. Tìm kiếm nhị phân<br /> • Repeatedly halving the size of the “search space” is the<br /> main idea behind the method of binary search.<br /> • An item in a sorted array of length n can be located with<br /> just log2 n comparisons.<br /> n log2(n)<br /> <br /> 100<br /> 1000<br /> 10000<br /> <br /> • “Savings” is significant!<br /> <br /> 7<br /> 10<br /> 13<br /> <br /> III. Bài toán áp dụng<br /> 1<br /> <br /> 2<br /> <br /> 3<br /> <br /> 4<br /> <br /> 5<br /> <br /> 6<br /> <br /> 7<br /> <br /> 8<br /> <br /> 9 10<br /> <br /> 11 12<br /> <br /> v 12 15 33 35 42 45 51 62 73 75 86 98<br /> Binary<br /> search:<br /> target x =<br /> 70<br /> <br /> L:<br /> <br /> 1<br /> <br /> Mid:<br /> <br /> 6<br /> <br /> R:<br /> <br /> 12<br /> <br /> v(Mid)