I. TÌM HIỂU VỀ MÔN HỌC
1. Thông tin chung
Tên học phần: Toán rời rạc
Số tín chỉ: 3
Điều kiện tiên quyết: Hoàn thành các môn nhập môn
2. Mô tả học phần
Môn học này nhằm cung cấp cho sinh viên những kiến thức cơ bản:
- Các khái niệm cơ bản của logic và mệnh đề
- Các khái niệm cơ bản về thuật toán, độ phức tạp tính toán
- Các bài toán đếm, bài toán tồn tại, bài toán liệt kê, tổ hợp
- Lý thuyết đồ thị, các dạng đồ thị
- Các hàm về đại số logic.
3. Mục tiêu của học phần đối với người học
Mục tiêu về kiến thức, kĩ năng
- Sinh viên phải nắm được các khái niệm cơ bản của toán rời rạc. Hiểu rõ được khái niệm về đồ thị, phân loại đồ thị, các bài toán tối ưu trên đồ thị, cây
- Ngoài ra sinh viên còn được cung cấp kiến thức về các hàm đại số logic.
- Học phần cung cấp các kiến thức cơ sở ngành, tạo điều kiện thuận lợi cho
- việc học tập các môn chuyên ngành, tiếp cận dễ dàng với các công nghệ mới.
- Sinh viên có thể vận dụng các kiến thức của môn học để giải quyết các bài toán tối ưu trên thực tế như: các bài toán đếm, bài toán tìm đường đi ngắn nhất, tìm cây khung nhỏ nhất,….
- Học phần trang bị cho sinh viên các kỹ năng làm việc độc lập hoặc theo nhóm.
Mục tiêu về thái độ
- Sinh viên có tính kiên trì, sáng tạo, có thái độ học tập chăm chỉ.
II. GIÁO TRÌNH MÔN TOÁN RỜI RẠC
Tài liệu bao gồm:
Phần 1: Lý thuyết tổ hợp
Chương 1. Mở đầu
1. Sơ lược về tổ hợp
2. Nhắc lại lý thuyết tổ hợp
3. Một số nguyên lý cơ bản
4. Các cấu hình tổ hợp đơn giản
Chương 2. Bài toán đếm
1 Giới thiệu bài toán
2 Nguyên lý bù trừ
3 Quy về các bài toán đơn giản
4 Công thức truy hồi
5 Phương pháp hàm sinh
6 Liệt kê
Chương 3. Bài toán tồn tại
1. Giới thiệu bài toán
2. Phương pháp phản chứng
3 Nguyên lý Dirichlet
4 Hệ đại diện phân biệt
5. Định lý Ramsey
Chương 4.Bài toán liệt kê
1. Giới thiệu bài toán
2. Thuật toán và độ phức tạp tính toán
3. Phương pháp sinh
4. Thuật toán quay lui
Chương 5. Bài toán tối
1 Phát biểu bài toán
2 Các thuật toán duyệt
3 Thuật toán nhánh cận giải bài toán tiíĩười du lịch
4 Bài toán lập lịch gia công trên hai máy
Phần 2: Lý thuyết đồ thị
Chương 1. Các khái niệm cơ bản của lý thuyết đồ thị
1. Định nghĩa đồ thị
2. Các thuật ngữ cơ bản
3. Đường đi, Chu trình, Đồ thị liên thông
4. Một số dạng đồ thị đặc biệt
Chương 2. Biểu diễn đồ thị trên máy tính
1. Ma trận kế. Ma trận trong số
2. Ma trận liên thuộc đỉnh- cảnh
3. Danh sách cạnh
4. Danh sách kể
Chương 3. Các thuật toán tìm kiếm trên đồ thị và ứng dụng
1. Tìm kiếm theo chiều sâu trên đồ thị
2. Tìm kiếm theo chiều rộng trên đồ thị
3. Tìm đường đi và kiểm tra tính liên thông
Chương 4. Đồ thị Euler và đồ thị Hamilton
1. Đồ thị Euler
2. Đồ thị Hamilton
Chương 5. Cây và cây khung của đồ thị
1 Cây và các tính chất của cây
2. Cây khung của đồ thị
3. Xây dựng tập các chu trình cơ bản của đồ thị
4. Bài toán cây khung nhỏ nhất
Chương 6. Bài toán đường đi ngắn nhất
1. Các khái niệm mở đầu
2. Đường đi ngắn nhất xuất phát từ một đỉnh
3. Thuật toán Dijdstra
4. Đường đi trong đồ thị không có chu trình
5. Đường đi ngắn nhất giữ tất cả các cập đình
Chương 7. Cơ sở Nhiệt động lực học Bài toán luồng cực đại trong mạng
1. Mạng, luồng trong mạng và bài toán luồng cực đại
2. Lát cắt. Đường tăng luồng. Đại lý Ford-Fulkerson
3. Thuật toán tìm luồng cực đại trong mạng
4. Một số bài toán luồng tổng quát
5. Một số ứng dụng trong tổ hợp
Phần 3: Hàm đại số logic
Chương 1. Mở đầu
1. Mô hình xử lý thông tin và hàm đại số lôgic
2. Các hàm đại số logic sơ cấp
3. Biểu diễn các hàm đại số lôgic qua hệ tuyển, hội, phủ đỉnh
4. Biểu diễn tối thiểu của hàm đđáioos lôgic
Chương 2. Dạng tuyển chuẩn tắc của hàm đại số lôgic
1. Các khái niệm cơ bản
2. Dạng tuyển chuẩn tắc thu gọn
3. Dạng tuyển chuẩn tắc nghẽn và dạng tuyển chuẩn tắc tối thiểu
Chương 3. Thuật toán tìm dạng tuyển chuẩn tắc tối thiểu
1. Chú ý mở đầu
2. Tìm dạng tuyển chuẩn tắc thu gọn
3. Tìm dạng tuyển chắc tắc tối thiểu
4. Sơ đồ tối thiểu
Xem thêm
Việc làm dành cho sinh viên:
Việc làm gia sư môn Toán mới nhất
Việc làm gia sư các môn cập nhật theo ngày mới nhất
Việc làm thêm nhân viên phục vụ nhà hàng/ quán cafe dành cho sinh viên
Việc làm giáo viên Toán mới nhất
Mức lương của gia sư môn Toán là bao nhiêu?