Mời các bạn cùng tham khảo đề thi kết thúc học kỳ II năm học 2021-2022 môn Tối ưu rời rạc sau đây để biết được cấu trúc đề thi, cách thức làm bài thi cũng như những dạng bài chính được đưa ra trong đề thi. Từ đó, giúp các bạn sinh viên có kế hoạch học tập và ôn thi hiệu quả. | ĐẠI HỌC KHOA HỌC TỰ NHIÊN HÀ NỘI ĐỀ KIỂM TRA CUỐI KÌ Khoa Toán Cơ Tin học Môn thi Tối ưu rời rạc Đề thi có 2 trang Thời gian làm bài 110 phút Mã đề thi 46 LƯU Ý Hãy dùng chính ngôn ngữ của mình dịch từ slide nội dung giống sách tài liệu trên mạng hay giống bất kì một bài làm nào khác đều không được điểm cả người chép lẫn người cho chép . Tổng điểm của các câu là 11. Bài 1 điểm . Hãy lựa chọn một bài toán đã học trong môn học Tối ưu rời rạc nêu định nghĩa bài toán trình bày một thuật toán giải bài toán và độ phức tạp tính toán của thuật toán. Bài 2 điểm . Chính phủ muốn xây dựng hệ thống đường cao tốc nối 5 tỉnh thành phố gồm Hà Nội Bắc Ninh Hải Phòng Ninh Bình và Phú Thọ với nhau. Khoảng cách đường nối trực tiếp giữa các tỉnh nếu được xây dựng được đưa ra bởi bảng sau độ dài theo đơn vị km Hà Nội Bắc Ninh Hải Phòng Ninh Bình Phú Thọ Hà Nội 0 Bắc Ninh - 0 Hải Phòng - - 0 Ninh Bình - - - 0 Phú Thọ - - - - 0 a điểm . Bạn hãy giúp chính phủ đưa ra phương án kết nối có tổng độ dài là ngắn nhất qua đó có chi phí xây dựng nhỏ nhất sử dụng một thuật toán đã học. Thuật toán bạn áp dụng có tên là gì b 1 điểm . Hãy nêu và chứng minh độ phức tạp tính toán của thuật toán bạn sử dụng trong câu a cho trường hợp tổng quát với đầu vào là một đồ thị đầy đủ có n đỉnh. Bài 3 2 điểm . Hãy sử dụng một thuật toán đã học tìm đường đi ngắn nhất từ đỉnh a đến đỉnh h trong đồ thị sau 1 b e 2 2 8 4 6 2 3 a c f h 1 5 4 1 d g 6 1 Bài 4 1 điểm . a điểm Hãy nêu định nghĩa của bài toán ghép cặp hoàn hảo có trọng số cực tiểu. b điểm Hãy viết mô hình tối ưu nguyên cho bài toán trong câu a. Bài 5 3 1 điểm . a 2 điểm Hãy tìm luồng cực đại và lát cắt cực tiểu của bài toán sau s là đỉnh nguồn t là đỉnh đích 22 a d 25 18 2 1 3 3 2 s b e t 14 3 21 c f 5 b 1 điểm Bạn được phép tăng dung tích của một cạnh trong mạng trên lưu ý không được thêm cạnh chưa tồn tại . Bạn sẽ thay đổi dung tích của cạnh nào
