TR NG CĐ CNTT TP.HCMƯỜ Đ THI H T MÔN TRR & LTDT - L N 2 (Đ 1)Ề Ế Ầ ề
Khoa CNTT L P: Khóa 10.Ớ
* * * (TG 90 phút – đ c xem tài li u riêng)ượ ệ
Bài 1(1đ):
Ch ng minh bi u th c m nh đ sau là h ng saiứ ể ứ ệ ề ằ
((a ∨ b) → c) ∧ ((a ∨ b) ∧ ┐c)
Bài 2(3đ):
M t m t kh u ph i có đ dài t 6 đ n 8 ký t (không phân bi t ký t hoa, th ng), m i kýộ ậ ẩ ả ộ ừ ế ự ệ ự ườ ỗ
t đ c l y t b ng 26 ch cái. Tính s m t kh u có th t o ra trong m i tr ng h p sau:ự ượ ấ ừ ả ữ ố ậ ẩ ể ạ ỗ ườ ợ
a) Không có đi u ki n gì thêm.ề ệ
b) Trong m t kh u ph i có ít nh t m t ký t X.ậ ẩ ả ấ ộ ự
c) Trong m t kh u ph i có ít nh t m t ký t X và có ít nh t m t ký t Y.ậ ẩ ả ấ ộ ự ấ ộ ự
Bài 3(2đ):
Tìm các công th c đa th c t i ti u c a hàm Bool sau, b ng ph ng pháp bi u đứ ứ ố ể ủ ằ ươ ể ồ
Karnaugh.
F(x,y,z,t) = xyt + xyz
t
+ x
z
t
+
x
y
t
+
x
y
z
t +
x
y
z
Bài 4(4 đ):
Cho đ n đ th có h ng G=(V,E) có ma tr n tr ng s nh sau (d u - là gi a 2 đ nhơ ồ ị ướ ậ ọ ố ư ấ ữ ỉ
không có cung):
1 2 3 4 5 6
1 0 8 5 6 -
-
2 - 0 - - - 9
3 - - 0
15
3 -
4 - 1 - 0 - -
5 4 - - - 0 4
6 - 7 - 2 - 0
V đ th . Th hi n s ho t đ ng c a thu t toán Dijkstra v i đ th trên, đ tìm đ ng điẽ ồ ị ể ệ ự ạ ộ ủ ậ ớ ồ ị ể ườ
ng n nh t t đ nh 1 đ n các đ nh còn l i. Li t kê các l trình này.ắ ấ ừ ỉ ế ỉ ạ ệ ộ
H t.ế
TR NG CĐ CNTT TP.HCMƯỜ Đ THI H T MÔN TRR & LTDT - L N 2 (Đ 2)Ề Ế Ầ ề
Khoa CNTT L P: Khóa 10.Ớ
* * * (TG 90 phút – đ c xem tài li u riêng)ượ ệ
Bài 1(1đ):
Ch ng minh bi u th c m nh đ sau là h ng đúngứ ể ứ ệ ề ằ
((p ∨ q) → r) ∨ ((p ∨ q) ∧ ┐r)
Bài 2(3đ):
M t m t kh u ph i có đ dài t 5 đ n 7 ký t (không phân bi t ký t hoa, th ng), m i kýộ ậ ẩ ả ộ ừ ế ự ệ ự ườ ỗ
t đ c l y t b ng 26 ch cái. Tính s m t kh u có th t o ra trong m i tr ng h p sau:ự ượ ấ ừ ả ữ ố ậ ẩ ể ạ ỗ ườ ợ
a) Không có đi u ki n gì thêm.ề ệ
b) Trong m t kh u ph i có đúng m t ký t A.ậ ẩ ả ộ ự
c) Trong m t kh u ph i có đúng m t ký t A và có đúng m t ký t B.ậ ẩ ả ộ ự ộ ự
Bài 3(2đ):
Tìm các công th c đa th c t i ti u c a hàm Bool sau, b ng ph ng pháp bi u đứ ứ ố ể ủ ằ ươ ể ồ
Karnaugh.
F(x,y,z,t) =
x
y
t
+
x
y
z
t +
x
y
z + xyt + xyz
t
+ x
z
t
Bài 4(4 đ):
Cho đ n đ th có h ng G=(V,E) có ma tr n tr ng s nh sau (d u - là gi a 2 đ nhơ ồ ị ướ ậ ọ ố ư ấ ữ ỉ
không có cung):
1 2 3 4 5 6
1 0 8 5 6 -
-
2 - 0 - - - 9
3 - - 0
15
3 -
4 - 1 - 0 - -
5 4 - - - 0 4
6 - 7 - 2 - 0
V đ th . Th hi n s ho t đ ng c a thu t toán Dijkstra v i đ th trên, đ tìm đ ng điẽ ồ ị ể ệ ự ạ ộ ủ ậ ớ ồ ị ể ườ
ng n nh t t đ nh 5 đ n các đ nh còn l i. Li t kê các l trình này.ắ ấ ừ ỉ ế ỉ ạ ệ ộ
H t.ế