TAILIEUCHUNG - Bài giảng Thuật toán ứng dụng: Chia để trị

Bài giảng Thuật toán ứng dụng: Chia để trị. Chương này cung cấp cho học viên những nội dung về: tổng quan chia để trị; ví dụ minh họa; độ phức tạp chia để trị; sắp xếp trộn; giảm để trị; . Mời các bạn cùng tham khảo chi tiết nội dung bài giảng! | THUẬT TOÁN ỨNG DỤNG CHIA ĐỂ TRỊ Phạm Quang Dũng Bộ môn KHMT dungpq@ 1 NộI dung Tổng quan chia để trị Ví dụ minh họa Độ phức tạp chia để trị Giảm để trị 2 Tổng quan chia để trị Chia bài toán cần giải ban đầu thành các bài toán con độc lập nhau Giải trị các bài toán con Tổng hợp lời giải của các bài toán con để dẫn ra lời giải của bài toán xuất phát 3 Ví dụ minh họa Bài toán dãy con dài nhất cho dãy số nguyên a a1 a2 an. Tìm dãy con gồm một số liên tiếp các phần tử có tổng lớn nhất Phân chia ký hiệu P i j là lời giải của bài toán tìm dãy con liên tiếp của dãy ai ai 1 aj có tổng cực đại Tổng hợp lời giải Ký hiệu PL i j là lời giải của bài toán tìm dãy con liên tiếp của dãy ai ai 1 aj sao cho phần tử cuối cùng là aj có tổng cực đại Ký hiệu PR i j là lời giải của bài toán tìm dãy con liên tiếp của dãy ai ai 1 aj sao cho phần tử đầu tiên là ai có tổng cực đại 4 Ví dụ minh họa Xét đoạn l l 1 . r . Ký hiệu m l r 2 P l r MAX P l m P m 1 r PL l m PR m 1 r l P l m P m 1 r r m m 1 PL l m PR m 1 r 5 Ví dụ minh họa include using namespace std define INF 1e9 define MAX 1000000 int a MAX int n void input cin gt gt n for int i 0 i lt n i cin gt gt a i 6 Ví dụ minh họa int PL int l int r int rs -INF int s 0 for int i r i gt l i- s a i rs max rs s return rs int PR int l int r int rs -INF int s 0 for int i l i Ví dụ minh họa int P int l int r if l r return a r int m l r 2 return max max P l m P m 1 r PL l m PR m 1 r void solve cout Độ phức tạp tính toán Chia bài toán xuất phát thành a bài procedure D-and-C n toán con mỗi bài toán con kích 1. if n n0 thước n b 2. xử lý trực tiếp T n thời gian của bài toán kích 3. else thước n 4. chia bài toán xuất phát Thời gian phân chia dòng 4 D n thành a bài toán con kích thước Thời gian tổng hợp lời giải dòng 6 n b C n 5. gọi đệ quy a bài toán con Công thức truy hồi 6. tổng hợp lời giải 7. Q 1 0 T gt 0 9 Độ phức tạp tính toán Độ phức tạp của thuật toán chia để trị định lí thợ Công thức truy hồi T n aT n b cnk với các hằng số a 1 b

• Cơ sở dữ liệu
• Bài giảng Thuật toán ứng dụng
• Thuật toán ứng dụng
• Chia để trị
• Thuật toán chia để trị
• Công thức truy hồi
• Tìm kiếm nhị phân
• Phân tích Thuật toán
• Quy hoạch động
• Cài đặt thuật toán
• Thuật toán Tham lam
• Ý tưởng tham lam
• Bài toán lập lịch
• Tiếp cận tham lam
• Toán ứng dụng
• Bài giảng Toán ứng dụng
• Biểu diễn đồ thị
• Thuật toán tìm kiếm
• Bài toán đường đi ngắn nhất
• Thuật toán Floyd
• Tiếp cận chia để trị
• Bài toán tháp Hà Nội
• Bài toán tính giá trị đa thức
• Bài toán đếm số dãy con
• Bài giảng Ma trận
• Khái niệm thuật toán
• Thuật toán trong tin học
• Phương pháp biểu diễn thuật toán
• Cấu trúc dữ liệu
• Chương trình nhân hai số nguyên
• Kỹ năng phân loại bài toán
• Kỹ năng phân tích thuật toán
• Quay lui đệ qui
• Bài toán quy hoạch động
• Thuật toán quay lui
• Liệt kê nhị phân
• Đệ quy quay lui
• Bài toán liệt kê xâu nhị phân
• Phương trình tuyến tính
• Thuật toán nhánh và cận
• Chu trình Euler
• Thuật toán Dijkstra
• Thuật toán Kruskal
• Disjoint set structure
• Bài toán xếp ba lô
• Bài toán dãy con chung dài nhất
• Phân tích về quy hoạch động
• Biểu diễn đồ thị trong máy tính
• Thuật toán Floyd Warshall
• Đồ thị phẳng
• Thư viện cấu trúc dữ liệu
• Cấu trúc dữ liệu mở
• Thuật toán Dequeue
• Thuật toán Tarjan DFS
• Duyệt theo chiều sâu
• Cấu trúc dữ liệu duy trì
• Cấu trúc dữ liệu trừu tượng
• Giải thuật tìm kiếm
• Cài đặt tìm kiếm ở thư viện
• Hàm đệ quy
• Quy tắc xây dựng phần tử
• Nhánh cận
• Chiến lược tìm kiếm tối ưu tổ hợp
• Danh sách tuyến tính
• Quan hệ tuyến tính
• Ngăn xếp dữ liệu
• Dãy con cực đại
• Dãy con tăng dần dài nhất
• Dãy con chung dài nhất
• Thuật toán nâng cao
• Bài giảng Thuật toán nâng cao
• Thuật toán quay lui tổng quát
• Ứng dụng của thuật toán quay lui
• Chuỗi nhị phân
• Bài giảng Lý thuyết tài chính ứng dụng
• Lý thuyết tài chính ứng dụng
• Kế toán doanh nghiệp
• Bản chất cuả tài chính
• Chức năng của tài chính
• Vai trò của tín dụng
• Tài chính doanh nghiệp
• Bài giảng Tin học 10 bài 8
• Bài giảng điện tử Tin học 10
• Bài giảng lớp 10 Tin học
• Bài giảng điện tử lớp 10
• Quy trình quản lý tin học
• Giải các bài toán khoa học kĩ thuật
• Những ứng dụng của tin học
• Bài giảng Kỹ thuật điện tử
• Kỹ thuật điện tử
• Vi mạch khuếch đại thuật toán
• Vi mạch thuật toán
• Thông số kỹ thuật vi mạch thuật toán
• Ứng dụng vi mạch thuật toán
• Bài giảng Cấu trúc dữ liệu và thuật toán
• Cấu trúc dữ liệu và thuật toán
• Ứng dụng cây gia phả
• Ứng dụng cây thư mục
• Thiết kế thuật toán
• Bài giảng Phân tích thuật toán
• Thuật toán hoán vị
• Số nghịch thế
• Bảng nghịch thế
• Lý thuyết đồ thị
• Bài giảng Lý thuyết đồ thị
• Thuật toán tìm kiếm trên đồ thị
• Thuật toán tìm kiếm theo chiều sâu
• Thuật toán tìm kiếm theo chiều rộng
• Ứng dụng thuật toán tìm kiếm đồ thị