BÀI TẬP THỰC HÀNH TOÁN RỜI RẠC
1. Khối lượng: 1 TC
- Giờ bài tập và thảo luận: (10 tiết)
- Sinh viên tự học: (20 tiết)
2. Học phần tiên quyết: Tin học đại cương.
3. Học phần học trước, song hành: Đại số, Toán rời rạc.
4. Mục tiêu:
Học phần giúp cho sinh hiểu hiểu rõ hơn lý thuyết và ứng dụng kiến thức lý thuyết giải quyết các bài toán thực tế.
Sinh viên phải hiểu rõ kiến thức lý thuyết liên quan. Sinh viên phải chuẩn bị trước các bài thực hành.
Các bài thực hành nhằm giúp cho sinh hiểu các thuật toán đã được học trong lý thuyết.
5. Nhiệm vụ của sinh viên:
- Dự lớp và tham gia thảo luận
- Làm bài tập
- Thi cuối học kỳ
6. Tài liệu học tập:
[1] Nguyễn Đức Nghĩa-Nguyễn Tô Thành, Toán rời rạc, NXB Giáo dục, 1999.
[2] Kenneth H.Rosen, Toán học rời rạc ứng dụng trong tin học, NXB Giáo dục, 2007.
[3] Chu Đức Khánh, Lý thuyết đồ thị, NXB Đại học Quốc gia TP Hồ Chí Minh, 2002.
[4] Richard Johnsonbaugh, Discrete Mathematics, Macmillan Publishing Company, 1986.
[5] James L. Hein, Discrete Mathematics, Jones and Bartiett Publishers, 1996.
7. Phương thức đánh giá tiếp thu học phần:
- Giáo viên hướng dẫn đánh giá: (quá trình thực hiện, tinh thần học tập..) trọng số: 0.4
- Đánh giá kết thúc học phần: trọng số: 0.6 Hình thức:
8. Nội dung chi tiết học phần:
Bài tập 1. Bài toán đếm-Bài toán liệt kê
1. Đếm số xâu nhị phân độ dài n:
a) Bất kỳ.
b) Không có hai bit 0 kề nhau.
c) Có ít nhất hai bit 0 kề nhau.
2. Viết chương trình liệt kê tất cả các xâu nhị phân độ dài n như yêu cầu của bài toán 1. Liệt kê có số thứ tự để kiểm tra kết quả đã đếm được. Thử nhập với nhiều giá trị khác nhau của n. Lưu ý các trường hợp n=1 và n=2.
3. Viết chương trình nhập một xâu chữ gồm n chữ cái hoa (A..Z)-trong đó có một số chữ cái lặp. Liệt kê tất cả các cách sắp xếp n chữ cái này. Có đếm tổng số cách sắp xếp.
4. Xét phương trình nguyên: x1+x2+..+xn=k với xi≥0 "i=1..k. Viết chương trình nhập n,k và in ra tất cả các nghiệm của phương trình.Có đếm tổng số nghiệm.
Bài tập 2. Bài toán tối ưu rời rạc
1. Viết chương trình nhập n là số chi tiết cần gia công và nhập thời gian gia công trên hai máy của từng chi tiết. Tính và in thời gian hoàn thành gia công nhanh nhất.
2. Viết chương trình nhập n là số thành phố và nhập ma trận khoảng cách Cnxn=(cij)nxn. Tìm hành trình ngắn nhất cho người du lịch.
Bài tập 3. Bài toán trên đồ thị
1. Viết chương trình phát sinh ngẫu nhiên ma trận trọng số Anxn=(aij)nxn của đồ thị vô hướng liên thông G gồm n đỉnh (aij=aji "i,j=1..n).
a) Kiểm tra đồ thị G có phải là đồ thị Euler hay không.
b) Nhập hai đỉnh x,y và dùng thuật toán Dijkstra để tìm đường đi ngắn nhất từ x đến y.
c) Dùng thuật toán Prim để tìm cây phủ nhỏ nhất của đồ thị G.
Bài tập 4. Bài toán luồng cực đại trên mạng
1. Viết chương trình nhập n là số đỉnh và nhập ma trận khoảng cách khả năng thông qua của các cung Cnxn=(cij)nxn, với quy ước đỉnh v1 là đỉnh nguồn và vn là đỉnh đích. Dùng thuật toán Ford-Fulkerson để tìm luồng cực đại trên mạng đã nhập.
Bài tập 5. Bài toán tối thiểu hoá mạch logic
1. Viết chương trình nhập n là bậc của hàm Boole f và nhập bảng giá trị đầy đủ của f. Dùng thuật toán Quine-McKluskey để tìm biểu thức tối thiểu. In ra kết quả dưới dạng bảng chân trị.
Nguồn:itf.dut.edu.vn