bởi admin lúc Mon, Apr 16 '18 11:36 AM | Lần xem 1091 | Lần tải 150
  • Download images Bài tập TOÁN RỜI RẠC TS.Nguyễn Viết Đông
  • Download images Bài tập TOÁN RỜI RẠC TS.Nguyễn Viết Đông
  • Download images Bài tập TOÁN RỜI RẠC TS.Nguyễn Viết Đông
  • Download images Bài tập TOÁN RỜI RẠC TS.Nguyễn Viết Đông
  • Download images Bài tập TOÁN RỜI RẠC TS.Nguyễn Viết Đông


TS. NGUYỄN VIẾT ĐÔNG
BÀI TẬP TOÁN RỜI RẠC
August 2, 2012
1)
Hãy kiểm tra suy luận sau
t u
(s t)
(p q )
(s u )
______________
p
2)
Đề thi 2010 .
a) Một dãy số thực {xn} được nói là thuộc O(n) nếu tồn tại số thực dương C và số tự nhiên m
cho xn C n mỗi khi n m. Hãy sử dụng mệnh đề lượng từ hóa để viết lại định nghĩa trên.
)Viết ra mệnh đề lượng từ hóa cho một dãy số thực không thuộc O(n).
sao
3)
Đề thi năm 2011.
a) Một thuật toán được nói là có thời gian đa thức nếu thời gian chạy thuật toán T(n) với n là chiều
dài của input, thỏa tính chất :
"Tồn tại số thực dương C và số tự nhiên d sao cho T(n) C nd, với n đủ lớn”.
) Hãy sử dụng mệnh đề lượng từ hóa để viết lại định nghĩa trên.
Viết ra mệnh đề lượng từ hóa cho định nghĩa của một thuật toán với thời gian không phải là thời gian
đa thức.
4)
Đề 2012
Kiểm tra tính đúng đắn của suy luận sau
p q
(p s)
(t p)
(q s)
t
5)
Đề năm 2005
Kiểm tra tính đúng của suy luận sau:
∀x∈R(P(x)Q(x))
∀x∈R(P(x)Q(x) R(x))
_________________________
6)
∀x∈R(R(x) P(x)) .
Cho A = 1,2,3,4,5,6,7,8,9,10,11,12.
Có bao nhiêu quan hệ tương đương trên A gồm 3
lớp
tương đương mà mỗi lớp
có 4 phần tử.
7)
Đề thi 2003.
a) Có bao nhiêu cặp tập hợp con A, B của một tập hợp 8
phần tử sao cho A B = .
) Có bao nhiêu cặp tập hợp con A, B của một tập hợp 8
phần tử sao cho: AB A+ B.
1
TS. NGUYỄN VIẾT ĐÔNG
BÀI TẬP TOÁN RỜI RẠC
August 2, 2012
8)
Đề thi 2008
Ta lấy ngẫu nhiên 5 bìa từ một hộp chứa 60 tấm bìa trên đó lần lượt ghi các số 10, 11, …, 69.
a)
Có bao nhiêu trường hợp có thể xảy ra.
)
Có bao nhiêu trường hợp trong đó 5 bìa lấy ra chứa đúng “hai đôi” (mỗi đôi gồm hai bìa có chữ
số cuối giống nhau. Chữ số cuối của hai đôi này là hai chữ số khác nhau và khác với chữ số cuối
của bìa còn lại).
c) Có bao nhiêu trường hợp trong đó chữ số cuối của 5 bìa tạo
thành một dãy tăng?
d) Có bao nhiêu trường hợp chữ số cuối của 5 bìa tạo thành một dãy tăng và có ít nhất hai bìa có chữ
số đầu khác nhau.
9)
Đề thi 2009.
Ta lấy ngẫu nhiên 5 bìa từ một hộp chứa 50 tấm bìa trên đó lần lượt ghi các số 10, 11, …, 59.
a) Có bao nhiêu trường hợp có thể xảy ra.
) Có bao nhiêu trường hợp trong đó có đúng hai trong năm bìa lấy ra có chữ số cuối bằng nhau.
10) Mỗi người sử dụng một hệ thống máy tính của một công ty X phải
sử dụng một password dài từ
6 đến 8 ký tự, trong đó mỗi ký tự là một chữ cái (trong 26 chữ cái) hoặc là một chữ số (trong 10
chữ số). Mỗi password phải có ít nhất một chữ số. Hỏi có thể lập được bao nhiêu password khác
nhau?
11)Đề 2012.Cho tập hợp
X = x∈ :
1 x 20với quan hệ

thông thường. Tìm số tập con
A
của X thỏa điều kiện trong mỗi trường hợp sau:
a)
min(A) = 8 và |A| 10.
)
min(A) = 6 và max(A) = 18.
12) Trong suốt một tháng gồm 30 ngày, một đội bóng phải chơi ít nhất mỗi ngày một trận, nhưng
trong tháng đó không được chơi nhiều hơn 45 trận. Hãy chứng minh rằng có một giai đoạn gồm
một số ngày liên tiếp mà trong giai đoạn đó đội phải chơi đúng 14 trận.
13) Xét 3 chuỗi ký tự trên tập mẫu tự {a, b, c} ( với a 1 = ac, s2 = aacb, s3 = aba.
a) Hãy sắp xếp chúng theo thứ tự tăng đối với thứ tự từ điển.
)
Cho biết giữa s1 và s3 có bao nhiêu chuỗi ký tự có chiều dài 6.
14) Đề thi 2011.Có bao nhiêu bộ ba số nguyên (x1, x2, x3) sao cho x1 > 10, x2 >15, 0 ≤ x3 ỏa
x1+ x2 + x3 ≤ 100.
15)Đề thi2012.
a) Tìm nghiệm tổng quát của hệ thức đệ qui:
xn – xn–1 –2xn–2 =0.
) Tìm nghiệm của hệ thức đệ qui:
xn – xn–1 – 2xn–2 = (6n

5)2n–1
thỏa điều kiện đầu x0 = 7, x1 = 4
16)Đề thi 2011
a) Tìm nghiệm tổng quát của hệ thức đệ quy:
an = 6 an – 1 – 9an – 2 .
2
0 1
TS. NGUYỄN VIẾT ĐÔNG
BÀI TẬP TOÁN RỜI RẠC
August 2, 2012
)Tìm nghiệm thỏa điều kiện đầu: a0 = 2, a1 = 15 của hệ thức đệ qui:
an = 6 an – 1 – 9an – 2 + n . 3n + 1.
17)
a)
)
Tìm nghiệm tổng quát của hệ thức đệ qui sau
an = 6an – 1 – 9an – 2 + (18n – 6 ) 3n – 1
Tìm số các chuỗi nhị phân chiều dài n chứa chuỗi con 00.
18)a) Tìm nghiệm tổng quát của hệ thức đệ qui:
an = an-1 + 6an-2.
) Tìm nghiệm thỏa điều kiện đầu a = 8, a = 5 của hệ thức đệ qui:
an = an-1 + 6an-2 + 10n(-2)n - 3(-2)n-1
19). Đề thi năm 2005
Một người gửi 100 triệu đồng vào một quĩ đầu tư vào ngày đầu của một năm. Ngày cuối cùng của
năm người đó được hưởng hai khoản tiền lãi. Khoản thứ nhất là 20% tổng số tiền có trong tài khoản
cả năm, khoản lãi thứ hai là 45% của tổng số tiền có trong tài khoản của năm trước đó. Gọi Pn là số
tiền có trong tài khoản vào cuối năm thứ n.
a)Tìm công thức truy hồi cho Pn
)Tìm biểu thức của Pn theo n .
20) Đề thi 2004
Một bãi giữ xe được chia thành n lô cạnh nhau theo hàng ngang để xếp xe đạp và xe máy. Mỗi xe
đạp chiếm 1 lô còn mỗi xe máy chiếm 2 lô. Gọi Ln là số cách xếp cho đầy n lô.
a)Tìm công thức đệ qui thỏa bởi Ln
)Tìm biểu thức của Ln theo n .
21) Tìm hệ thức đệ qui cho xn, trong đó xn là số miền của mặt phẳng bị phân chia bởi n đường thẳng
trong đó không có 2 đường nào song song và không có ba đường nào đồng qui. Tìm xn .
22)(Đề thi 2012). Tìm tất cả các công thức đa thức tối tiểu của hàm Bool 4 biến sau:
f(x,y,z,t) = xyz y(xz zt) xy(zt z).
23) (Đề 2011)Xét hàm Bool
𝑓 =
𝑥 𝑦 𝑥𝑦 (𝑧 t) z( xt 𝑦𝑡) 𝑦 𝑧𝑡
a)Hãy vẽ biểu đồ Karnauugh của 𝑓.
)Viết ra dạng nối rời chính tắc ( dạng tuyển chuẩn tắc) của 𝑓.
24) Cho hàm Bool của 4 biến
f (x, y,z,t) =xt(z y) x z(yt ) y(t z)
a) Tìm các tế bào lớn của Kar( f ).
) Tìm
tất cả các công thức đa thức tối tiểu của f.
25)Hai đồ thị sau đây có đẳng cấu với nhau không?
u1
u2
v1
v2
v3
u5
u6
v6
u4
u3
v5
3
(G)
(G’)
bởi admin lúc Mon, Apr 16 '18 11:36 AM

<p>B&agrave;i tập to&aacute;n rời rạc cho ng&agrave;nh CNTT của Thạc sĩ Nguyễn Viết Đ&ocirc;ng</p>
770626.pdf
Kích thước: 482.71 kb
Lần tải: 0 lần
Download