Đề thi cuối kỳ môn Mô hình hóa toán học năm 2020 - Mã đề 1913 (B01)

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: 03/01/2020

Họ & tên SV:

MSSV:

(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. 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 = E₀|) C (|ψ ∧ 0 ≤ E < E₀|)

(|ψ ∧ B ∧ 0 ≤ E = E₀|) C (|ψ ∧ 0 ≤ E < E₀|)

A

.

B

.

ꢁ ©

(|φ ∧ 0 ≤ E|) while B { C } (|ψ ∧ ¬B|)

(|ψ ∧ 0 ≤ E|) while B { C } (|ψ ∧ ¬B|)

ꢀ ¨

(|φ ∧ B ∧ 0 ≤ E|) C (|ψ ∧ 0 ≤ E|)

(|ψ ∧ B ∧ 0 ≤ E|) C (|ψ ∧ 0 ≤ E|)

C

.

D

.

ꢁ ©

(|φ ∧ 0 ≤ E|) while B { C } (|ψ ∧ ¬B|)

Câu 2. Xét đoạn chương trình sau.

(|ψ ∧ 0 ≤ E|) while B { C } (|ψ ∧ ¬B|)

Nếu cho biết rằng hậu điều kiện (postcondition) của nó là {x = y} thì điều kiện nào sau

đây là tiền điều kiện (precondition) của nó?

ꢀ ¨

A {x = 2y ∧ y < 2}.

B {x > 2y ∧ y = 2}.

C {x = 2y ∧ y > 2}.

D {x < 2y ∧ y > 2}.

ꢁ ©

Câu 3. Chọn phát biểu đúng.

ꢀ ¨

A Khi đọc một sự kiện từ một trạng thái, NFA không xác định được chắc chắn trạng thái kế tiếp.

ꢁ ©

ꢀ ¨

B NFA không xác định được chắc chắn trạng thái kế tiếp để đơn giản hóa hình vẽ.

ꢁ ©

ꢀ ¨

C NFA thì số trạng thái không xác định còn DFA thì xác định được số trạng thái.

ꢁ ©

ꢀ ¨

D Tổng số trạng thái luôn rút giảm trong quá trình đơn định hóa từ một NFA sang DFA.

ꢁ ©

Trong các câu 4–7, xét automata hữu hạn trên tập ký tự {a, b} bên dưới đây.

a

b

ε

0

1

2

a

b

5

4

3

b

a, ε

a

Câu 4. Hãy cho biết đâu không phải là từ hợp lệ trong automata trên.

ꢀ ¨

A abababa

B bbbbbabaa

C aabbaabbababa

D aabbbbaa

ꢁ ©

Chữ ký SV:. . . . . . . . . . . . . . . . . .

Mã đề 1913 (B01)

Trang 1

Câu 5. Hãy viết biểu thức chính qui cho automata bên trên.

ꢀ ¨

A X = a^∗ba^∗; Y = b^∗ab^∗a ; Z = X(Y (a + b)X)^∗+ XY ((a + b)XY )^∗

ꢁ ©

ꢀ ¨

B X = a^∗ba^∗b^∗a; Y = b^∗a ; Z = X(Y (ab + b)X)^∗+ XY ((ab + b)XY )^∗

ꢁ ©

ꢀ ¨

C X = a^∗b; Y = a^∗b^∗ab^∗a ; Z = X(Y (ab + b)X)^∗+ XY ((ab + b)XY )^∗

ꢁ ©

ꢀ ¨

D X = a^∗b; Y = a^∗+ a^∗b^∗ab^∗a ; Z = X(Y (ab + b)X)^∗+ XY ((ab + b)XY )^∗

ꢁ ©

Câu 6. Nếu sử dụng giải thuật đơn định hóa để chuyển NFA trên thành DFA thì DFA mới có bao nhiêu

trạng thái.

ꢀ ¨

A 20

B 18

C 15

D 16

ꢁ ©

Câu 7. Số trạng thái có trong DFA tối giản (tương đương với NFA trên) là bao nhiêu?

ꢀ ¨

A 10

B 20

C 16

D 18

ꢁ ©

Câu 8. 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) −→ (x + 3 < y).

B y ≥ x + 3.

ꢁ ©

ꢀ ¨

ꢁ ©

ꢀ ¨

C y ≥ x.

D y ≥ x + 1.

ꢁ ©

Câu 9. 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 ≥ 0.

C y ≥ x ≥ 0.

D y > 0.

ꢁ ©

Câu 10. Biễu thức chính quy cho ngôn ngữ L = {aⁿb^m|(n + m) chẵn} là

ꢀ ¨

A ((aa)⁺(bb)⁺) · (a(aa)⁺b(bb)⁺).

B (aa)^∗(bb)^∗+ a(aa)^∗b(bb)^∗.

ꢁ ©

ꢀ ¨

C ((aa)^∗(bb)^∗) · (a(aa)^∗b(bb)^∗).

D (aa)⁺(bb)⁺+ a(aa)⁺b(bb)⁺.

ꢁ ©

Câu 11. Để xem xét automata bên dưới và biểu thức chính quy E = [(ab)^∗(ba)^∗(bb^∗a(aa)^∗b(ab)^∗)^∗]^∗có

biểu diễn cùng một ngôn ngữ hay không, hãy chọn phát biểu đúng dưới đây.

b

q₀

q₃

a

b

q₁

q₂

b

a

ꢀ ¨

A Biểu diễn cùng một ngôn ngữ.

ꢁ ©

ꢀ ¨

B Không tương đương, tuy nhiên không thể xác định được phản ví dụ.

ꢁ ©

ꢀ ¨

C Không tương đương, phản ví dụ là aa.

ꢁ ©

ꢀ ¨

D Không tương đương, phản ví dụ là abbaaabab.

ꢁ ©

Chữ ký SV:. . . . . . . . . . . . . . . . . .

Mã đề 1913 (B01)

Trang 2

Câu 12.

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à

ꢀ ¨

x!

A (y = (x − a)!) ∧ (a ≥ 0).

B (y = ) ∧ (a ≥ 0).

ꢁ ©

a!

x!

ꢀ ¨

C (y = (x − a)!) ∧ (a ≤ x).

D (y = ) ∧ (a ≤ x).

ꢁ ©

a!

Câu 13. Cho P là chương trình x = 2020. Khi đó theo luật gán (assignment rule) ta có

ꢀ ¨

A |=_par(|2020 = 4|) P (|x = 4|).

B |=_tot(|2020 = 2020|) P (|x = 2020|).

ꢁ ©

ꢀ ¨

ꢁ ©

ꢀ ¨

C |=_par(|2020 = y|) P (|x = y|).

D |=_par(|2020 = 2020|) P (|x = 2020|).

ꢁ ©

Câu 14. Một dạng bất biến (invariant form) nên được sử dụng để chứng minh tính đúng đắn của đoạn

chương trình P như trong Câu 30 là

ꢀ ¨

A {m = (n − i) × n ∧ i ≥ 0}.

B {m = (i × n) ∧ i > 0}.

ꢁ ©

ꢀ ¨

ꢁ ©

ꢀ ¨

C {m = (n − i) × n ∧ i > 0}.

D {m = (i × n) ∧ i > 0}.

ꢁ ©

Câu 15. 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

E

B

C

D

a

b

F

G

b

ꢀ ¨

A aababba

B bbaaaa

C aaaabb

D abaababab

ꢁ ©

Câu 16. Luật đúng đắn (correctness) cho cấu trúc if... else được phát biểu như sau

ꢀ ¨

(|φ ∧ B|) C (|ψ|)

(|φ ∧ ¬B|) C (|ψ|)

A

.

ꢁ ©

(|φ|) if B { C } else { C } (|ψ|)

ꢀ ¨

(|φ₁|) C₁(|ψ|)

(|φ₂|) C₂(|ψ|)

B

.

ꢁ ©

(|(B → φ₁) ∧ (¬B → φ₂)|) if B { C₁} else { C₂} (|ψ|)

ꢀ ¨

(|φ ∧ B|) C₁(|ψ|)

(|φ ∧ ¬B|) C₂(|ψ|)

.

C

ꢁ ©

(|φ|) if ¬B { C₁} else { C₂} (|ψ|)

ꢀ ¨

(|φ|) C₁(|ψ|)

(|φ|) C₂(|ψ|)

D

.

ꢁ ©

(|(B → φ) ∧ (¬B → φ)|) if B { C₁} else { C₂} (|ψ|)

Chữ ký SV:. . . . . . . . . . . . . . . . . .

Mã đề 1913 (B01)

Trang 3

Câu 17.

Precondition của While

r := 1;

i := 0;

while i < m do

r := r ∗ n;

i := i + 1

sẽ là

ꢀ ¨

A (m ≥ 0) ∧ (n ≥ 0).

B (m ≥ 0) ∧ (n > 0).

ꢁ ©

ꢀ ¨

ꢁ ©

ꢀ ¨

C m > 0.

D (m > 0) ∧ (n > 0).

ꢁ ©

Câu 18. 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 Không thể.

ꢁ ©

ꢀ ¨

B Có thể sử dụng một DFA tối giản mà số lượng trạng thái vô hạn.

ꢁ ©

ꢀ ¨

C Có thể sử dụng một DFA tối giản gồm ba trạng thái.

ꢁ ©

ꢀ ¨

D Có thể sử dụng một DFA tối giản có hơn ba trạng thái.

ꢁ ©

Câu 19. Xét Σ = {a, b, c} và L = {ab, ca, a, bb, bc}. Chuỗi nào dưới đây thuộc vào L^∗.

ꢀ ¨

A abaacbb

B bbabacabbbaaa

C abcabbbbba

D aabbbcabbba

ꢁ ©

Câu 20. Biểu thức nào sau đây là biểu thức chính quy biểu diễn tập các chuỗi trên Σ = {a, b} có chứa

chuỗi con ab và chuỗi con ba?

ꢀ ¨

A (a⁺b⁺a(a ∪ b)^∗) · (b⁺a⁺b(a ∪ b)^∗) .

B (a^∗b^∗a(a ∪ b)⁺) ∪ (b^∗a^∗b(a ∪ b)⁺) .

ꢁ ©

ꢀ ¨

ꢁ ©

ꢀ ¨

C (a^∗b^∗a(a ∪ b)⁺) · (b^∗a^∗b(a ∪ b)⁺) .

D (a⁺b⁺a(a ∪ b)^∗) ∪ (b⁺a⁺b(a ∪ b)^∗) .

ꢁ ©

Câu 21. Đáp án nào là phản ví dụ cho thấy hai automata bên dưới không tương đương?

a

q₀

q₃

p₀

p₃

a

b

a

b

a

q₁

q₂

b

p₁

p₂

b

a

ꢀ ¨

A abaab

B baab

C babb

D abbaa

ꢁ ©

Câu 22. 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 12?

ꢀ ¨

A |=_par(|>|) if (b > 0) {c = a + b} else c = a − b (|ψ|), và |=_tot(|>|) downfac (|y = x!|).

ꢁ ©

ꢀ ¨

B |=_tot(|>|) if (b > 0) {c = a + b} else c = a − b (|ψ|), và |=_par(|>|) downfac (|y = x!|).

ꢁ ©

ꢀ ¨

C |=_par(|>|) if (b > 0) {c = a + b} else c = a − b (|ψ|), và |=_par(|>|) downfac (|y = x!|).

ꢁ ©

ꢀ ¨

D |=_tot(|>|) if (b > 0) {c = a + b} else c = a − b (|ψ|), và |=_tot(|>|) downfac (|y = x!|).

ꢁ ©

Câu 23. Hai biểu thức chính qui: E₁= ((c + b)^∗(a + c))^∗và E₂= (ba + bc + ca + c)^∗có biểu diễn cùng

một ngôn ngữ không?

ꢀ ¨

A Biểu diễn cùng ngôn ngữ

B Không tương đương

ꢁ ©

ꢀ ¨

ꢁ ©

ꢀ ¨

C E₂⊇ E₁

D E₁⊆ E₂

ꢁ ©

Chữ ký SV:. . . . . . . . . . . . . . . . . .

Mã đề 1913 (B01)

Trang 4

Câu 24. Xét Σ = {a, b, c} và L = {a, ab, bc, ba}. Chuỗi nào dưới đây không thuộc vào L⁵.

ꢀ ¨

A aabcabba

B bcbaaaa

C aaaaa

D abaababca

ꢁ ©

Câu 25. Cách nào dưới đây có thể xác định hai automata hữu hạn (FA) là tương đương?

ꢀ ¨

A So sánh số trạng thái của hai FA.

ꢁ ©

ꢀ ¨

B Chuyển về các biểu thức chính quy tương đương để chứng minh bằng toán học.

ꢁ ©

ꢀ ¨

C Chuyền về so sánh bảng chuyển trạng thái của hai automata tối ưu tương ứng.

ꢁ ©

ꢀ ¨

D Áp dụng vét cạn các trường hợp dựa trên bảng chuyển trạng thái.

ꢁ ©

Câu 26. Xét đoạn chương trình sau.

Dạng bất biến (invariant form) nên được sử dụng để chứng minh tính đúng đắn của nó là

ꢀ ¨

P

i

A {(s = _k=1b[k]) ∧ 2020 > i > 0}.

B {(s = ²⁰²⁰b[k]) ∧ 2020 > i ≥ 0}.

k=1

ꢁ ©

ꢀ ¨

ꢁ ©

ꢀ ¨

P

i−1

C {(s = _k=0b[k]) ∧ 2020 ≥ i ≥ 0}.

D {(s = _k=1b[k]) ∧ 2020 ≥ i > 0}.

ꢁ ©

Câu 27. Dạng bất biến (invariant form) của chương trình While như trong Câu 17 mà có thể dùng trong

việc chứng minh tính đúng đắn của nó là sẽ là

ꢀ ¨

A (r = nⁱ) ∧ (0 ≤ i ≤ m).

B (r = nⁱ) ∧ (0 ≤ i ≤ m) ∧ (n > 0).

ꢁ ©

ꢀ ¨

ꢁ ©

ꢀ ¨

C (r = nⁱ) ∧ (0 ≤ i ≤ m) ∧ (n ≥ 0).

D (r = nⁱ) ∧ (n > 0).

ꢁ ©

Câu 28. 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 } (|ψ ∧ ¬B|)

(|ψ|) while B { C } (|ψ ∧ ¬B|)

ꢀ ¨

(|φ ∧ B|) C (|ψ|)

(|ψ ∧ B|) C (|ψ|)

C

.

D

.

ꢁ ©

(|φ|) while B { C } (|ψ|)

(|ψ|) while B { C } (|ψ|)

Câu 29. Xét đoạn chương trình sau.

Dạng bất biến (invariant form) nên được sử dụng để chứng minh tính đúng đắn của nó với tiền

điều kiện {y = y₀∧ y ≥ 0} là

ꢀ ¨

A {z = x(y₀− y) ∧ y > 0}.

B {z = x(y − y₀) ∧ y₀≥ 0}.

ꢁ ©

ꢀ ¨

ꢁ ©

ꢀ ¨

C {z = x(y₀− y) ∧ y ≥ 0}.

D {z = x(y − y₀) ∧ y₀> 0}.

ꢁ ©

Chữ ký SV:. . . . . . . . . . . . . . . . . .

Mã đề 1913 (B01)

Trang 5

Câu 30.

Hậu điều kiện (postcondition) của đoạn chương trình P

là

ꢀ ¨

A m + n.

B m × n.

C m = n².

D mⁿ.

ꢁ ©

Chữ ký SV:. . . . . . . . . . . . . . . . . .

Mã đề 1913 (B01)

Trang 6

Đề thi cuối kỳ môn Mô hình hóa toán học năm 2020 - Mã đề 1913 (B01) - Đại học Bách khoa thành phố Hồ Chí Minh