TAILIEUCHUNG - 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

Chia để trị là một phương pháp được áp dụng rộng rãi, ý tưởng chung là phân rã bài toán thành bài toán nhỏ hơn "độc lập" với nhau, giải các bài toán con theo cùng 1 cách thức, "Tổng hợp"” lời các bài toán con để có được kết quả bài toán ban đầu. Để tìm hiểu rõ hơn về phương pháp này, bài giảng. | 2/2/2017 Phân tích và Thiết kế THUẬT TOÁN Hà Đại Dương duonghd@ Web: Bài 4 - Thiết kế thuật toán Chia để trị Divide&Conquer PHÂN TÍCH VÀ THIẾT KẾ THUẬ TOÁN NỘI DUNG I. II. III. IV. Giới thiệu Lược đồ chung Bài toán áp dụng Bài tập 1 2/2/2017 I. Giới thiệu Là một phương pháp được áp dụng rộng rãi Ý tưởng chung là phân rã bài toán thành bài toán nhỏ hơn “độc lập” với nhau. Giải các bài toán con theo cùng 1 cách thức “Tổng hợp” lời các bài toán con để có được kết quả bài toán ban đầu. Tư tưởng chung của cách tiếp cận Chia để trị II. Lược đồ chung Chia: • 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 “độc lập” • 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, hoặc không thể chia nhỏ nữa) Trị: • 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 giải trực tiếp Tổng hợp: • 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. II. Lược đồ chung 2 2/2/2017 III. Bài toán áp dụng 1. Tìm kiếm nhị phân The Manhattan phone book has 1,000,000+ entries. How is it possible to locate a name by examining just a tiny, tiny fraction of those entries? III. Bài toán áp dụng 1. Tìm kiếm nhị phân Key idea of “phone book search”: repeated halving To find the page containing Pat Reed’s number while (Phone book is longer than 1 page) Open to the middle page. if “Reed” comes before the first entry, Rip and throw away the 2nd half. else Rip and throw away the 1st half. end end III. Bài toán áp dụng 1. Tìm kiếm nhị phân What happens to the phone book length? Original: 3000 After 1 rip: 1500 After 2 rips: 750 After 3 rips: 375 After 4 rips: 188 After 5 rips: 94 : After 12 rips: 1 pages pages pages pages pages pages page 3 2/2/2017 III. Bài toán áp dụng 1. Tìm kiếm nhị phân • Repeatedly halving the size of the “search space” is the main idea behind the method of binary search. • An item in a sorted array of length n can be .

• Kỹ thuật lập trình
• Phân tích thiết kế giải thuật
• Thiết kế thuật toán
• Chia để trị
• Bài tập Chia để trị
• Đánh giá độ phức tạp thuật toán
• Kỹ thuật thiết kế giải thuật
• Thiết kế giải thuật
• Bài giảng thiết kế giải thuật
• Kỹ thuật phân tích thiết kế giải thuật
• Bài giảng phân tích thiết kế giải thuật
• Phân tích thuật toán
• Phương pháp phân tích thuật toán
• Vai trò của phân tích thuật toán
• Quá trình phân tích thuật toán
• Phân tích thiết kế thuật toán
• Bài giảng Phân tích thiết kế thuật toán
• Giải thuật xấp xỉ
• Bài toán che phủ đỉnh
• Bài toán NP đầy đủ
• Phân tích thiết kế giải thuật chương 37
• Bài giảng Phân tích thiết kế
• Phân tích thiết kế dữ liệu
• Cắt tỉa Alpha Beta
• Tiêu chuẩn đánh giá giải thuật
• Phương pháp đánh giá giải thuật
• Phương pháp thiết kế thuật giải
• Thuật toán chính xác
• Thuật toán gần đúng
• Bước thiết kế một thuật giải
• Single Source Shortest Paths
• Phân tích thiết kế giải thuật chương 10
• Giải bài toán các đường đi ngắn nhất
• Biểu diễn các đường đi ngắn nhất
• Thuật toán sắp xếp
• Phân tích thuật toán sắp xếp
• Thuật toán tìm kiếm
• Phân tích thuật toán tìm kiếm
• Kỹ thuật phân tích thuật toán
• Đánh giá một giải thuật
• Cây khung nhỏ nhất
• Giải thuật tổng quát
• Giải thuật của Kruskal
• Giải thuật của Prim
• Phân tích giải thuật
• Hệ thức truy hồi
• Độ phức tạp giải thuật
• Phân tích giải thuật lặp
• Phân tích giải thuật đệ quy
• Phân tích thuật giải
• Thiết kế thuật giải
• Chiến lược thiết kế thuật giải
• Quy hoạch động
• Biểu diễn thuật giải
• Phân tích thiết kế thuật toán
• Kỹ thuật tối ưu hóa chương trình
• Mức thiết kế một chương trình
• Kỹ thuật tinh chế mã
• Kỹ thuật tối ưu hóa rẽ nhánh
• Phương pháp thiết kế thuật toán
• Tối ưu thuật toán
• Cấu trúc dữ liệu giải thuật
• Bài giảng Cấu trúc dữ liệu giải thuật
• Giải thuật quay lui
• Giải thuật tìm kiếm trong đồ thị
• Biểu diễn của một đồ thị
• Biểu diễn một đồ thị vô hướng
• Biểu diễn một đồ thị có hướng
• Giải thuật sắp xếp
• Chương trình sắp xếp
• Cấu trúc dữ liệu
• Giải thuật lưu trữ ngoài
• Giải thuật nâng cao
• Kỹ thuật phân tích giải thuật
• Hệ thống thông tin
• Giải thuật hình học
• Giải thuật so khớp chuỗi
• Hình học tính toán
• Giải thuật thô sơ
• Kỹ thuật quét
• Tính đúng đắn
• Kỹ thuật mã hóa
• Giải thuật đệ quy
• Thiết kế giải thuật đệ quy
• Đệ quy tuyến tính
• Đệ quy nhị phân