ĐỀ THI MÔN TÓAN RỜI RẠC & LÝ THUYẾT DỒ THỊ LỚP: HC3CT-Lần 1-Đề 1

Tham khảo đề thi - kiểm tra 'đề thi môn tóan rời rạc & lý thuyết dồ thị lớp: hc3ct-lần 1-đề 1', khoa học tự nhiên, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả
Nội dung trích xuất từ tài liệu:
ĐỀ THI MÔN TÓAN RỜI RẠC & LÝ THUYẾT DỒ THỊ LỚP: HC3CT-Lần 1-Đề 1 ĐỀ THI MÔN TÓAN RỜI RẠC & LÝ THUYẾT DỒ THỊ TRƯỜNG CĐCNTT TP.HCM LỚP: HC3CT-Lần 1-Đề 1. Khoa CNTT *** (TG 90 phút – được xem tài liệu) Bài 1: Chứng minh biểu thức mệnh đề sau là hằng đúng (┐(a ∧b) ∧a) → ┐b Bài 2: Đơn đồ thị phẳng liên thông có 9 đỉnh, bậc các đỉnh là 2,2,2,3,3,3,4,4,5. Tìm số cạnh, số mặt và vẽ đồ thị. Bài 3: 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) = xyzt + xy t + xy z + x y z t + x y t + x y t Bài 4: Cho đơn đồ thị G=(V,E) có ma trận trọng số như sau (dấu - là giữa 2 đ ỉnh không có cạnh): 1 2 3 4 5 6 7 1 0 4 - 5 15 - - 2 4 0 28 - - - - 3 - 28 0 17 30 - 12 4 5 - 17 0 - 10 7 5 15 - 30 - 0 5 15 6 - - - 10 5 0 3 7 - - 12 7 15 3 0 a) Vẽ đồ thị G. b) 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 2 đến các đỉnh còn lại. Liệt kê các lộ trình này. Hết.