Đề thi cao học chuyên ngành Tin Học (Môn CoBan)

MÔN CƠ BẢN

Hỏi rằng có thể tạo đc bao nhiêu mật khẩu gồm 8 ký tự , đc viết bởi 4 chữ cái a, b, c,d sao cho mỗi chữ cái xuất hiện đúng 2 lần và không có hai chữ ký tự nào viết liền nhau giống nhau?

Tìm văn phạm sinh G mà ngôn ngữ sinh bởi nó là L(G)={a3nb3nc3n: n thuộc N}
Nêu phân loại Chomsky và các ví dụ mô tả

Cho trước hai mệnh đề logic A và B. Khi nào A và B tương đương logic với nhau.
Hãy xác định biểu thức logic tương đương với
và chỉ chứa phép toán tuyểnm hội và phủ định mà thôi.
Xây dựng mạch cho công tắc đèn cầu thang sao cho ở trên cầu thang cũng như ở dưới cầu thang ta đều có thể bật tắt đèn cầu thang.

Hãy nêu thuật toán Prim và áp dụng nó để tìm cây khung tối ưu trong đồ thị có 14 đỉnh, 25 cạnh và trọng số của cạnh nối hai đỉnh i và j được ký hiệu bởi e(i,j) như sau:
e(1,2)=1, e(1,14)=3, e(2,3)=5, e(2,14)=2, e(3,14)=4, e(3,13)=7, e(3,12)=11, e(3,4)=8, e(4,5)=13, e(4,12)=9, e(5,6)=20, e(5,8)=23, e(5,11)=24, e(5,12)=14,
e(6,7)=19, e(6,8)=21, e(7,8)=18, e(8,9)=17 e(8,10)=22, e(8,11)=25, e(9,10)=16, e(10,11)=15, e(11,12)=12, e(12,13)=10, e(13,14)=6.
Trong một mạng điện có 5 điểm A, B, C, D và E trên mặt phẳng cần phải mắc đường dây điện nối với nhau đôi một. Hỏi rằng có thể thiết kế đường nối trên mặ phẳng sao cho ko có hai đường nối nào cắt nhau hay không, hãy chứng minh câu trả lời.