CHƯƠng trình giáo dụC ĐẠi họC (Đào tạo theo hệ thống tín chỉ) ngành đÀo tạO: CÔng nghệ thông tin loại hình đào tạo: Chính quy

1. 
   Tên học phần: TOÁN RỜI RẠC 2 - Mã số TH02C
   
2. 
   Số tín chỉ: 03
   
3. 
   Trình độ: Đại học. Cho sinh viên năm thứ 2 (học kỳ 1). Lớp 5TH.
   

4. 
   Phân bổ thời gian:
   

- Thực hành: 0 tiết.

5. 
   Điều kiện tiên quyết: Các kiến thức cơ bản về tập hợp, ánh xạ, hình học sơ cấp, ma trận, các khái niệm cơ bản và các phép toán cơ bản trong số học. Biết ngôn ngữ lập trình C hoặc Pascal.
   
6. 
   Mục tiêu của học phần:
   

• 
  Sinh viên nắm được các cấu trúc đại số cơ bản Nhóm, vành, trường và các ứng dụng của chúng.
  
• 
  Sinh viên cần nắm được khái niệm số nguyên tố, hợp số, phép chia hết, chia có dư và các tính chất, UCLN, BCNN, biết cách giải các phương trình, hệ phương trình đồng dư và bước đầu vận dụng các kiến thức đó các bài toán mã hóa..
  
• 
  Sinh viên nắm được các khái niệm trong đồ thị, các dạng đồ thị và cách biểu diễn một đồ thị.
  
• 
  Sinh viên nắm vững các thuật toán của các bài toán: Tìm đường đi ngắn nhất, tìm cây khung có trọng số bé nhất, cây phân nhánh có trọng số nhỏ nhất và các bài toán luồng cực đại.
  

7. 
   Mô tả tóm tắt nội dung học phần:
   

- Giới thiệu các cấu trúc đại số: nhóm, vành và trường.

- Giới thiệu các khái niệm cơ bản trong đồ thị, các thuật toán ứng dụng giải quyết các bài toán tìm đường đi ngắn nhất, tìm cây khung có trọng số bé nhất và các bài toán luồng cực đại.

8. 
   Nhiệm vụ của học sinh:
   

- Làm bài tập tại lớp.

- Làm bài tập lớn theo nhóm.

9. Tài liệu học tập.

[1] Giáo trình toán rời rạc 2, Đại học Cần Thơ.

[2] GS. Phạm Thế Long, TS. Nguyễn Xuân Viên, TS. Nguyễn Thiện Luận, TS. Nguyễn Đức Hiếu, TS. Nguyễn Văn Xuất, Giáo trình toán rời rạc, NXB Đại học sư phạm.

[3] Đỗ Văn Nhơn, Giáo trình toán rời rạc, ĐH KHTN TP Hồ Chí Minh

[4] Nguyễn Hữu Anh, Toán rời rạc, NXB Lao động XH.

[6] Hà Huy Khoái, Số học và thuật toán, Viện toán học.

[7] Hoàng Xuân Sính, Đại số đại cương, NXB Giáo dục.

[8] Nguyễn Cam, Chu Đức Khánh, Lý thuyết đồ thị, NXB TP Hồ Chí Minh, 1999.

- Bài tập tại lớp.

- Bài tập lớn.

- Bài kiểm tra: Trung bình (Bài kiểm tra giữa học phần + Bài tập lớn)

- Thi kết thúc học phần. Hình thức thi – Tự luận mở. Thời gian thi: 90 phút.

11. Thang điểm: 10

12. Nội dung chi tiết học phần

NỘI DUNG	LT	BT	GHI CHÚ
Chương I: Cấu trúc đại số Nhóm – Vành – Trường I. Phép toán hai ngôi trên một tập hợp. I.1 Tập hợp. I.2. Ánh xạ. I.2.1 Khái niệm về ánh xạ. I.2.2 Các tính chất của ánh xạ. I.3 Phép toán hai ngôi trên một tập hợp. I.3.1 Định nghĩa I.3.2 Tập con ổn định đối với phép toán hai ngôi. I.3.3 Các tính chất của phép toán hai ngôi. II. Nửa nhóm II.1 Nửa nhóm – Nửa nhóm con. II.2 Lũy thừa. III Nhóm III.1 Nhóm. III.2 Nhóm con. IV. Vành IV.1 Vành IV.2 Ước của phần tử không – Miền nguyên IV.3 Vành con IV.4 Idean và idean chính IV.5 Tính chất số học trong vành V. Trường V.1 Trường V.2 Trường con V.3 Trường Galois	8	4
Chương II: Lý thuyết chia hết và đồng dư I. Phép chia hết và chia có dư trên vành số nguyên. I.1Phép chia hết. I.2 Tính chất của phép chia hết. I.3 Phép chia có dư. II. Ước chung lớn nhất. II.1 Một số định nghĩa. II.2 Sự tồn tại UCLN. II.3 Các tính chất của UCLN. II.4 Thuật toán Euclide. III. Bội chung nhỏ nhất III.1 Một số định nghĩa. III.2 Sự tồn tại BCNN. III.3 Các tính chất của BCNN. IV. Số nguyên tố và hợp số IV.1 Số nguyên tố và hợp số. IV.2 Tập hợp số nguyên tố. IV.3 Sàng Ơratosten. IV.4 Định lý cơ bản của số học. IV.5 Một số vấn đề về số nguyên tố. V. Phương trình nguyên V.1 Phương trình bậc nhất hai ẩn. V.2 Phương trình bậc nhất nhiều ẩn. V.3 Phương trình bậc cao. VI. Quan hệ đồng dư. VI.1 Quan hệ đồng dư. VI.2 Tính chất của quan hệ đồng dư. VII. Vành các lớp thặng dư VII.1 Vành các lớp thặng dư. VII.2 Hệ thặng dư đầy đủ và hệ thặng dư thu gọn. VII.3 Định lý Euler. VII.4 Định lý Fermat. VIII. Phương trình đồng dư một ẩn VIII.1 Phương trình đồng dư. VIII.2 Nghiệm của phương trình đồng dư. VIII.3 Phương trình đồng dư tương đương. VIII.4 Phương trình đồng dư bậc nhất một ẩn. VIII.5 Mối quan hệ giữa phương trình đồng dư bậc nhất một ẩn và phương trình Diophante. IX. Hệ phương trình đồng dư bậc nhất một ẩn IX.1 Định nghĩa. IX.2 Điều kiện để hệ phương trình đồng dư có nghiệm. IX.3 Giải hệ phương trình đồng dư bằng phương pháp thế. X. Phương trình đồng dư bậc cao một ẩn X.1 Dạng tổng quát. X.2 Cách giải. XI. Ứng dụng của lý thuyết đồng dư XI.1 Các hàm băm. XI. 2 Các số giả ngẫu nhiên. XI.3 Mật mã.	8	4
Chương III: Đại cương về đồ thị I. Các định nghĩa và các khái niệm cơ bản. I.1 Đồ thị có hướng. I.2 Đồ thị và ánh xạ. I.3 Đồ thị vô hướng. I.4 Các khái niệm thường gặp. II Biểu diễn đồ thị. II.1 Ma trận đỉnh cung. II..2 Ma trận đỉnh cạnh. II..3 Ma trận đỉnh đỉnh. II.4 Danh sách liên kết. III. Đường đi và chu trình. III.1 Đường đi và chu trình trên đồ thị vô hướng. III.2 Đường đi và chu trình trên đồ thị có hướng. IV. Đồ thị liên thông – Bộ phận liên thông. I.3.4 Xác định bộ phận liên thông. I.3.5 Đồ thị liên thông mạnh – Bộ phận liên thông mạnh. V. Đồ thị Euler. V.1 Bài toán bảy cây cầu ở Konigsberg. V.2 Đồ thị Euler. V.3 Định lý Euler. V.4 Thuật toán tìm chu trình Euler. VI. Đồ thị Hamilton. VI.1 Bài toán Hamilton. VI.2 Đồ thi Hamilton. VI.3 Các định lý. VI.4 Thuật toán tìm chu trình Hamilton.	6	2
Chương IV: Đường đi ngắn nhất I. Bài toán tìm đường đi ngắn nhất. I.1 Bài toán. I.2 Các ví dụ. I.3 Điều kiện tồn tại đường đi ngắn nhất. II. Các thuật toán cơ bản tìm đường đi ngắn nhất II.1 Thuật toán Moore – Dijkstra ( l(u)>=0). II.2 Trường hợp l(u)=1. II.3 Trường hợp l(u) bất kỳ. II.4 Giải thuật ma trận. III. Bài toán trung tâm về tổ chức thi công III.1 Bài toán. III.2 Mô hình đồ thị bài toán GANT. III.3 Mô hình đồ thị bài toán PERT.	6	4
Chương V: Cây và cây có hướng I. Cây I.1 Định nghĩa. I.2 Tính chất của cây. I.3 Giải thuật xây dựng rừng tối đại. I.4 Định lý. I.5 Cây bù. II. Cây khung với trọng lượng bé nhất (Cây bao trùm tối tiểu). II.1 Bài toán cây khung với trọng lượng bé nhất. II.2 Sự tồn tại cây khung có trọng lượng bé nhất II.3 Giải thuật Kruskal. II.4 Giải thuật Prim. III. Cây có hướng III.1 Định nghĩa. III.2 Định lý. III.3 Bài toán cây phân nhánh có trọng số bé nhất. III.4 Giải thuật.	4	4
Chương VI: Luồng cực đại trong mạng. I. Mạng và luồng trong mạng. I.1 Mạng. I.2 Luồng trong mạng. I.3 Bài toán luồng trong mạng. II. Lát cắt – Sự tăng luồng II.1 Lát cắt. II.2 Sự tăng luồng trong mạng. III. Tìm luồng cực đại trong mạng III.1 Gán nhãn cho các đỉnh. III.2 Tăng luồng. IV. Bài toán tổng quát về luồng trong mạng IV.1 Mạng với nhiều điểm phát và điểm thu. IV.2 Mạng với khả năng thông qua của cung và của đỉnh. IV.3 Mạng với khả năng thông qua của cung bị chặn.	3	2
Tổng cộng	35	20

13. Ngày phê duyệt: 09/2012

14. Cấp phê duyệt: Bộ môn Hệ Thống Thông Tin