zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Khoa Học Tự Nhiên

Đề thi kết thúc học kỳ II năm học 2021-2022 môn Tối ưu rời rạc - ĐH Khoa học Tự nhiên

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:2

Báo xấu

47
lượt xem 4
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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ả.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Đề thi kết thúc học kỳ II năm học 2021-2022 môn Tối ưu rời rạc - ĐH Khoa học Tự nhiên

TailieuVNU.com ĐẠ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 (1.5 đ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 (2.5 đ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 43.8 117.9 94.1 83.8 Bắc Ninh - 0 138.9 128.1 133.1 Hải Phòng - - 0 171.0 229.5 Ninh Bình - - - 0 172.1 Phú Thọ - - - - 0 a) (1.5 đ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
TailieuVNU.com Bài 4 (1 điểm). a) (0.5 đ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) (0.5 đ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 và tăng lên bao nhiêu để luồng cực đại tăng lên nhiều nhất? Hãy giải thích rõ cho câu trả lời của bạn (không giải thích hay giải thích không thuyết phục sẽ không được điểm). c) (1 điểm) Câu hỏi thưởng điểm: Hãy viết mô hình quy hoạch nguyên của bài toán lát cắt cực tiểu cho mạng trong trường hợp tổng quát. 2

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.