Discrete Mathematics

ĐẠI HỌC MỞ HÀ NỘI KHOA CÔNG NGHỆ THÔNG TIN

ĐỀ CƯƠNG CHI TIẾT MÔN HỌC

TOÁN RỜI RẠC

1. Thông tin chung về môn học

- Tên môn học: Toán rời rạc

- Tên tiếng Anh: Discrete Mathematics

- Mã môn học: TRR

- Số tín chỉ: 4

- Tổng số thời gian:  60 tiết (Lý thuyết: 40, Bài tập: 20)

- Môn học tiên quyết (nếu có): Cơ sở lập trình, Giải tích Toán học, Đại số và Hình giải tích

- Loại môn học (Bắt buộc hoặc Lựa chọn): Bắt buộc

2. Mục tiêu môn học

·     Về kiến thức: Cung cấp cho sinh viên nắm được các kiến thức cơ bản về lý thuyết tổ hợp, đồ thị hữu hạn, logic toán, otomat hữu hạn.

·     Kỹ năng: Rèn luyện kỹ năng tính toán, nâng cao khả năng tư duy và suy luận logic. Biết áp dụng lập trình được một số bài toán cụ thể, từ đó thấy được mối liên hệ chặt chẽ giữa môn học với các lĩnh vực của khoa học tự nhiên, kỹ thuật, đời sống.

·     Về thái độ: Nâng cao ý thức tự học, làm đủ bài tập về nhà, tích cực phát biểu ý kiến; có sáng tạo trong quá trình vận dụng kiến thức để giải quyết các bài tập và áp dụng vào các bài toán thực tế cuộc sống.

3. Chuẩn đầu ra

Sinh viên hoàn thành học phần này có thể: giải được/vẽ sơ đồ thuật toán/lập trình các bài toán cơ bản: bài toán đếm, bài toán liệt kê, bài toán tồn tại, một số bài tối ưu trên đồ thị hữu hạn, bài tập về logic toán, từ đó biết áp dụng giải một số bài toán thực tế. 

4. Tóm tắt môn học

·     Tiếng Anh:

Discrete mathematics is the part of mathematics focusing to the study of the proprieties of discrete objects.

It includes many special theories and applications which are developing rapidly since the 18^th century, especially since the appearance of first computers and the explosion of information and communications technology - ICT - at the end of the 20^th Century.

(One of the main reason as to leverage the importance of discrete mathematics is the storage and processing of information on computers is essentially discrete processes)

It includes the following main contents:

-             Set theory

-       Combinatorics

-       Finite graph and its applications

-       Mathematical logic

-        Theory of Finite Automate*

·     Tiếng Việt:

Toán rời rạc là một lĩnh vực của toán học nghiên cứu các đối tượng rời rạc. Nó bao gồm nhiều chuyên ngành lý thuyết và ứng dụng được phát triển nhanh chóng và mạnh mẽ từ thế kỷ 18 đến nay, đặc biệt là từ khi có sự xuất hiện của các máy tính điện tử đầu tiên và sự bùng nổ của công nghệ thông tin và truyền thông vào cuối thế kỷ 20

Một trong những nguyên nhân chủ yếu làm nâng tầm quan trọng của toán rời rạc là việc cất giữ và xử lý thông tin trên máy tính bản chất là các quá trình rời rạc.

Môn học bao gồm các nội dung chính:

-        Lý thuyết tập hợp

-        Tổ hợp

-        Đồ thị hữu hạn và ứng dụng

-        Logic toán

-        Ô tô mát hữu hạn*

5. Nội dung chi tiết môn học (tên các chương, mục, phân bổ số giờ tín chỉ và số tiết học đến từng chương)

Chương 1: TẬP HỢP VÀ ÁNH XẠ (03 tiết: 02 Lý thuyết + 01 Bài tập)

1.1.        Tập hợp và phần tử

1.2.        Các phép toán tập hợp

1.3.        Quan hệ tương đương và quan hệ thứ tự

1.4.        Ánh xạ

Chương 2: BÀI TOÁN ĐẾM (12 tiết: 08 Lý thuyết + 04 Bài tập)

2.1.        Phát biểu bài toán

2.2.        Khái niệm thuật toán

2.3.        Các phép toán tổ hợp không lặp

2.4.        Các phép toán tổ hợp có lặp

2.5.        Các nguyên lý đếm

Chương 3: BÀI TOÁN LIỆT KÊ (03 tiết: 02 Lý thuyết + 01 Bài tập)

3.1.        Phát biểu bài toán

3.2.        Thuật toán sinh

3.3.        Thuật toán quay lui

Chương 4: BÀI TOÁN TỒN TẠI (06 tiết: 04 Lý thuyết + 02 Bài tập)

4.1.        Phát biểu bài toán

4.2.        Các phương pháp giải bài toán tồn tại –

Chương 5: BÀI TOÁN TỔ HỢP TỐI ƯU (12 tiết: 08 Lý thuyết + 04 Bài tập)

Có thể lược bỏ đối với các chuyên ngành phi - Toán

5.1.        Phát biểu bài toán

5.2.        Thuật toán duyệt toàn bộ

5.3.        Thuật toán nhánh cận

5.4.        Thuật toán quy hoạch động rời rạc

Chương 6: ĐỒ THỊ HỮU HẠN VÀ ỨNG DỤNG (12 tiết: 08 Lý thuyết + 04 Bài tập)

6.1.        Đồ thị có hướng

6.2.        Đồ thị vô hướng

6.3.        Đồ thị Euler và đồ thị Hamilton

6.4.        Cây và các bài toán về cây

6.5.        Các bài toán tìm kiếm trên đồ thị

6.6.        Các bài toán tối ưu trên đồ thị*

Chương 7: MỘT SỐ VẤN ĐỀ CƠ BẢN TRONG LOGIC TOÁN (12 tiết: 08 Lý thuyết + 04 Bài tập)

7.1.        Mệnh đề và các phép toán mệnh đề

7.2.        Biến mệnh đề và biểu thức logic

7.3.        Các quy tắc thay thế logic

7.4.        Các quy tắc suy diễn logic

7.5.        Vị từ và lượng từ

7.6.        Hàm đại số logic

7.7.        Cổng logic và tổng hợp các mạch logic

Chương 8: OTOMAT HỮU HẠN VÀ ỨNG DỤNG (Tự học)

Có thể lược bỏ đối với các chuyên ngành phi - Toán

8.1.        Những khái niệm cơ bản về otomat hữu hạn

8.2.        Những khái niệm cơ bản về logic hình thức

8.3.        Ngôn ngữ chính quy và biểu thức chính quy

8.4.        Quan hệ giữa otomat hữu hạn và ngôn  ngữ chính quy

6. Tài liệu sử dụng:

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

[1] Nguyễn Địch, Lê Thị Thanh Thùy – Giáo trình Toán rời rạc, phần Lý thuyết và phần Bài tập – Khoa Công nghệ thông tin, Viện Đại học Mở Hà Nội.

b. Tài liệu tham khảo

[2]. Phan Đình Diệu. Lý thuyết ô tô mát hữu hạn và thuật toán. NXB ĐHTHCN. Hà Nội, 1977.

[3].  Phan Đình Diệu. Logic toán và cơ sở toán học. NXB Đại học Quốc gia Hà Nội, 2003.

[4].  Thái Thanh Sơn. Đại số học. NXB Đại học Quốc gia Hà Nội 2004

[5].  Nguyễn Đức Nghĩa, Nguyễn Tô Thành. Toán rời rạc. NXB Đại học Quốc gia Hà Nội, 2008.

[6].  Berge. C. Theorie des Graphes et ses applications. Dunod Paris 1968. Bản dịch tiếng Việt.

[7]. Iablonski. S. V. Introduction to Discrete Mathematics. NXB Nauka Moscow, 1979.

[8]. Keneth. H.Rosen. Discrete Mathematics and its applications. Mc. Graw. Hill 1994. Bản dịch tiếng Việt năm 2000.

[9].  Liu.C.L. Elements of Discrete Mathematics.  Mc.Graw. Hill, 1985.

[10]. Steiglitz. K. Combinatorial Optimization. Prentice Hall. New. Jersey 1982.

7. Hình thức – kế hoạch tổ chức giảng dạy ….(Chung)

8. Phương pháp, hình thức kiểm tra – đánh giá kết quả học tập môn học

……….(Chung)

- Tỷ lệ thang điểm đánh giá:

Tiêu chí đánh giá	Tỷ lệ
Đánh giá chuyên cần	10%
Đánh giá quá trình về chuyên môn	20%
Đánh giá kết thúc môn học	70%