Giáo trình Toán rời rạc | Đại học Bách khoa Hà Nội

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

Bài giảng học phần Toán rời rạc

Đề cương học phần Toán rời rạc

Đề thi học phần Toán rời rạc 

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?