Đề thi cuối kỳ môn Mô hình hóa toán học năm 2016 - Mã đề 1728 (L01,02,03) - Đại học Bách khoa thành phố Hồ Chí Minh
TRƯỜNG ĐHBK TP. HCM
ĐỀ THI CUỐI KỲ
Môn: Mô hình hóa toán học (CO2011)
Thời gian làm bài: 90 phút
KHOA KH&KT MÁY TÍNH
(SV được sử dụng một tờ A4
chứa các ghi chú cần thiết)
Ngày thi: 30/05/2018
Họ & tên SV:
Điểm số:
MSSV:
GV chấm bài:
Chữ ký:
Điểm chữ:
(Kết quả thi sẽ được quy về thang điểm 10 dựa vào kết quả của sinh viên làm bài tốt nhất. Sinh viên
không được viết nháp vào đề và hãy chọn đáp án chính xác nhất cho mỗi câu hỏi trắc nghiệm và trả
lời vào trong phiếu.)
Câu 1. Phát biểu nào sau đây không đúng?
ꢀ ¨
A Biểu thức (term) t là tự do đối với biến x trong một công thức logic vị từ φ nếu
ꢁ ©
không tồn tại các công thức con ∀y(· · · ) hoặc ∃y(· · · ) trong φ sao cho y xuất hiện
(occur) trong t.
ꢀ ¨
B Biểu thức (term) t là tự do đối với biến x trong một công thức logic vị từ φ, nếu
ꢁ ©
không tồn tại các công thức con ∀x(· · · ) hoặc ∃x(· · · ) trong φ.
ꢀ ¨
C Biểu thức (term) t là tự do đối với biến x trong một công thức logic vị từ φ, if t
ꢁ ©
không chứa biến nào.
ꢀ ¨
D Biểu thức (term) t là tự do đối với biến x trong một công thức logic vị từ φ nếu x
ꢁ ©
là biến duy nhất trong t.
Câu 2. Công thức logic vị từ nào sau đây không là hằng đúng?
I. ∀x(P(x) ∧ Q(x)) −→ ∀xP(x) ∧ ∀xQ(x).
II. ∃x(P(x) ∧ Q(x)) −→ ∃xP(x) ∧ ∃xQ(x).
III. (∀xP(x) → ∀xQ(x)) −→ ∀x(P(x) → Q(x)).
IV. (∃xP(x) → ∃xQ(x)) −→ ∃x(P(x) → Q(x)).
ꢀ ¨
ꢀ ¨
A Công thức II.
B Công thức I.
ꢁ ©
ꢀ ¨
ꢁ ©
ꢀ ¨
C
D Công thức IV.
ꢁ ©
ꢁ ©
Câu 3. Xết một hệ thống logic vị từ gồm (F, P), với F = ∅ và P = {P}, trong đó P là một vị từ ba
biến. Hơn nữa, xét công thức φ:
∀x∀y∃z P(x, y, z)
và một mô hình M sao cho AM = {a, b} và PM = {(a, a, b), (a, b, a), (a, b, b), (b, b, a), (b, b, b)}.
ꢀ ¨
Phát biểu nào sau dây đúng?
A φ không phải là một công thức trên hệ thống (F, P).
ꢁ ©
ꢀ ¨
B M là một mô hình cho (F, P) và φ là một công thức trên (F, P), nhưng M không
ꢁ ©
thỏa được φ.
ꢀ ¨
C M không phải là một mô hình cho (F, P).
ꢁ ©
ꢀ ¨
D M là một mô hình cho (F, P) và φ là một công thức trên (F, P), và M thỏa được φ.
ꢁ ©
Chữ ký SV: . . . . . . . . . . . . .
Mã đề 1728 (L01,02,03)
Trang 1/6
Câu 4. Công thức nào sau đây diễn tả chính xác nhất phát biểu sau
“Khi một ngân hàng gặp khó khăn về tính thanh khoản (t) thì cả hệ thống tài
chính sẽ bị ảnh hưởng (c) trừ khi Ngân hàng Nhà nước đứng ra mua lại nó với giá 0
đồng (b) .”
ꢀ ¨
ꢀ ¨
ꢀ ¨
ꢀ ¨
A (¬c → b) → t.
B → ¬→
C (c ∧ ¬b) → ¬t.
D (c ∧ ¬b) → t.
ꢁ ©
ꢁ ©
ꢁ ©
ꢁ ©
Câu 5. Luật đúng đắn bộ phận (partial correctness) cho cấu trúc while được phát biểu như sau
ꢀ ¨
ꢀ ¨
(|φ ∧ B|) C (|ψ|)
(|φ ∧ B|) C (|ψ|)
A
.
B
.
ꢁ ©
ꢁ ©
(|φ|) while B { C } (|ψ|)
(|φ|) while B { C } (|ψ ∧ ¬B|)
ꢀ ¨
ꢀ ¨
(|ψ ∧ B|) C (|ψ|)
(|ψ ∧ B|) C (|ψ|)
C
.
D
.
ꢁ ©
ꢁ ©
(|ψ|) while B { C } (|ψ|)
(|ψ|) while B { C } (|ψ ∧ ¬B|)
Câu 6. Tiền điều kiện yếu nhất (weakest precondition) φ của bộ ba Hoare
(|φ|) if (x < y) x = x + 3; else x = x + 1; (|x ≤ y|)
là
ꢀ ¨
ꢀ ¨
A y ≥ x.
B (y > x) −→ (x + 3 < y).
ꢁ ©
ꢁ ©
ꢀ ¨
ꢁ ©
ꢀ ¨
C y ≥ x + 1.
D y ≥ x + 3.
ꢁ ©
Câu 7. Công thức vị từ nào sau đây là phủ định của công thức sau?
∃C > 0, ∃d ∈ N, ∃m ∈ N, ∀n ∈ N(n ≥ m =⇒ |T(n)| < C × nd)?.
ꢀ ¨
A ∀C > 0, ∀d ∈ N, ∀m ∈ N, ∃n ∈ N(n ≥ m =⇒ |T(n)| > C × nd).
ꢁ ©
ꢀ ¨
B ∀C > 0, ∃d ∈ N, ∀m ∈ N, ∃n ∈ N(n ≥ m ∧ |T(n)| > C × nd).
ꢁ ©
ꢀ ¨
C ∀C > 0, ∀d ∈ N, ∀m ∈ N, ∃n ∈ N(n ≥ m ∧ |T(n)| ≥ C × nd).
ꢁ ©
ꢀ ¨
D ∀C > 0, ∀d ∈ N, ∀m ∈ N, ∃n ∈ N(n < m ∧ |T(n)| ≥ C × nd).
ꢁ ©
Câu 8. Phát biểu nào sau đây đúng cho tính đúng đắn (correctness) đối với các bộ ba Hoare, trong đó
downfac là chương trình như trong Câu 25?
ꢀ ¨
A |=par (|>|) if (b > 0) {c = a + b} else c = a − b (|ψ|), và |=par (|>|) downfac (|y = x!|).
ꢁ ©
ꢀ ¨
B |=par (|>|) if (b > 0) {c = a + b} else c = a − b (|ψ|), và |=tot (|>|) downfac (|y = x!|).
ꢁ ©
ꢀ ¨
C |=tot (|>|) if (b > 0) {c = a + b} else c = a − b (|ψ|), và |=tot (|>|) downfac (|y = x!|).
ꢁ ©
ꢀ ¨
D |=tot (|>|) if (b > 0) {c = a + b} else c = a − b (|ψ|), và |=par (|>|) downfac (|y = x!|).
ꢁ ©
Câu 9.
Precondition của While
r := 1;
i := 0;
while i < m do
r := r ∗ n;
i := i + 1
sẽ là
ꢀ ¨
ꢀ ¨
A m > 0.
B (m ≥ 0) ∧ (n ≥ 0).
ꢁ ©
ꢁ ©
ꢀ ¨
ꢁ ©
ꢀ ¨
C (m > 0) ∧ (n > 0).
D (m ≥ 0) ∧ (n > 0).
ꢁ ©
Câu 10. Một bể nước hình trụ, bán kính 5m, chiều cao 20m đang được tháo nước ở dưới đáy bể. Lượng
√
nước thoát ra với vận tốc trung bình 0.5 h m3/min (h là chiều cao bể nước). Hỏi sau bao lâu
thì bể nước sẽ cạn?
ꢀ ¨
ꢀ ¨
ꢀ ¨
ꢀ ¨
A ≈ 400.862 phút.
B ≈ 620 phút.
C ≈ 1404.962 phút.
D ≈ 20 giờ.
ꢁ ©
ꢁ ©
ꢁ ©
ꢁ ©
Chữ ký SV: . . . . . . . . . . . . .
Mã đề 1728 (L01,02,03)
Trang 2/6
Câu 11. Hãy biểu thị phát biểu “Hiệu của hai số nguyên âm không nhất thiết phải là số nguyên âm” bằng
logic vị từ với vũ trụ là tập các số nguyên.
ꢀ ¨
ꢀ ¨
A ∃m∀n(m < 0 ∧ n < 0 ∧ ¬(m − n < 0)).
B ∀m∀n(m < 0 ∧ n < 0 ∧ ¬(m − n < 0)).
ꢁ ©
ꢁ ©
ꢀ ¨
ꢁ ©
ꢀ ¨
C ∃∃∧ ∧ ¬−
D ∃m∀n(m ∧ n ∧ ¬(m − n < 0)).
ꢁ ©
Câu 12. Trong phương pháp đơn hình, số gia hàm mục tiêu rN = cTN − cBT B−1N dùng để
ꢀ ¨
A kết luận miền phương án là rỗng hay không.
ꢁ ©
ꢀ ¨
B k
ꢁ ©
ꢀ ¨
C tính một điểm cực biên của miền phương án.
ꢁ ©
ꢀ ¨
D tìm một cơ sở của bài toán.
ꢁ ©
Câu 13. Một ao cá có sức chứa 1000 con cá. Tại thời điểm ban đầu người ta thả 100 con cá và nhận thấy
rằng sau hai năm thì số cá là 300 con. Giả sử sự gia tăng lượng cá thỏa mô hình tăng trưởng
logistic. Hãy xác định số cá sau 5 năm?
ꢀ ¨
ꢀ ¨
ꢀ ¨
ꢀ ¨
A ≈ 755.
B ≈ 665.
C ≈ 645.
D ≈ 765.
ꢁ ©
ꢁ ©
ꢁ ©
ꢁ ©
Câu 14. 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 X1 − X2 = 1.
B X1 − X2 ≤ 0.
C X1 + X2 = 1.
D X1 + X2 ≤ 1.
ꢁ ©
ꢁ ©
ꢁ ©
ꢁ ©
Câu 15. Trong tiếp cận nhánh-cận (branch and bound) giải bài toán quy hoạch tuyến tính với biến
nguyên, nếu một nghiệm tối ưu của bài toán quy hoạch tuyến tính, thu được từ việc làm nhẹ
bài toán gốc, là nguyên thì nó là
ꢀ ¨
ꢀ ¨
A nghiệm tối ưu của bài toán gốc.
B
ꢁ ©
ꢁ ©
ꢀ ¨
ꢀ ¨
C một nghiệm không chấp nhận được của
D một nghiệm suy biến của bài toán gốc.
ꢁ ©
ꢁ ©
bài toán gốc.
Câu 16. Phát biểu nào sau đây thể hiện tính không giải được (undecidability) của hệ thống logic vị từ?
ꢀ ¨
A Trong logic vị từ, tồn tại một công thức sao cho nó vừa là đúng đắn vừa là không
ꢁ ©
đúng đắn.
ꢀ ¨
B T
ꢁ ©
bt ì lđg đn hy kôg
ꢀ ¨
C Trong logic vị từ, có một công thức đúng đắn nhưng không tồn tại thuật toán để
ꢁ ©
kiểm tra tính đúng đắn của nó.
ꢀ ¨
D Trong logic vị từ, không tồn tại thuật toán để quyết định xem liệu một mô hình nào
ꢁ ©
đó có thỏa được một công thức cho trước hay không.
Câu 17. Cho C(x) là vị từ “x đang ở đúng vị trí’, E(x) là vị từ “x vẫn còn tốt’. Với vũ trụ là tập tất cả
các vật dụng, phát biểu nào sau đây biểu thị cho công thức vị từ sau?
(∃x(¬C(x) ∧ E(x))) ∧ ∀y((¬C(y) ∧ E(y)) =⇒ (x = y)).
ꢀ ¨
ꢁ ©
ꢀ ¨
ꢁ ©
A Cỉ ộđậhnhi ag ở đng
v
C Có một trong số các đồ vật không phải
B Một trong số các đồ vật đang ở đúng vị
ꢁ ©
ꢁ ©
trí và vẫn còn tốt.
ꢀ ¨
ꢀ ¨
D Chỉ có một trong số các đồ vật đang ở
đang ở đúng vị trí nhưng vẫn còn tốt.
đúng vị trí nhưng nó không còn tốt.
Chữ ký SV: . . . . . . . . . . . . .
Mã đề 1728 (L01,02,03)
Trang 3/6
Câu 18. Nhắc lại rằng một công logic thức mệnh đề D được gọi là có dạng chuẩn tuyển (disjunctive
normal form - DNF) nếu như nó là tuyển của các mệnh đề con dạng hội (conjunctive clauses),
trong đó mỗi mệnh đề con dạng hội C là hội của các “literals” (các biến mệnh đề hoặc phủ định
của nó). Chính xác hơn, ta định nghĩa một DNF dưới dạng sau BNF như sau:
L ::= p | ¬p
C
::= L | L ∧ C
D ::= C | C ∨ D.
Khẳng định nào dưới đây về các mệnh đề con dạng hội L1 ∧ L2 ∧ · · · ∧ Lm là đúng?
ꢀ ¨
A Một mệnh đề con dạng hội L1 ∧ L2 ∧ · · · ∧ Lm là đúng đắn khi và chỉ khi tồn tại i, j
ꢁ ©
với 1 ≤ i, j ≤ m sao cho Li is ¬Lj.
ꢀ ¨
B Một mệnh đề con dạng hội L1 ∧ L2 ∧ · · · ∧ Lm là không thỏa được khi và chỉ khi tồn
ꢁ ©
tại i, j với 1 ≤ i, j ≤ m sao cho Li is ¬Lj.
ꢀ ¨
C Một mệnh đề con dạng hội L1 ∧ L2 ∧ · · · ∧ Lm là thỏa được khi và chỉ khi tồn tại
ꢁ ©
i, j với 1 ≤ i, j ≤ m sao cho Li is ¬Lj.
ꢀ ¨
D Một mệnh đề con dạng hội L1 ∧ L2 ∧ · · · ∧ Lm là không thỏa được khi và chỉ khi với
ꢁ ©
mọi i với 1 ≤ i ≤ m sao Li là một biến mệnh đề, tồn tại j với 1 ≤ j ≤ m sao cho Lj
is ¬Li.
Câu 19. Dạng bất biến (invariant form) của chương trình While như trong Câu 9 mà có thể dùng trong
việc chứng minh tính đúng đắn của nó là sẽ là
ꢀ ¨
ꢀ ¨
A (r = ni) ∧ (0 ≤ i ≤ m) ∧ (n ≥ 0).
B (r = ni) ∧ (0 ≤ i ≤ m).
ꢁ ©
ꢁ ©
ꢀ ¨
ꢁ ©
ꢀ ¨
C (r = ni) ∧ (n > 0).
D (r = ni) ∧ (0 ≤ i ≤ m) ∧ (n > 0).
ꢁ ©
Câu 20. Luật đúng đắn toàn phần (total correctness) cho cấu trúc while được phát biểu như sau
ꢀ ¨
ꢀ ¨
(|φ ∧ B ∧ 0 ≤ E|) C (|ψ ∧ 0 ≤ E|)
(|φ ∧ B ∧ 0 ≤ E = E0|) C (|ψ ∧ 0 ≤ E < E0|)
A
.
B
.
ꢁ ©
ꢁ ©
(|φ ∧ 0 ≤ E|) while B { C } (|ψ ∧ ¬B|)
(|φ ∧ 0 ≤ E|) while B { C } (|ψ ∧ ¬B|)
ꢀ ¨
ꢀ ¨
(|ψ ∧ B ∧ 0 ≤ E|) C (|ψ ∧ 0 ≤ E|)
(|ψ ∧ B ∧ 0 ≤ E = E0|) C (|ψ ∧ 0 ≤ E < E0|)
C
.
D
.
ꢁ ©
ꢁ ©
(|ψ ∧ 0 ≤ E|) while B { C } (|ψ ∧ ¬B|)
(|ψ ∧ 0 ≤ E|) while B { C } (|ψ ∧ ¬B|)
Câu 21. Cho P là chương trình x = 2018. Khi đó theo luật gán (assignment rule) ta có
ꢀ ¨
ꢀ ¨
A |=par (|2018 = y|) P (|x = y|).
B |=par (|2018 = 4|) P (|x = 4|).
ꢁ ©
ꢀ ¨
ꢁ ©
ꢀ ¨
C |=par (|2018 = 2018|) P (|x = 2018|).
D |=tot (|2018 = 2018|) P (|x = 2018|).
ꢁ ©
ꢁ ©
Câu 22. Cho F(x, y) là vị từ “x lừa dối y”, với vũ trụ là tập tất cả mọi người trên trái đất. Công thức vị
từ nào sau đây biểu thị cho phát biểu: “Nancy có thể lừa dối được đúng hai người.”
ꢀ ¨
A ∃x∃y, (y = x ∧ F(Nancy, x) ∧ F(Nancy, y) ∨ ∃z(z = x ∨ z = y ∨ F(Nancy, z))) .
ꢁ ©
ꢀ ¨
B ∀x∀y, (y = x ∧ F(Nancy, x) ∧ F(Nancy, y)) .
ꢁ ©
ꢀ ¨
C ∃x∀y, (y = x ∧ F(Nancy, x) ∧ F(Nancy, y) ∧ ∀z(z = x ∨ z = y ∨ ¬F(Nancy, z))) .
ꢁ ©
ꢀ ¨
D ∃x∃y, (y = x ∧ F(Nancy, x) ∧ F(Nancy, y) ∧ ∀z(z = x ∨ z = y ∨ ¬F(Nancy, z))) .
ꢁ ©
Câu 23. Liệu có thể sử dụng một automata hữu hạn đơn định và tối giản để mô tả hệ thống hiển thị
thông tin (mức nhiên liệu, tốc độ di chuyển, vị trí GPS, ngày, giờ) trên mặt biển báo của một
loại phương tiện cơ giới đặc thù chỉ với một nút nhấn không?
ꢀ ¨
A Có thể sử dụng một DFA tối giản gồm ba trạng thái.
ꢁ ©
ꢀ ¨
B Không thể.
ꢁ ©
ꢀ ¨
C Có thể sử dụng một DFA tối giản có hơn ba trạng thái.
ꢁ ©
ꢀ ¨
D Có thể sử dụng một DFA tối giản mà số lượng trạng thái vô hạn.
ꢁ ©
Chữ ký SV: . . . . . . . . . . . . .
Mã đề 1728 (L01,02,03)
Trang 4/6
Câu 24. Tiền điều kiện yếu nhất (weakest precondition) φ của bộ ba Hoare
(|φ|) x = 1; y = x + y (|x ≤ y|)
là
ꢀ ¨
ꢀ ¨
A y ≥ x ≥ 0.
B y > x > 0.
ꢁ ©
ꢀ ¨
ꢁ ©
ꢀ ¨
C y > 0.
D y ≥ 0.
ꢁ ©
ꢁ ©
Câu 25.
Một dạng bất biến (invariant form) của chương trình downfac
mà ta có thể dùng trong việc chứng minh tính đúng đắn của nó là
ꢀ ¨
ꢀ ¨
A (y = (x − a)!) ∧ (a ≤ x).
C (y = ) ∧ (a ≤ x).
B (y = (x − a)!) ∧ (a ≥ 0).
ꢁ ©
ꢀ ¨
ꢁ ©
ꢀ ¨
x!
x!
D (y = ) ∧ (a ≥ 0).
ꢁ ©
ꢁ ©
a!
a!
Câu 26. Trong phương pháp đơn hình, giá trị số gia hàm mục tiêu tương ứng các biến cơ sở
ꢀ ¨
ꢀ ¨
ꢀ ¨
ꢀ ¨
A không âm.
B lớn hơn không.
C
D bé hơn không.
ꢁ ©
ꢁ ©
ꢁ ©
ꢁ ©
Câu 27. 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 c
ꢁ ©
hoặc tìm được nghiệm nguyên.
ꢀ ¨
B giá trị của hàm mục tiêu là 0.
ꢁ ©
ꢀ ¨
C cận trên (upper bound) mới tìm được lớn hơn cận dưới (lower bound).
ꢁ ©
ꢀ ¨
D cận dưới (lower bound) bằng 0.
ꢁ ©
Câu 28. Chuỗi nào dưới đây không thuộc vào ngôn ngữ L∗ với L được biểu diễn bởi automata dưới đây.
b
a
a
A
B
F
C
D
a
a
a
b
b
b
E
G
b
ꢀ ¨
ꢀ ¨
ꢀ ¨
ꢀ ¨
A aaaabb
B aababba
C abaababab
D bbaaaa
ꢁ ©
ꢁ ©
ꢁ ©
ꢁ ©
Câu 29. Cho hàm sản xuất Q = A(t)KαLβ(0 < α, 1 > β) với K = K0 + at(K0, a > 0) là hàm vốn,
L = L0 + bt(L0, b > 0) là hàm lao động, t- biến thời gian, A(t) là hàm số dương và đồng biến
theo t. ∀t ≥ 0, hãy xác định tốc độ biến thiên của Q theo t?
ꢀ ¨
dQ
A
= αA(t)Kα−1Lβa + βA(t)KαLβ−1b ≥ 0.
ꢁ ©dt
ꢀ ¨
dQ
ꢁ ©dt
B
= αA(t)Kα−1Lβa + βA(t)KαLβ−1b + KαLβA0(t).
= αA(t)Kα−1Lβa + βA(t)KαLβ−1b + KαLβA0(t) > 0.
= αA(t)Kα−1Lβa + βA(t)KαLβ−1b+ < 0.
ꢀ ¨
dQ
ꢁ ©dt
C
ꢀ ¨
dQ
ꢁ ©dt
D
Chữ ký SV: . . . . . . . . . . . . .
Mã đề 1728 (L01,02,03)
Trang 5/6
Câu 30. Một công ty đề nghị bạn góp vốn 3500 USD đầu tư một dự án vào đầu năm. Công ty này sẽ trả
cho bạn 750 USD vào mỗi cuối năm, liên tục trong 7 năm. Hãy quy đổi số tiền lợi tức thu được
sau 7 năm về thời điểm gốc (được gọi là NPV), qua đó trả lời xem chúng ta có nên đầu tư và
dự án này không? Biết rằng lãi suất ngân hàng là 9% và sẽ được duy trì trong suốt 7 năm.
ꢀ ¨
A NPV = 112.32 > 0, chúng ta có thể đầu tư dự án này.
ꢁ ©
ꢀ ¨
B NPV = 274.714 > 0, chúng ta có thể đầu tư dự án này.
ꢁ ©
ꢀ ¨
C NPV = -74.14 < 0, chúng ta không nên đầu tư dự án này.
ꢁ ©
ꢀ ¨
D NPV ≈ 0, chúng ta không nên đầu tư dự án này.
ꢁ ©
Chữ ký SV: . . . . . . . . . . . . .
Mã đề 1728 (L01,02,03)
Trang 6/6
6 trang
24660
Free
Bạn đang xem tài liệu "Đề thi cuối kỳ môn Mô hình hóa toán học năm 2016 - Mã đề 1728 (L01,02,03) - Đạ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_thi_cuoi_ky_mon_mo_hinh_hoa_toan_hoc_nam_2016_ma_de_1728.pdf
