ĐẠ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 18th century,
especially since the appearance of first computers and the explosion of
information and communications technology - ICT - at the end of the 20th 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%
|
