Bài tập lớn Toán rời rạc | Đại học Kinh tế kỹ thuật công nghiệp

lOMoAR cPSD| 45740153 BÀI TẬP LỚN
HỌC PHẦN TOÁN RỜI RẠC I. Tự luận
Bài 1 Một xâu nhị phân được gọi là Palindrome nếu ta đảo ngược xâu đó sẽ
cho kết quả là chính nó. Ví dụ các xâu 101101101, 1111, 01010 là Palindrome.
Hãy đếm số xâu Palindrome có độ dài n.
Bài 2 Nam có 8 tờ tiền loại 1, 2, 3, 4, 5, 6, 7, 8 nghìn đồng. Nam cho Hoa rút
ngẫu nhiên 5 tờ của mình. Hãy chứng minh, Hoa bao giờ cũng có ít nhất hai tờ tiền
có tổng giá trị là 9 nghìn đồng.
Bài 3 Tìm số nghiệm nguyên không âm của phương trình: x1 + x2 + x3 + x4 =
20, thỏa màn điều kiện x1 ≤ 3; x2 ≥2; x3 >4
Bài 4 Trong một cuộc hội thảo khoa học, một số nhà khoa học bắt tay nhau.
Hãy chứng minh số người bắt tay với một số lẻ người khác là một số chẵn.
Bài 5 Cho đồ thị được biểu diễn bằng hình dưới đây.
a) Viết thứ tự các đỉnh được thăm của đồ thị theo thuật toán BFS, DFS.
b) Tìm đường đi ngắn nhất từ đỉnh 0 đến các đỉnh còn lại của đồ thị bằng thuật toán Dijkstra.
c) Tìm cây khung nhỏ nhất của đồ thị trên bằng thuật toán Kruskal.
d) Tìm cây khung nhỏ nhất của đồ thị trên bằng thuật toán Prim. II. Lập trình
1. Lập trình cài đặt thuật toán duyệt đồ thị theo chiều rộng (BFS).
2. Lập trình cài đặt thuật toán duyệt đồ thị theo chiều sâu (DFS).
3. Lập trình cài đặt thuật toán tìm cây khung nhỏ nhất của đồ thị theo thuật toán Prim.
4. Lập trình cài đặt thuật toán tìm đường đi ngắn nhất từ một đỉnh đến các
đỉnh còn lại của đồ thị theo thuật toán Dijkstra.
5. Lập trình cài đặt thuật toán nhánh cận giải bài toán cái túi.
6. Lập trình cài đặt thuật toán nhánh cận giải bài toán người du lịch.