ĐỀ CƯƠNG ÔN TẬP MÔN TOÁN
(30 tiết)
MỤC TIÊU
(30 tiết)
MỤC TIÊU
Hệ thống lại một số kiến thức quan trọng của các môn học cơ sở Toán cho Tin học
NỘI DUNG
I- Cơ sở lôgic (5 tiết)
1. Phép tính mệnh đề và vị từ
- Khái niệm về mệnh đề và vị từ
- Các phép tính cơ bản NOT - AND - OR
2. Quy tắc suy luận
- Quy tắc cộng
- Quy tắc rút gọn
- Quy tắc Modus Ponens
- Quy tắc Modus Tollens - Chứng minh phản chứng
- Tam đoạn luận
3. Nguyên lý quy nạp
- Nguyên lý quy nạp - Hệ tiên đề Peano
- Chứng minh quy nạp
II- Đại số bool (7 tiết)
1. Quan hệ thứ tự và tập hợp thứ tự
- Quan hệ thứ tự
- Tập hợp thứ tự - Sơ đồ Hasse
- Các phần tử đặc biệt trên một tập hợp thứ tự
2. Dàn (lattice) và đại số bool
- Định nghĩa dàn và đại số bool
- Các tính chất của dàn và đại số bool
3. Hàm bool
- Hàm bool n biến
- Đại số bool các hàm bool
- Dạng tuyển chuẩn tắc và dạng hội chuẩn tắc
4. Công thức tối tiểu của hàm bool
- Định nghĩa công thức tối tiểu của hàm bool
- Các phương pháp tìm công thức tối tiểu: Karnaugh, Consensus và Mc. Quine Cluskey
5. Hệ phương trình bool và hệ phủ tối tiểu
- Định nghĩa hệ phương trình bool
- Phương pháp giải hệ phương trình bool
- Bài toán phủ tối tiểu
III- Phép đếm (3 tiết)
1. Nguyên lý cộng, nguyên lý nhân và nguyên lý bù trừ
2. Giải tích tổ hợp
3. Nguyên lý Dirichlet
4. Công thức đệ quy
IV- Lý thuyết đồ thị (10 tiết)
1. Đại cương về đồ thị
- Định nghĩa và các thuật ngữ cơ bản về đồ thị
- Phân loại đồ thị
2. Đồ thị liên thông
- Khái niệm về liên thông, liên thông mạnh và liên thông yếu
- Giải thuật kiểm tra tính liên thông
3. Đường đi ngắn nhất (Shortest Path Problem)
- Bài toán đường đi ngắn nhất
- Giải thuật tìm đường đi ngắn nhất Dijkstra , Ford và Floyd
4. Cây khung có trọng lượng nhỏ nhất (Minimum Spanning Trees)
- Bài toán cây khung có trọng lượng nhỏ nhất
- Giải thuật tìm cây khung có trọng lượng nhỏ nhất Kruskal và Prim
5. Luồng cực đại trên mạng
- Bài toán luồng cực đại trên mạng
- Giải thuật xác định luồng cực đại trên mạng: Ford - Fulkerson
V- Số học (5 tiết)
1. Lý thuyết chia
- Phép chia hết và chia có dư
- Ước chung lớn nhất, bội chung nhỏ nhất
- Số nguyên tố và hợp số
2. Lý thuyết đồng dư
- Quan hệ đồng dư và các tính chất
- Phương trình đồng dư bậc nhất một ẩn
- Hệ phương trình đồng dư bậc nhất một ẩn
TÀI LIỆU THAM KHẢO
[1] Nguyễn Đức Nghĩa và Nguyễn Tô Thành- Toán rời rạc
Nhà xuất bản Giáo dục 1997
[2] Nguyễn Hữu Anh - Toán rời rạc
Nhà xuất bản Giáo dục 1999
[3] Khoa CNTT&TT - Bài giảng Toán rời rạc 1,2,3,4
Đại học Cần Thơ 2005
[4] Nguyễn Tiến Tài và Nguyễn Hữu Hoan - Số học
Nhà xuất bản Giáo dục 2001
[5] J. Vélu - Méthodes mathématiques pour l'informatique
Dunod 1989
[6] J. E. Munro - Discrete mathematic for computing
Thomas Nelson Australia 1992