TRƯỜNG ĐẠI HỌC PHENIKAA
KHOA CÔNG NGHỆ THÔNG TIN
ĐỀ THI KẾT THÚC HỌC PHẦN
Học kỳ: III - Năm học: 2023-2024
Hệ đào tạo: Đại học Bậc học: Đại học
Tên học phần: Toán rời rạc
Ngày 08 tháng 08 năm 2024
Thời gian làm bài: 90 phút
Thống nhất: Mã số sinh viên của em là một số gồm 8 chữ số, gọi N là số mã số sinh viên, gọi a là chữ
số thứ sáu, b là chữ số thứ bảy, c là chữ số thứ tám.
Ví dụ: Bạn Trần Rời Rạc có mã số sinh viên là 23011211 thì N = 23011211, a = 2, b = 1, c = 1.
Với 𝑁, 𝑎, 𝑏 như thống nhất, đếm số lượng số tự nhiên từ 1 đến 𝑁 có bao nhiêu số chia hết cho (𝑎 + 10)
hoặc (𝑏 + 20).
Ví dụ: Bạn Trần Rời Rạc có mã số sinh viên là 23011211 thì 𝑎 = 2, 𝑏 = 1 và bạn Trần Rời Rạc cần đếm
từ 1 đến 23011211 có bao nhiêu số chia hết cho 12 hoặc 21.
Cho đồ thị G1 như ở hình bên. Với 𝑎, 𝑏 như thống nhất,
tạo đồ thị G2 bằng cách loại bỏ hai đỉnh 𝑎, 𝑏 và tất cả các
cạnh liên thuộc với 𝑎, 𝑏. Ví dụ: Bạn Trần Rời Rạc có 𝑎 =
1, 𝑏 = 1 thì chỉ loại đi duy nhất đỉnh 1 và tất cả các cạnh
liên thuộc với 1.
a) Nêu các tính chất của đồ thị G1.
b) Xét đồ thị G2, viết ra một dãy số, các số cách
nhau một dấu cách tương ứng là bậc của các
đỉnh từ nhỏ đến lớn.
c) Tìm đường đi ngắn nhất từ đỉnh 10 đến đỉnh
11 trên đồ thị G2 (sinh viên chỉ cần đưa
phương án đường đi và độ dài của đường đi
ngắn nhất, không cần nêu rõ cách giải).
d) Tìm cây khung nhỏ nhất của đồ thị G2 bằng
thuật toán Prim nếu số c của bạn là chẵn, bằng thuật toán Kruskal nếu số 𝑐 của bạn là lẻ. Ví dụ: Bạn Trần
Rời Rạc có mã số sinh viên là 23011211 thì 𝑐 = 1, bạn cần sử dụng thuật toán Kruskal để tìm cây khung
nhỏ nhất.
Cho 10 biểu thức chính quy sau (các biểu thức được đánh số thứ tự từ 0 đến 9). Với 𝑎, 𝑏, 𝑐 như thống
nhất, gọi 𝑥 là biểu thức thứ 𝑎, 𝑦 là biểu thức thứ 𝑏, 𝑧 là biểu thức thứ 𝑐.
0) 0*1 1) 1*0 2) 1*1 3) 01* 4) 10*
5) 11* 6) 01*0 7) 10*1 8) 00*1 9) 10*0
a) Xây dựng văn phạm sinh ngôn ngữ có dạng là biểu thức 𝑥;
b) Xây dựng otomat đoán nhận biểu thức 𝑦;
c) Xây dựng otomat đoán nhận biểu thức 𝑧 ∗;
Ví dụ: Bạn Trần Rời Rạc có a = 2, b = 1, c = 1 thì câu a) bạn cần xây dựng văn phạm sinh ngôn ngữ có
dạng 1*1; câu b) dựng otomat đoán nhận biểu thức 1*0; câu c) dựng otomat đoán nhận biểu thức (1*0)*;
Cho 10 mệnh đề có số thứ tự lần lượt từ 0 đến 9 như sau:
0) ((¬𝑝 ˄ 𝑞) ˄ (𝑞 ˄ 𝑟)) ˄ ¬𝑞
1) (𝑝 ˄ ¬𝑞) ˄ (¬𝑝 ˅ 𝑞))
2) (¬𝑝 ˅ 𝑞) ˅ (𝑝 ˄ 𝑞))
3) ¬𝑝 ˄ (𝑞 ˅ (¬𝑝 ˄ 𝑞))
4) (𝑞 ˄ (𝑝 ˅ ¬𝑞)) ˅ (𝑝 ˄ ¬𝑞)
5) 𝑝 ˅ 𝑞 ˄ (¬(𝑝 ˄ 𝑞) ˅ 𝑞)
6) ¬(𝑝 ˅ 𝑞)˅ (𝑝 ˄ 𝑞) ˅ (𝑝 ˅ ¬𝑞)
7) ¬𝑝 ˄ (𝑝 ˅ 𝑞)˅¬(¬𝑝 ˄ 𝑞)
8) (𝑝 ˄ 𝑞) ˅ (¬𝑝 ˅ (𝑝 ˄ ¬𝑞))
9) (¬𝑝 ˄ 𝑞) ˅ (𝑝 ˄ 𝑞) ˄ (𝑝 ˅ ¬𝑞)
a) Dùng bảng chân trị chỉ ra mệnh đề thứ 𝑎 có là hằng đúng hay không.
b) Không dùng bảng chân trị chỉ ra mệnh đề thứ 𝑐 có là hằng đúng hay không.
Ví dụ: Bạn Trần Rời Rạc có mã số sinh viên là 23011211 thì 𝑎 = 2, 𝑐 = 1 và bạn Trần Rời Rạc cần
dùng bảng chân trị để làm mệnh đề thứ 2 (câu a), dùng một phương pháp khác bảng chân trị để làm mệnh
đề thứ 1 (câu b).
HẾT!