Đề cương ôn tập môn Toán rời rạc

by **admin** Mon Aug 06, 2012 10:42 pm

Một số câu hỏi ôn tập thi vấn đáp Toán rời rạc
1. Khái niệm mệnh đề, các phép toán mệnh đề
2. Thế nào là hằng đúng, mâu thuẫn, tiếp liên
3. Khái niệm hàm mệnh đề, hàm mệnh đề 2 biến, 3 biến
4. Khái niệm lượng từ tồn tại, với mọi
5. Các quy tắc suy luận
6. Các phương pháp chứng minh, cơ sở của các phương pháp
7. Nguyên lý quy nạp thứ 1, thứ 2
8. Tính đúng đắn của một chương trình
9. Khái niệm hàm boole
10. Biểu diễn hàm Boole bằng phương pháp khai triển tổng các tích
11. Các cổng logic, tổ hợp các cổng
12. Phương pháp Karnaught cực tiểu hóa các mạch
13. Nguyên lý đếm cơ bản ( cộng, nhân)
14. Nguyên lý bù trừ
15. Biểu đồ cây
16. Nguyên lý Dirichlet
17. Hoán vị, chỉnh hợp, tổ hợp
18. Hệ sô nhị thức- Định lý hằng đẳng thức Pascal
19. Chỉnh hợp lặp, tổ hợp lăp
20. Thuật toán sinh hoán vị theo thứ tự từ điển
21. Sinh tổ hợp- thuật toán sinh xâu nhi phân liền sau. Biểu diễn tập con trên máy tính
22. Khái niệm quan hệ 2 ngôi, quan hệ n ngôi, cơ sở dữ liệu
23. Quan hệ tương đương
24. Biểu diễn quan hệ bằng ma trận, đồ thị có hướng
25. Khái niệm bao đóng, bao đóng phản xạ, đối xứng
26. Thuật toán tìm bao đóng bắc cầu
27. Khái niệm đơn đồ thị, đa đồ thị, giả đồ thị, đồ thị có hướng
28. Đường đi, chu trình, đường đi đơn, chu trình đơn
29. Đồ thị liên thông, đồ thị nhiều thành phần liên thông
30. Đồ thị phẳng, công thức Euler
31. Một số đồ thị đặc biệt: đồ thị đầy đủ, đồ thị vòng, đồ thị bánh xe, đồ thị phân đôi
32. Đồ thị Euler, nửa Euler. Định lý điều kiện cần và đủ để đồ thị là Euler, nửa Euler
33. Đồ thị Hamilton. Định lý Dirak 1952
34. Đường đi ngắn nhất trong đồ thị không trọng số. Tìm số đường đi có độ dài n ( Định lý 2 trang 543- Toán rời rạc ứng dụng trong tin học)
35. Đường đi ngắn nhất trong đồ thị có trọng số. Thuật toán Dijstra
36. Đồ thị đối ngẫu. Tô màu đồ thị, sắc số đồ thị, định lý 4 màu
37. Khái niệm cây, cấu trúc cây
38. Khái niệm cây nhị phân, nhị phân đầy đủ, cây tìm kiếm nhị phân
39. Các phương pháp duyệt cây
40. Khái niệm cây khung, cây khung nhỏ nhất, thuật toán tìm cây khung nhỏ nhất

Một số dạng bài tập thi vấn đáp Toán rời rạc
1. Cho các mênh đề phức, xác định giá trị chân lý của mệnh đề
2. Chứng minh mênh đề tương đương
3. Dịch từ logic sang mệnh đề và ngược lại
4. Xác đinh giá trị chân lý của hàm mệnh đề với các giá trị cụ thể của biến hoặc lượng từ
5. Quy tắc suy luận để suy diến câu
6. Các phương pháp chứng minh định lý, đặc biệt quy nap
7. Cho biểu thức Boole, Xác đinh giá trị của hàm boole ứng với biểu thức này
8. Tìm biểu thức biểu diễn hàm bằng phương pháp khai triển tổng các tích
9. Phương pháp Karnaught cực tiểu hóa các mạch, vẽ mạch
10. Các nguyên lý đếm cơ bản, bù trừ ( trường hợp 3 tập hợp )
11. Nguyên lý Dirichlet
12. Hoán vị, chỉnh hợp, tổ hợp
13. Tìm hệ số nhị thức dùng tam giác Pascal
14. Chỉnh hợp lặp, tổ hợp lặp
15. Thuật toán sinh hoán vị, sinh xâu nhị phân liền sau ( khái niệm Tổ hợp- Tập con)
16. Cho quan hệ, kiểm tra tương đương ( kiểm tra 3 tính chất phản xạ, đối xứng, bắccầu)
17. Cho quan hệ, biểu diễn quan hệ, kiểm tra tính đối xứng, phản xạ
18. Tìm bao đóng phản xạ, đối xứng, bắc cầu của quan hệ
19. Cho đồ thi không trọng số ( có hướng, vô hướng). Tìm tất cả các đường đi độ dài n
20. Cho đồ thị có trọng số. Tìm đường đi ngắn nhất theo thuật toán Dị jstra
21. Cho bài toán lập lịch thi, tô màu đồ thị để tìm số ca thi ít nhất có thể
22. Cho bản đồ, tô màu đồ thị đối ngẫu của bản đồ
23. Cho dãy đã sắp xếp, biểu diễn dãy trên cây tìm kiếm nhi phân. Áp dụng tìm 1 phần tử
24. Cho đồ thi, tìm cây khung nhỏ nhât theo thuật toán Kruskal hoặc Prim
25. Cho đồ thi, tìm tất cả các cây khung của đồ thị
Chú ý:
Phần lý thuyết sẽ hỏi sinh viên 1 đến 3 câu
Phần bài tập số lượng 1 đến 2 câu
Câu trong đề thi có thể chỉ là một ý của một câu ở phần ôn tập này
Chúc các em ôn tập tốt