TAILIEUCHUNG - Bài giảng Thuật toán ứng dụng: Tiếp cận chia để trị - Trương Xuân Nam

Bài giảng Thuật toán ứng dụng: Tiếp cận chia để trị cung cấp cho người học những kiến thức như: Ý tưởng chia để trị; Bài toán tính giá trị đa thức; Bài toán tháp Hà Nội; Bài toán đếm số dãy con có tổng cho trước; Phân tích về chia để trị; Bài tập. Mời các bạn cùng tham khảo! | THUẬT TOÁN ỨNG DỤNG Tiếp cận Chia để trị Nội dung 1. Ý tưởng chia để trị 2. Bài toán tính giá trị đa thức 3. Bài toán tháp Hà Nội 4. Bài toán đếm số dãy con có tổng cho trước 5. Phân tích về chia để trị 6. Bài tập TRƯƠNG XUÂN NAM 2 Phần 1 Ý tưởng chia để trị TRƯƠNG XUÂN NAM 3 Ý tưởng chia để trị TRƯƠNG XUÂN NAM 4 Ý tưởng chia để trị Bài học từ cuộc sống chia nhỏ bó đũa để dễ bẻ hơn Ý tưởng cơ bản chia nhỏ bài toán lớn thành các bài toán con để có thể tìm lời giải dễ dàng hơn Tính nhanh ab Tính x ab 2 Tính ab x x nếu b chẵn Hoặc ab x x a nếu b lẻ Chú ý đây vẫn chưa phải cách tính nhanh nhất Sắp xếp trộn Chia dãy làm hai dãy con Sắp xếp hai dãy con Trộn hai dãy con đã sắp làm một TRƯƠNG XUÂN NAM 5 Ý tưởng chia để trị Sắp xếp nhanh Chọn ngẫu nhiên một giá trị m Chia dãy thành hai nửa Một nửa đầu nhỏ hơn m Một nửa sau lớn hơn m Sắp xếp nửa đầu Sắp xếp nửa sau Tìm kiếm nhị phân Chia miền tìm kiếm làm hai Chọn miền tìm kiếm phù hợp Gần như 100 các bài chia đệ trị đặt nền tảng trên lối viết đệ quy TRƯƠNG XUÂN NAM 6 Phần 2 Bài toán tính giá trị đa thức TRƯƠNG XUÂN NAM 7 Bài toán tính giá trị đa thức Cho đa thức Pn x a0xn a1xn-1 . an-1x an Nhập các giá trị a0 a1 . an và x tính giá trị Pn x . Giải bằng chia để trị - P0 x a0 - Pn x Pn-1 x x an Viết bằng đệ quy Chuyển đổi tương ứng sang vòng lặp TRƯƠNG XUÂN NAM 8 Phần 3 Bài toán tháp Hà Nội TRƯƠNG XUÂN NAM 9 Bài toán tháp Hà Nội Có 3 cọc gỗ và N miếng gỗ tròn có bán kích từ nhỏ đến lớn Ban đầu tất cả N miếng gỗ đặt chồng lên nhau ở cọc số 1 theo thứ tự nhỏ ở trên lớn ở dưới Hãy chuyển N miếng gỗ này sang cọc 3 Điều kiện Mỗi lần di chuyển được lấy một miếng gỗ từ cọc này đặt sang cọc khác Tại mọi thời điểm trên cùng một cọc thì miếng gỗ ở trên bao giờ cũng có bán kính nhỏ hơn miếng gỗ ở dưới TRƯƠNG XUÂN NAM 10 Bài toán tháp Hà Nội Tiếp cận chia để trị chia vấn đề thành 3 vấn đề con Chuyển n miếng từ cọc A qua trung gian B sang cọc C Chuyển n-1 miếng từ cọc A qua trung gian C sang cọc B Chuyển miếng thứ n từ A sang C Chuyển n-1

• Cơ sở dữ liệu
• Bài giảng Thuật toán Ứng dụng
• Thuật toán Ứng dụng
• 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
• 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
• 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
• Chia để trị
• Thuật toán chia để trị
• Công thức truy hồi
• Tìm kiếm nhị phân
• 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ị