Tài liệu ĐỀ THI HẾT MÔN TRR & LTDT - LẦN 1 (Đề 1) LỚP: LT6CT 2012 pdf

TRƯỜNG CĐ CNTT TP.HCM ĐỀ THI HẾT MÔN TRR & LTDT - LẦN 1 (Đề 1)

Khoa CNTT LỚP: LT6CT 2012.

* * * (TG 90 phút – Không được xem tài liệu)

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):

A B C D E F

A 0 18 15 16 - -

B - 0 - - - 19

C - - 0 15 13 -

D - 11 - 0 - -

E 14 - - - 0 4

F - 17 - 12 - 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 A đến các đỉnh còn lại. Liệt kê các lộ trình này.

Hết.