Đề kiểm tra giữa kỳ môn Mô hình hóa toán học năm 2016 - Mã đề 1631 - Đại học Bách khoa thành phố Hồ Chí Minh
TRƯỜNG ĐHBK TP. HCM
BÀI KIỂM TRA GIỮA KỲ
KHOA KH&KT MÁY TÍNH
Môn: MÔ HÌNH HÓA TOÁN HỌC
(CO2011)
Lớp: TNMT
Nhóm: A01
Thời gian làm bài: 60 phút
(Không được sử dụng tài liệu)
Ngày kiểm tra: 16/03/2016
Họ & tên SV:
Điểm số:
MSSV:
GV chấm bài:
Chữ ký GV:
Điểm chữ:
(Bài KT có 20 câu hỏi trắc nghiệm, mỗi câu có điểm số là 0.5. Tô đậm phương án trả lời đúng: ꢀ;
gạch chéo nếu muốn bỏ để chọn lại phương án khác: ꢀ.)
@
Câu 1. Trong một nghiệm chấp nhận được của bài toán LP tìm được bởi thuật toán đơn hình, các biến
giả (artificial variables) đều
ꢀ ¨
ꢀ ¨
A
B bằng 0.
ꢁ ©
ꢀ ¨
ꢁ ©
ꢀ ¨
C âm.
D không cần thỏa điều kiện nào cả.
ꢁ ©
ꢁ ©
Câu 2. Bước đầu tiên trong phương pháp nhánh-cận (branch and bound) trong việc giải bài toán quy
hoạch nguyên là để ...
ꢀ ¨
ꢀ ¨
A
B đổi các hệ số trong hàm mục tiêu sang số nguyên.
ꢁ ©
ꢀ ¨
ꢁ ©
C giải bài toán gốc bằng cách giải bài toán quy hoạch tuyến tính nhưng cho phép xét nghiệm không nguyên.
ꢁ ©
ꢀ ¨
D so sánh cận dưới (lower bound) với một cận trên (upper bound) chọn trước.
ꢁ ©
Câu 3. Công thức logic vị từ nào sau đây không là hằng đúng?
I. ∀xP(x) ∨ ∀xQ(x) −→ ∀x(P(x) ∨ Q(x)).
II. ∃xP(x) ∨ ∃xQ(x) −→ ∃x(P(x) ∨ Q(x)).
III. ∀x(P(x) → Q(x)) −→ (∀xP(x) → ∀xQ(x)).
IV. ∃x(P(x) → Q(x)) −→ (∃xP(x) → ∃xQ(x)).
ꢀ ¨
ꢀ ¨
A Công thức I.
C Công thức III.
B
ꢁ ©
ꢀ ¨
ꢁ ©
ꢀ ¨
D Công thức IV.
ꢁ ©
ꢁ ©
Câu 4. Xét biểu thức vị từ φ sau
ꢀ
ꢃ
ꢁ
ꢂ
∀z Q(x) ∧ ∀x P(z) → R(x) ∧ R(z) → R(x) ∧ P(x).
ꢄ
ꢅ
Kết quả của phép thay thế (substitution) x ⇒ f(x, y, z)) φ là gì?
ꢀ
ꢃ
ꢀ ¨
ꢁ
ꢁ
ꢂ
ꢂ
A ∀z0 Q(f(x, y, z)) ∧ ∀x P(z) → R(f(x, y, z)) ∧ R(z0) → R(f(x, y, z)) ∧ P(f(x, y, z)).
ꢁ ©
ꢀ ¨
ꢀ
ꢃ
ꢁ
ꢂ
B ∀z0 Q(f(x, y, z)) ∧ ∀x P(z0) → R(x) ∧ R(z0) → R(f(x, y, z)) ∧ P(f(x, y, z)).
ꢁ ©
ꢀ ¨
ꢀ
ꢃ
C ∀z0 Q(f(x, y, z)) ∧ ∀x0 P(z0) → R(f(x, y, z)) ∧ R(z0) → R(f(x, y, z)) ∧ P(f(x, y, z)).
ꢁ ©
ꢀ ¨
ꢀ
ꢃ
ꢁ
ꢂ
D ∀z Q(f(x, y, z0)) ∧ ∀x0 P(z) → R(f(x0, y, z0)) ∧ R(z0) → R(f(x, y, z0)) ∧ P(f(x, y, z)).
ꢁ ©
Chữ ký SV: . . . . . . . . . . . . . . . . . .
Mã đề 1631
Trang 1
Câu 5. Trong kỳ Hoa Sơn luận võ, năm vị cao thủ đã gặp nhau để xác định danh hiệu đệ nhất: Đông
Tà, Tây Độc, Nam Đế, Bắc Cái và Trung Thần Thông. Để phân biệt thắng thua thì họ đấu từng
cặp đôi và không giới hạn thời gian. Nhà vô địch là người có nhiều trận thắng nhất. Đông Tà
không thể đánh bại Nam Đế, nhưng ông ta đã đánh bại Tây Độc. Do dùng nhiều sức trong mỗi
trận đấu nên Nam Đế chỉ thắng hai trận đầu tiên. Bắc Cái chỉ thắng được Nam Đế.Tây Độc
không thể chiến thắng Trung Thần Thông, nhưng lại chiến thắng Nam Đế và Bắc Cái. Riêng
Trung Thần Thông chỉ bị thất bại một trận đấu.
Hãy cho biết Trung Thần Thông đã bị đánh bại bởi vị nào?
ꢀ ¨
ꢀ ¨
A Nam Đế
B Nam Đế hoặc Đông Tà
ꢁ ©
ꢀ ¨
ꢁ ©
ꢀ ¨
C Đông Tà
D Tây Độc
ꢁ ©
ꢁ ©
Câu 6. Xét hai biểu thức mệnh đề sau:
φ = p ∧ q,
Khẳng định nào sau đây là đúng?
ψ = r → (p ∧ q).
ꢀ ¨
ꢀ ¨
A Nếu một phép gán chân trị làm cho ψ sai
B Nếu một phép gán chân trị làm cho ψ đúng
ꢁ ©
ꢁ ©
thì phép gán này cũng làm cho φ đúng.
thì phép gán này cũng làm cho φ đúng.
ꢀ ¨
ꢀ ¨
C N
D Nếu một phép gán chân trị làm cho φ đúng
ꢁ ©
ꢁ ©
thì phép gán này cũng làm cho sai.
thì phép gán này cũng làm cho ψ đúng.
Các câu 7–8 dùng chung dữ kiện sau. Một dự án gồm các công việc A, B, C, D, E, F và G cần thực
hiện. Thời lượng (theo ngày) cần thiết để xử lý các công việc lần lượt là , p
pD = 7, pE = 9, pF = 6 và pG = 2.
Ta ký hiệu
X1 + X2 + . . . + Xn ꢀ Y1 + Y2 + . . . + Ym + c
để biểu diễn các công việc Xi (i = 1, . . . , n) đều cần hoàn thành trước khi khởi động các công việc Yk
(k = 1, . . . , m) một khoảng thời gian c ngày.
Xét thời gian bắt đầu khởi động dự án là 0. Dự án được gọi là “kết thúc” khi tất cả các công việc
trong dự án đều hoàn thành.
Câu 7. Biết rằng: ꢀ ꢀ ; ꢀ ; E ꢀ F. Hỏi dự án này sẽ kết thúc sớm
nhất vào ngày nào?
A 2
ꢀ ¨
ꢀ ¨
ꢀ ¨
ꢀ ¨
B 28
C 36
D 5
ꢁ ©
ꢁ ©
ꢁ ©
ꢁ ©
Câu 8. Biết rằng: ꢀ ; ꢀ ; C + E ꢀ F + G + 1; F ꢀ G + 3. Dự án này sẽ
kết thúc sớm nhất vào ngày nào?
ꢀ ¨
ꢀ ¨
ꢀ ¨
ꢀ ¨
A 16
B 23
C 26
D 20
ꢁ ©
ꢁ ©
ꢁ ©
ꢁ ©
Câu 9. Công thức nào sau đây không biểu diễn đúng phát biểu tương ứng?
ꢀ ¨
ꢀ ¨
A “Một kẻ tấn công có thể khiến
B “
ꢁ ©
ꢁ ©
cho một máy chủ nhầm tưởng rằng
việc đăng nhập là thành công, ngay
cả khi việc đó không xảy ra:”
φ := ∃a∃s(((loggedIn_gia(a, s))) −→
”
∀∧ ¬−→
_
loggedIn(a, s)).
ꢀ ¨
ꢀ ¨
C “Có những môn học thú vị trong
D “Một kẻ tấn công có thể ghi đè dữ
ꢁ ©
ꢁ ©
ngành CS mà số sinh viên theo
học lại ít hơn so với một số môn
học không thú vị:” ∃x∃y((Thu_vi(x) ∧
¬Thu_vi(y)) −→ It_hon(x, y)).
liệu lên thông tin của một người
dùng nào đó trên máy chủ:” φ :=
∃u∃c∃s∃d((¬ownsCredentials(u, c)) −→
canWrite(u, c, s, d)).
Chữ ký SV: . . . . . . . . . . . . . . . . . .
Mã đề 1631
Trang 2
Câu 10. Cứ vào ngày 01 tháng 06 hàng năm, ở giữa một cái ao tròn ở Nam Mỹ xuất hiện một đoá hoa
Victoria Regia. Thân hoa mọc từ dưới đáy ao lên, còn các cánh hoa thì nằm trên mặt nước
giống như các hoa súng. Mỗi ngày diện tích của đoá hoa tăng gấp đôi, và cuối cùng vào ngày 01
tháng 07, nó phủ cả mặt hồ, các cánh hoa rơi ra, còn hạt thì chìm xuống đáy. Hỏi vào ngày nào
thì diện tích của đóa hoa chiếm một nửa diện tích của ao ?
ꢀ ¨
ꢀ ¨
ꢀ ¨
ꢀ ¨
A ngày 15 tháng 06
B ngày 07 tháng 06
C ngày 24 tháng 06
D ngày 30 tháng 06
ꢁ ©
ꢁ ©
ꢁ ©
ꢁ ©
Câu 11. Công thức nào sau đây tương đương với φ1 −→ φ2 −→ φ3?
ꢀ ¨
ꢀ ¨
A φ1 ∨ φ2 −→ φ3.
B φ1 −→ φ2 ∧ φ3.
ꢁ ©
ꢁ ©
ꢀ ¨
ꢀ ¨
C φ2 −→ φ1 −→ φ3
D −→ −→
ꢁ ©
ꢁ ©
Câu 12. Loan sở hữu 15 mẫu đất trồng trọt. Cô ấy muốn trồng lúa mì hoặc ngô trên mảnh đất này.
Mảnh đất có thể cho lợi nhuận là 80 triệu đồng/mẫu lúa mì hoặc 50 triệu/mẫu ngô. Các lao
động và phân bón được sử dụng cho mỗi mẫu được liệt kê trong bảng dưới đây.
Loại cây trồng
lúa mì
Nhân công/mẫu 3 công nhân 2 công nhân
Phân bón/mẫu 5 tạ 10 tạ
ngô
Hiện tại trên mảnh đất có sẵn 100 tạ phân bón và có 30 công nhân làm việc. Xét X và Y lần
lượt là số lượng mẫu trồng lúa mì và ngô (giả sử ta chỉ xét X, Y ∈ N). Khi đó, Các giá trị có
thể có của X là
ꢀ ¨
ꢀ ¨
ꢀ ¨
ꢀ ¨
A 10.
B 11.
C 15.
D 16.
ꢁ ©
ꢁ ©
ꢁ ©
ꢁ ©
Câu 13. Khi dùng phương pháp nhánh-cận (branch-and-bound method) để giải bài toán quy hoạch
nguyên trong mô hình cực đại hóa, ta sẽ dừng việc phân nhánh khi
ꢀ ¨
ꢀ ¨
ꢀ ¨
A giá trị của hàm mục tiêu là 0.
B
ꢁ ©
ꢁ ©
hoặc tìm được nghiệm nguyên.
ꢀ ¨
C cận trên (upper bound) mới tìm được lớn
D cận dưới (lower bound) bằng 0.
ꢁ ©
ꢁ ©
hơn cận dưới (lower bound).
Trong hai câu 14–15, ta sử dụng cùng các thông tin và ký hiệu sau:
P là tập sinh viên trường BK,
B là tập hợp quyển sách trong thư viện trường BK,
Bor(p, b) là vị từ “sinh viên p đang mượn quyển sách b”,
Over(b) là vị từ “quyển sách b bị (mượn) quá hạn”.
Câu 14. Phát biểu “Quyển sách b ở trên giá sách.” có biểu diễn hình thức sau:
ꢀ ¨
ꢀ ¨
A ∃p ∈ P : Bor(p, b)
ꢁ ©
B ∃p ∈ P : Bor(p, b)
ꢁ ©
ꢁ ©
ꢀ ¨
ꢁ ©
ꢀ ¨
C ∀p ∈ P : Bor(p, b)
D ∀p ∈ P : Bor(p, b)
Câu 15. Câu “Nếu quyển sách b bị quá hạn, thì nó đã đang được mượn.” có thể có biểu diễn hình thức
sau:
ꢀ ¨
A (∃p ∈ P : Bor(p, b)) → Over(b)
ꢁ ©
ꢀ ¨
B [ ∀p ∈ P : Bor(p, b) ] → Over(b)
ꢁ ©
ꢀ ¨
C Over(b) → ∃p ∈ P : Bor(p, b)
ꢁ ©
ꢀ ¨
D Over(b) → ∃p1 = p2 : Bor(p1, b) ∧ Bor(p2, b)
ꢁ ©
Câu 16. Để chuyển một ràng buộc nhỏ hơn hoặc bằng về dạng chính tắc trong thuật toán đơn hình ta phải
ꢀ ¨
ꢀ ¨
A thêm vào một biến giả mới.
B trừ đi một biến giả mới.
ꢁ ©
ꢁ ©
ꢀ ¨
C trừ đi hoặc thêm vào một biến giả mới tùy thuộc vào bài toán MIN hay MAX.
ꢁ ©
ꢀ ¨
D t
ꢁ ©
Chữ ký SV: . . . . . . . . . . . . . . . . . .
Mã đề 1631
Trang 3
Câu 17. Giả sử Xi (i = 1, 2) là 1 nếu dự án i được triển khai, và là 0 nếu ngược lại. Để đảm bảo rằng Dự án
1 không thể được triển khai trừ khi Dự án 2 cũng phải được triển khai. Ràng buộc nào dưới đây thể
hiện được yêu cầu này?
ꢀ ¨
ꢀ ¨
ꢀ ¨
ꢀ ¨
A − ≤
B X1 − X2 = 1.
C X1 + X2 = 1.
D X1 + X2 ≤ 1.
ꢁ ©
ꢁ ©
ꢁ ©
ꢁ ©
Câu 18. Giả sử ta đang chứng minh tính đúng đắn (validity) của phép suy luận (sequent)
∀xP(x), ∃xQ(x) ` ∀y(P(y) ∧ Q(y))
theo sơ đồ sau.
1
2
∀xP(x)
∃xQ(x)
tiền đề (premise)
tiền đề (premise)
3
x0 P(x0)
∀e 1
4
x0 Q(x0)
giả thiết (assump-
tion)
5
P(x0) ∧ Q(x0)
∧i 3,4
∃e 2, 4–5
∀i 3–6
6
P(x0) ∧ Q(x0)
7
∀y(P(y) ∧ Q(y))
Khẳng định nào dưới đây là đúng?
ꢀ ¨
ꢀ ¨
A Đây không phải là một chứng minh đúng
B Đây không phải là một chứng minh đúng
ꢁ ©
ꢁ ©
vì Dòng 2 không được dùng cùng biến với
vì Dòng 6 nằm trong khung nhưng có sử
dụng Dòng 2 nằm bên ngoài khung.
Dòng 1; mà phải viết là ∃zQ(z).
ꢀ ¨
ꢀ ¨
C Đây không phải là một chứng minh đúng
D Đây không phải là một chứng minh đúng
ꢁ ©
ꢁ ©
vì cả hai Dòng 3 và Dòng 4 đều đưa vào
vì biến y chỉ được đưa vào trong Dòng 7
mà không nằm trong khung.
cùng một biến x0.
Câu 19. Khi dùng thuật toán đơn hình để giải bài toán MAX ta thấy rằng khi tất cả tỉ số ∆ trong dòng dùng
để chọn các phần tử trụ (pivot) đều âm thì
ꢀ ¨
ꢀ ¨
A nghiệm se tối ưu (optimal).
B nghiệm không bị chặn (unbounded).
ꢁ ©
ꢀ ¨
ꢁ ©
ꢀ ¨
C nghiệm suy biến (degenerate)
D nghiệm không chấp nhận được (infeasible)
ꢁ ©
ꢁ ©
Câu 20. Ràng buộc
3q
3p
X
X
xijk = 1, ∀k = 1 : n; p, q = 1 : 3
j=3q−2 i=3p−2
muốn diễn tả điều kiện gì trong bài toán Sudoku?
ꢀ ¨
ꢀ ¨
A Các số từ 1 đến 9 xuất hiện đúng một lần
B Không điều kiện nào cả.
ꢁ ©
ꢁ ©
trên từng ô vuông 3x3, nhưng trong ràng
buộc có một sai sót nhỏ.
ꢀ ¨
ꢀ ¨
C Các số từ 1 đến 9 xuất hiện đúng một lần
D Các phương án còn lại đều sai.
ꢁ ©
ꢁ ©
trên từng ô vuông 3x3.
Chữ ký SV: . . . . . . . . . . . . . . . . . .
Mã đề 1631
Trang 4
4 trang
21840
Free
Bạn đang xem tài liệu "Đề kiểm tra giữa kỳ môn Mô hình hóa toán học năm 2016 - Mã đề 1631 - Đại học Bách khoa thành phố Hồ Chí Minh", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- de_kiem_tra_giua_ky_mon_mo_hinh_hoa_toan_hoc_nam_2016_ma_de.pdf
