Tiếp nối phần 1, Giáo trình Phân tích thiết kế thuật toán (Nghề Lập trình máy tính): Phần 2 cung cấp cho người học những kiến thức như: phương pháp chia để trị, phương pháp tham lam, phương pháp quay lui và quy hoạch động. Mời các bạn tham khảo! | Phân tích thiết kế thuật toán BÀI 4 PHƯƠNG PHÁP CHIA ĐỂ TRỊ Mã bài Giới thiệu Mặc dù không tồn tại một phương pháp vạn năng nào có thể giúp chúng ta thiết kế được thuật toán giải quyết mọi vấn đề nhưng các nhà nghiên cứu đã tìm ra một số phương pháp thiết kế cơ bản các phưong pháp này còn được gọi là các chiến lược thiết kế thuật toán. Mỗi phương pháp này có thể áp dụng để giải quyết một phạm vi khá rộng các bài toán. Trong tài liệu này chúng tôi sẽ trình bày các phương pháp thiết kế thuật toán như chia để trị divide and conquer phương pháp tham lam greeding method quay lui backtracking quy hoạch động dynamic programming nhánh cận branch and bound . Trong mỗi chiến lược chúng tôi sẽ trình bày phương pháp chung sau đó sẽ đưa ra một số ví dụ minh họa. Cần lưu ý rằng các phương pháp thiết kế thuật toán mà chúng ta xem xét chỉ là các chiến lược có tính định hướng sự tìm tòi thuật toán. Trong bài này chúng ta sẽ xét một phương pháp thường được sử dụng đó là phương pháp chia để trị. Mục tiêu thực hiện Học xong bài này học viên sẽ có khả năng Nắm bắt được ý tưởng của phương pháp chia để trị. Sử dụng phương pháp chia để trị để giải quyết các bài toán tìm kiếm chọn các phân từ sắp xếp nhân ma trận. Áp dụng phương pháp chia để trị để giải quyết một số bài toán trong thực tế. Thấy được lợi thế của phương pháp chia để trị trong việc xây dựng một số thuật toán. .13. Phương pháp tổng quát Ý tưởng chính của phương pháp này là phân bài toán cần giải thành các bài toán con. Các bài toán con lại được tiếp tục phân thành các bài toán con nhỏ hơn cứ thế tiếp tục cho tới khi chúng ta nhận được các bài toán con hoặc là đã có thuật giải hoặc là có thể dễ dàng đưa ra thuật giải. Sau đó ta tìm cách kết hợp các nghiệm của các bài toán con để nhận được nghiệm của bài toán con lớn hơn để cuối cùng nhận được nghiệm của bài toán cần giải. Thông thường các bài toán 110 Phân tích thiết kế thuật toán con nhận được trong quá trình phân chia là cùng dạng với bài toán ban đầu chỉ có cỡ .
