- NGUYỄN VIẾT ĐÔNG Hướng dẫn, đáp số BÀI TẬP TOÁN RỜI RẠC August 2, 2012 LỜI GIẢI TÓM TẮT HOẶC ĐÁP SỐ 1) t u (1) r (s t) (2. - p s) (luật De Morgan) 1 CuuDuongThanCong.com https://fb.com/tailieudientucntt TS. - NGUYỄN VIẾT ĐÔNG Hướng dẫn, đáp số BÀI TẬP TOÁN RỜI RẠC August r (p s) (tiền đề) 9) r (PP phủ định) 10) (t p. - b CuuDuongThanCong.com https://fb.com/tailieudientucntt TS. - NGUYỄN VIẾT ĐÔNG Hướng dẫn, đáp số BÀI TẬP TOÁN RỜI RẠC August . - 15) a) xn – xn–1 – 2xn–2 0. - Nghiệm tổng quát là xn = C1(–1)n + C22n b) xn – xn–1 – 2xn–2 (6n – 5)2n–1 (1) thỏa điều kiện đầu x0 = 7, x1 = 4. - 3 CuuDuongThanCong.com https://fb.com/tailieudientucntt TS. - NGUYỄN VIẾT ĐÔNG Hướng dẫn, đáp số BÀI TẬP TOÁN RỜI RẠC August 2, 2012 Vì 2 là nghiệm đơn của phương trình đặc trưng nên (1) có một nghiệm riêng dạng xn = n(an + b)2n Thế vào (1) ta được n(an + b)2n – (n – 1)[a(n –1. - b]2n – 2 = (6n – 5)2n – 1 12an – 10a + 6b = 12n – 10 12a = 12. - 1 C1 2C2 2 4 C2 3 Vậy xn = 4(–1)n + 3.2n + n22n 16) a) ĐS: an = c 3n +dn 3n . - Ta tính an: 4 CuuDuongThanCong.com https://fb.com/tailieudientucntt TS. - NGUYỄN VIẾT ĐÔNG Hướng dẫn, đáp số BÀI TẬP TOÁN RỜI RẠC August 2, 2012 - TH1 : Nếu bit đầu tiên là bit 1 thì có an – 1 cách chọn n – 1 bit còn lại. - Bit thứ 2 là bit 1 : có an – 2 cách chọn n – 2 bit còn lại Bit thứ 2 là bit 0 : có 2n – 2 cách chọn n – 2 bit còn lại ( các bit này chọn 0 hay 1 đều được) Vậy an = an – 1 + an – 2 + 2n – 2 ( n 2) (1). - Hệ thức đệ qui TTTN : an = an – 1 + an PTĐT : x2 – x – 1 = 0 có 2 nghiệm đơn là 𝑥1,2 = 2 𝑛 𝑛 1+ 5 1− 5 Nghiệm tổng quát của (2) là an = A +𝐵 2 2 Ta tìm một nghiệm riêng của (1) dưới dạng an = C2n. - C2n = C2n – 1 + C2n – 2 + 2n – 2 4C = 2C + C + 1 C = 1. - 5 CuuDuongThanCong.com https://fb.com/tailieudientucntt TS. - NGUYỄN VIẾT ĐÔNG Hướng dẫn, đáp số BÀI TẬP TOÁN RỜI RẠC August 2, 2012 Thế n = 2 vào (4), ta có: 2(-2)2(2A + B. - 19) a)Gọi Pn là tổng số tiền có trong tài khoản vào cuối năm thứ n. - Như vậy: 6 CuuDuongThanCong.com https://fb.com/tailieudientucntt TS. - NGUYỄN VIẾT ĐÔNG Hướng dẫn, đáp số BÀI TẬP TOÁN RỜI RẠC August 2, 2012 - Số tiền có trong tài khoản vào ngày đầu của năm thứ nhất sẽ là: P0 = 100 triệu - Số tiền có trong tài khoản vào ngày cuối năm của năm thứ nhất là: P1 = P0 + Lãi 1 + Lãi 2 Trong đó: Lãi 1 = 20% tổng số tiền có trong tài khoản cả năm = 0.2 * P0 Lãi 2 = 45% tổng số tiền có trong tài khoản của năm trước đó = 0.45 *0 Vậy : P1 = P0 + 0.2 P0 - Số tiền có trong tài khoản vào ngày cuối năm thứ hai sẽ là: P2= P1 + 0.2*P1 + 0.45*P0 Tổng số tiền có trong tài khoản vào cuối năm thứ n sẽ là: Pn= Pn-1 + 0.2*Pn-1 + 0.45*Pn-2 = 0.45*Pn-2 +1.02*Pn-1 b)Giải hệ thức đệ qui tuyến tính thuần nhất với P0 =100, P1 = 120 ta được n n Pn. - 7 CuuDuongThanCong.com https://fb.com/tailieudientucntt TS. - NGUYỄN VIẾT ĐÔNG Hướng dẫn, đáp số BÀI TẬP TOÁN RỜI RẠC August 2, 2012 Đường thẳng thứ n cắt n-1 đường thẳng cho trước tại n-1 giao điểm . - 8 CuuDuongThanCong.com https://fb.com/tailieudientucntt TS. - NGUYỄN VIẾT ĐÔNG Hướng dẫn, đáp số BÀI TẬP TOÁN RỜI RẠC August 2, 2012 x x x x x x x x z 1 t z 1 t z 2 3 t z 2 3 t z 4 5 t z 4 5 t z 6 7 8 t z 6 7 8 t y y y y y y y y x yz x yt x x x x x x x x z 1 t z 1 t z 2 3 t z 2 3 t z 4 5 t z 4 5 t z 6 7 8 t z 6 7 8 t y y y y y y y y yzt xyt x x x x x x x x z 1 t z 1 t z 2 3 t z 2 3 t z 4 5 t z 4 5 t z 6 7 8 t z 6 7 8 t y y y y y y y y xz y zt Tế bào lớn nhất thiết phải chọn: xz . - 9 CuuDuongThanCong.com https://fb.com/tailieudientucntt TS. - NGUYỄN VIẾT ĐÔNG Hướng dẫn, đáp số BÀI TẬP TOÁN RỜI RẠC August 2, 2012 Các công thức đa thức tương ứng với các phủ tối tiểu gồm các tế bào lớn: f xz yzt x yt (F1 ) f xz yzt xyz yzt (F2 ) f xz xyt x yz x yt (F3 ) f xz xyt x yz y zt (F4 ) So sánh ta thấy công thức (F1) thực sự đơn giản hơn các công thức khác. - x yt , x y z , x z t b) ĐS : Có ba công thức đa thức tối tiểu là y t y z x zt x y z , y t y z x yt x y z , y t y z x yt x z t 10 CuuDuongThanCong.com https://fb.com/tailieudientucntt TS. - NGUYỄN VIẾT ĐÔNG Hướng dẫn, đáp số BÀI TẬP TOÁN RỜI RẠC August G đẳng cấu với G’. - 6 2 MG = MG’ 26) 11 CuuDuongThanCong.com https://fb.com/tailieudientucntt TS. - NGUYỄN VIẾT ĐÔNG Hướng dẫn, đáp số BÀI TẬP TOÁN RỜI RẠC August 2, 2012 v1 v2 v3 v4 v5 v6 v7 v8 v9 v10 0. - (15,g)* Đường đi ngắn nhất từ a đến z là abdgz với chiều dài 15. - Đường đi : syx . - Đường đi: sy. - Đường đi: syxz d(s, t. - Đường đi: syt Tương tự ta được bảng sau với đồ thị mới 12 CuuDuongThanCong.com https://fb.com/tailieudientucntt TS. - NGUYỄN VIẾT ĐÔNG Hướng dẫn, đáp số BÀI TẬP TOÁN RỜI RẠC August 2, 2012 s x y z t 0. - Tuy nhiên kết quả bây giờ không phải là đường đi ngắn nhất. - Chẳng hạn trong cột y ta được đường đi sy với chiều dài 5. - Tuy nhiên đường đi syxy có chiều dài là . - 29) a) Dùng thuật toán Dijkstra ta tìm được đường đi ngắn nhất từ a đến các đỉnh e (độ dài 6): a b c d e f g h 0. - (5,b)* (8,b) (9,b) (6,f)* a b 2 1 h 2 f 1 e b) Đường đi ngắn nhất từ đỉnh a đến đỉnh d nhưng phải đi qua đỉnh e gồm các đường đi ngắn nhất từ a đến e và đường đi ngắn nhất từ e đến d. - Dùng thuật toán Dijkstra tìm được đường đi ngắn nhất từ e đến d (độ dài 4) như sau: 13 CuuDuongThanCong.com https://fb.com/tailieudientucntt TS. - NGUYỄN VIẾT ĐÔNG Hướng dẫn, đáp số BÀI TẬP TOÁN RỜI RẠC August 2, 2012 e a b c d f g h 0. - 14 CuuDuongThanCong.com https://fb.com/tailieudientucntt TS. - NGUYỄN VIẾT ĐÔNG Hướng dẫn, đáp số BÀI TẬP TOÁN RỜI RẠC August K4< K5