tailieunhanh - Giáo trình phân tích khả năng ứng dụng kĩ thuật thiết kế giải thuật ứng dụng trong sản xuất p8

Tham khảo tài liệu 'giáo trình phân tích khả năng ứng dụng kĩ thuật thiết kế giải thuật ứng dụng trong sản xuất p8', công nghệ thông tin, kỹ thuật lập trình phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | Bài 5 Xét một trò chơi có 6 viên bi hai người thay phiên nhau nhặt từ 1 đến 3 viên. Người phải nhặt chỉ một viên bi cuối cùng thì bị thua. 1. Vẽ toán bộ cây trò chơi 2. Sử dụng kĩ thuật cắt tỉa alpha-beta định trị cho nút gốc 3. Ai sẽ thắng trong trò chơi này nếu hai người đều đi những nước tốt nhất. Hãy cho một nhận xét về trường hợp tổng quát khi ban đầu có n viên bi và mỗi lần có thể nhặt từ 1 đến m viên. Bài 6 Xét một trò chơi có 7 cái đĩa. Người chơi 1 chia thành 2 chồng có số đĩa không bằng nhau. Người chơi 2 chọn một chồng trong số các chồng có thể chia và tiếp tục chia thành hai chồng không bằng nhau. Hai người luân phiên nhau chia đĩa như vậy cho đến khi không thể chia được nữa thì thua. 1. Vẽ toàn bộ cây trò chơi. 2. Sử dụng kĩ thuật cắt tỉa alpha-beta định trị cho nút gốc 3. Ai sẽ thắng trong trò chơi này nếu hai người đều đi những nước tốt nhất. Bài 7 Cho bài toán cái ba lô với trọng lượng của ba lô W 30 và 5 loại đồ vật được cho trong bảng bên. Tất cả các loại đồ vật đều chỉ có một cái. 1. Giải bài toán bằng kỹ thuật Tham ăn Greedy . 2. Giải bài toán bằng kỹ thuật nhánh cận. Loại đồ vật Trọng lượng Giá trị A 15 30 B 10 25 C 2 2 D 4 6 E 8 24 Trang 84 Giải thuật CHƯƠNG 4 CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT LƯU TRỮ NGOÀI TỔNG QUAN Mục tiêu Sau khi học chương này sinh viên cần nắm được các vấn đề sau Tiêu chuẩn đế đánh giá giải thuật xử lý ngoài. Giải thuật sắp xếp trộn để sắp xếp ngoài và phương pháp cải tiến tốc độ sắp xếp trộn. Cách thức tổ chức lưu trữ và các giải thuật tìm kiếm xen xoá thông tin trên các tập tin tuần tự tập tin chỉ mục tập tin bảng băm và đặc biệt là tập tin B-cây. Kiến thức cơ bản cần thiết Cấu trúc dữ liệu danh sách liên kết. Các cấu trúc dữ liệu cây và bảng băm. Vấn đề tìm kiếm tuần tự và tìm kiếm nhị phân. Các thao tác trên kiểu dữ liệu tập tin. Tài liệu tham khảo . Aho . Hopcroft . Ullman Data Structures and Algorithms Addison-Wesley 1983. Chapter 10 . Đinh Mạnh Tường Cấu trúc dữ liệu Thuật toán Nhà xuất