Đề cương môn học Toán rời rạc | Đại học Hoa Sen

lOMoAR cPSD| 47206521
ĐỀ CƯƠNG MÔN HỌC MSMH Tên môn học Số tín chỉ TOÁN RỜI RẠC KHTQ105DV01 03 Discrete Mathematics
Sử dụng kể từ học kỳ: 17.1A năm học 2017 - 2018 theo quyết ịnh số 742/QĐ-ĐHHS ký
ngày 20/06/2017 của Hiệu trưởng trường ĐH Hoa Sen.
A. Quy cách môn học: Số tiết
Số tiết phòng học Tổng Lý Thực
Đi thực Tự Phòng lý Phòng Đi thực Bài tập số tiết thuyết hành tế học
thuyết thực hành tế (1) (2) (3) (4) (5) (6) (7) (8) (9) 45 45 0 0 90 45 0 0
(1) = (2) + (3) + (4) + (5) = (7) + (8) + (9)
B. Liên hệ với môn học khác và iều kiện học môn học: Liên hệ Mã số môn học Tên môn học
Môn tiên quyết: Không có môn tiên quy ết
C. Tóm tắt nội dung môn học:
Môn học dành cho sinh viên chuyên ngành công nghệ thông tin, nhằm giới thiệu các khái niệm
cơ bản của toán học như: logic, mệnh ề, tập hợp, ánh xạ, thuật toán, quan hệ tương ương, v.v... Môn
học cũng cung cấp cho sinh viên các phép suy luận, phương pháp chứng minh, lý thuyết ồ thị và các
ứng dụng của nó trong thực tế. D. Mục tiêu của môn học: Stt
Mục tiêu của môn học
Trình bày các khái niệm cơ bản của môn học, 1
Trang bị các phương pháp chứng minh và suy luận, giúp sinh có khả năng
mô hình hóa và giải quyết các vấn ề liên quan, phát sinh trong ngành học 2 của mình.
E. Kết quả ạt ược sau khi học môn học: Stt
Kết quả ạt ược
Hiểu các khái niệm cơ bản trong chương trình, 1 lOMoAR cPSD| 47206521
Biết áp dụng các kiến thức ã học trong các vấn ề cụ thể liên quan ến các 2 mô hình ã học,
Có khả năng giải quyết các vấn ề phát sinh trong các lĩnh làm việc, nghiên
cứu của mình. Xây dựng ược các mô hình toán học và các thuật toán phù 3
hợp ể giải quyết vấn ề.
F. Phương thức tiến hành môn học:
Loại hình phòng Số tiết 1 Phòng lý thuyết 45
2 Phòng thực hành máy tính 0 Tổng cộng 45 Yêu cầu :
+ Ngôn ngữ sử dụng giảng dạy, học tập: tiếng Việt
+ Các yêu cầu ối với sinh viên khi tham gia môn học: Đọc trước các tài liệu học tập, làm bài tập
trên lớp, bài tập về nhà và nộp bài tập theo yêu cầu của giảng viên.
+ Cách tổ chức giảng dạy môn học:
STT Cách tổ chức giảng dạy Mô tả ngắn gọn Số tiết Sĩ số SV tối a 1 Giảng trên lớp (lecture) 45 60
G. Tài liệu học tập:
1. Tài liệu bắt buộc: [1] Kenneth H. Rosen, Discrete Mathematics and Its Applications (Fourth Edition), McGraw-Hill, 2000.
2. Tài liệu không bắt buộc (tham khảo):
[2] Nguyen Huu Anh, Discrete Mathematics, “Lao Dong Xa Hoi” publisher, Hanoi, 2006
(Tiếng Việt) [3] Hoang Chung, Introduction to Finite Mathematics, Education Publisher, Hanoi, 1999
(Tiếng Việt) [4] Do Duc Giao, Discrete Mathematics, Vietnam National University-Hanoi, Hanoi, 2000 (Tiếng Việt)
[5] Nguyen Duc Nghia, Nguyen To Thanh, Discrete Mathematics (Seventh Edition),
Vietnam National University-Hanoi, Hanoi, 2007 (Tiếng Việt)
[6] R.P. Grimaldi, Discrete and Combinatorial Mathematics: An Applied Introduction
(Fifth Edition), Pearson, 2004 [7]
Bài tập do giảng viên biên soạn.
H. Đánh giá kết quả học tập môn học:
1. Thuyết minh về cách ánh giá kết quả học tập
Sinh viên học môn “Toán rời rạc” sẽ ược ánh giá trên 3 loại hình:
- Đánh giá chuyên cần: Sinh viên phải i học ầy ủ và làm bài tập về nhà, giảng viên theo dõi
và ánh giá sinh viên trong suốt quá trình học, chiếm 20%.
- Làm bài tập, bài kiểm tra tại lớp và bài tập nhóm, nộp cho giảng viên chấm iểm, chiếm 30%. lOMoAR cPSD| 47206521
- Thi cuối kỳ: Sinh viên làm bài thi viết trong thời gian 90 phút, theo lịch của Phòng Đào tạo, chiếm 50%.
2. Tóm tắt cách ánh giá kết quả học tập * Đối với học kỳ chính: Thành Thời Trọng
Tóm tắt biện pháp ánh giá Thời iểm phần lượng số Kiểm tra
GV theo dõi chuyên cần và việc làm 20% Tuần 1 ến 1
bài tập về nhà của SV tuần 14 Kiểm tra
SV làm bài tập tại lớp và bài tập Tuần 1 ến 30% 2 nhóm nộp GV tuần 14 Thi cuối 90 phút
Bài thi viết. Được sử dụng tài liệu
50% Theo lịch học kỳ PĐT Tổng 100%
* Đối với học kỳ phụ: Môn học này không dạy ở học kỳ phụ.
3. Tính chính trực trong học thuật (academic integrity)
Chính trực là một giá trị cốt lõi và mang tính quyết ịnh cho chất lượng ào tạo của một trường ại học.
Vì vậy, ảm bảo sự chính trực trong giảng dạy, học tập, và nghiên cứu luôn ược chú trọng tại Đại học
Hoa Sen. Cụ thể, sinh viên cần thực hiện những iều sau:
2.1. Làm việc ộc lập ối với những bài tập cá nhân: Những bài tập hoặc bài kiểm tra cá nhân
nhằm ánh giá khả năng của từng sinh viên. Sinh viên phải tự mình thực hiện những bài tập
này; không ược nhờ sự giúp ỡ của ai khác. Sinh viên cũng không ược phép giúp ỡ bạn khác
trong lớp nếu không ược sự ồng ý của giảng viên. Đối với bài kiểm tra (cả tại lớp và tự làm ở
nhà), sinh viên không ược gian lận dưới bất cứ hình thức nào.
2.2. Không ạo văn: Đạo văn (plagiarism) là việc sử dụng ý, câu văn, hoặc bài viết của người khác
trong bài viết của mình mà không có trích dẫn phù hợp. Sinh viên sẽ bị xem là ạo văn nếu: i.
Sao chép nguyên văn một câu hay một oạn văn mà không ưa vào ngoặc kép và không có trích dẫn phù hợp. ii.
Sử dụng toàn bộ hay một phần bài viết của người khác. iii.
Diễn ạt lại (rephrase) hoặc dịch (translate) ý tưởng, oạn văn của người khác mà không có trích dẫn phù hợp. iv.
Tự ạo văn (self-plagiarize) bằng cách sử dụng toàn bộ hoặc phần nội dung chủ yếu của
một ề tài, báo cáo, bài kiểm tra do chính mình viết ể nộp cho hai (hay nhiều) lớp khác nhau.
2.3. Có trách nhiệm trong làm việc nhóm: Các hoạt ộng nhóm, bài tập nhóm, hay báo cáo nhóm
vẫn phải thể hiện sự óng góp của cá nhân ở những vai trò khác nhau. Báo cáo cuối kỳ của sinh
viên nên có phần ghi nhận những óng góp cá nhân này.
Bất kỳ hành ộng không chính trực nào của sinh viên, dù bị phát hiện ở bất kỳ thời iểm nào
(kể cả sau khi iểm ã ược công bố hoặc kết thúc môn học) ều sẽ dẫn ến iểm 0 ối với phần kiểm
tra tương ứng, hoặc iểm 0 cho toàn bộ môn học tùy vào mức ộ. (tham khảo
Chính sách Phòng tránh Đạo văn tại: http://thuvien.hoasen.edu.vn/chinh-sach-phong-tranh-
daovan). Để nêu cao và giữ vững tính chính trực, nhà trường cũng khuyến khích sinh viên báo cáo
cho giảng viên và Trưởng Khoa những trường hợp gian lận mà mình biết ược.
I. Phân công giảng dạy: lOMoAR cPSD| 47206521 STT Họ và tên
Thông tin liên lạc Lịch Vị trí giảng tiếp SV dạy 1 Đặng Công Tiên tien.dangcong@hoasen.edu.vn Giảng viên
2 ThS. Lê Thị Ngọc Huyên huyen.lethingoc@hoasen.edu.vn Giảng viên 3 ThS. Nguyễn Lê Duy duy.nguyenle@hoasen.edu.vn Giảng viên
J. Kế hoạch giảng dạy:
• Đối với học kỳ chính: Tuần/ Tên bài giảng
Sách tham Công việc sinh Buổi khảo viên phải hoàn thành 1/1
Chương 1. Logic, ánh xạ và quan hệ [1] 1.1. Logic -
Khái niệm mệnh ề, kí hiệu mệnh ề -
Các loại mệnh ề: phức hợp, phủ ịnh, hội, tuyển,
tuyển loại, kéo theo, ảo, nghịch ảo, phản ảo, tương
ương và các bảng giá trị chân lý tương ứng -
Thứ tự ưu tiên của các toán tử logic, dịch
những câu thông thường, mô tả hệ thống, tìm kiếm
Boole, các phép toán logic và bit
1.2. Sự tương ương giữa các mệnh ề Mở ầu: -
Định nghĩa 1 Các tương ương logic: - Định nghĩa 2 -
Bảng 5 (trang 22) và bảng 6 (trang 23) 2/2
1.3. Vị từ và lượng từ (trang 26…) [1] - Hàm mệnh ề - vị từ - Định nghĩa 1 (trang 27) - Định nghĩa 2 (trang 29) - Bảng 1 (trang 30) - Bảng 2 (trang 32)
- Dịch các câu… (trang 32)
- Lập trình logic (trang 35)
- Các lượng từ lồng nhau (lượng từ 2 biến- trang 41- 48)
1.4. Các phương pháp chứng minh
1.4.1. Các quy tắc suy luận
- Bảng 1: Các quy tắc suy luận( trang 55)
- Bảng 2: qui tắc suy luận cho các câu ược lượng hóa (trang 60) lOMoAR cPSD| 47206521 3/3
1.4. Các phương pháp chứng minh (tiếp theo) [1]
1.4.2. Các phương pháp chứng minh ịnh lý: trực tiếp,
gián tiếp, ngớ ngẩn, tầm thường, phản chứng, từng
trường hợp (trang 62-67…)
1.4.3. Định lý và lượng từ (trang 68)
1.5. Tập hợp, phép toán trên tập hợp, ánh xạ -
Định nghĩa 1, 2, 3, 4, 5, 6 (trang 77 ến 81) - Định lý 1 -
Định nghĩa 7, 8, 9, 10 (trang 81 ến 83) Các
phép toán trên tập hợp: -
Định nghĩa 1, 2, 3, 4, 5 (trang 85 ến 87) -
Các hằng ẳng thức tập hợp (trang 87,88) -
Biểu diễn các tập hợp trên máy tính (trang 91)( ọc thêm) 4/4
1.5. Tập hợp, phép toán trên tập hợp, ánh xạ (tiếp [1] theo) Ánh xạ (hàm, trang 96) -
Định nghĩa 1, 2, 3, 4 (trang 96 ến 98 -
Định nghĩa 5, 6, 7, 8, 9, 10 và 11 (trang 98 ến
103) - Một số hàm quan trọng (trang 103)(Giới thiệu cho sv tự ọc)
1.6. Khái niệm về thuật toán -
Khái niệm (trang 118 ến 128) -
Giới thiệu ộ phức tạp của thuật toán (trang 143- 151…) Bài tập chương 1 SV tự ọc thêm 5/5
Bài tập chương 1 (tiếp theo) [1]
Chương 2: Phép quy nạp và ệ quy
2.1. Dãy số và cách tính tổng, bản số của tập hợp SV tự ọc thêm -
Định nghĩa 1, 2, 3 (trang 228) -
Các dãy số nguyên ặc biệt (trang 229) - Bảng 1
(trang 231) Phép tính tổng: -
Kí hiệu, dãy số, giới hạn dưới, giới hạn trên - Bảng 2 (trang 234) -
Định nghĩa 4, 5 (trang 235)
2.2. Quy nạp toán học Chứng minh quy nạp lOMoAR cPSD| 47206521 6/6
2.3. Định nghĩa bằng ệ quy [1] SV tự ọc thêm
- Khái niệm ệ quy (trang …)
- Khái niệm ịnh nghĩa ệ quy (trang 260)
- Các tập ược ịnh nghĩa bằng ệ quy (trang 264)
2.4. Thuật toán ệ quy
- Định nghĩa 1 (trang 277) SV tự ọc thêm
- Thuật toán 1 ến 9 (trang 277 ến 281)
2.5. Quan hệ: Định nghĩa và tính chất
- Định nghĩa 1 (trang 469)
- Hàm cũng là một quan hệ (trang 470)
- Các quan hệ trên một tập (trang 471)
- Các tính chất của quan hệ (trang 472 ến 474) 7/7
2.6. Quan hệ tương ương và quan hệ thứ tự bộ [1] phận
Các quan hệ tương ương: -
Định nghĩa 1, 2 (trang 507, 508) -
Các lớp tương ương và các phân hoạch (trang 509 ến 511)
Quan hệ thứ tự bộ phận: -
Định nghĩa 1, 2, 3, 4; ịnh ý 1 (trang 515, 516) - Dàn (522)(ví dụ 24) 8/8 Bài tập chương 2 9/9
Chương 3. Phép ếm [1]
3.1. Khái niệm cơ bản về phép ếm
- Cơ sở của phép ếm (trang 301)
- Những nguyên lý ếm cơ bản: cộng, nhân (trang 302 ến …) -
Nguyên lý bù trừ (trang 308) - Biểu ồ cây (trang 309)
3.2. Nguyên lý chuồng chim -
Mở ầu: nguyên lý 1, 2 (trang 313, 314) -
Một số ứng dụng của nguyên lý Dirichle (trang 316)
10/10 3.3. Hoán vị và Tổ hợp [1]
- Khái niệm hoán vị + ịnh lý 1 (trang 321)
- Khái niệm tổ hợp (trang 322)
- Định lý 2 + hệ quả 1 (trang 323) lOMoAR cPSD| 47206521
11/11 Bài tập Chương 3 [1]
Chương 4. Lý thuyết ồ thị
4.1. Khái niệm cơ bản về ồ thị, cây và chu trình Đồ thị:
- Khái niệm ồ thị (trang 535)
- Các loại ồ thị (trang 535 ến 538)
- Các thuật ngữ cơ bản (trang 543 ến 545)
- Một số ồ thị ơn ặc biệt … (trang 545 ến 550)
Cây: Giới thiệu (trang …) Chu trình (trang 563)
12/12 4.2. Biểu diễn ồ thị và các phép ẳng cấu ồ thị [1]
- Biểu diễn các ồ thị (trang 553) - Ma trận kề (trang 554)
- Ma trận liên thuộc (trang 556)
- Sự ẳng cấu của các ồ thị (trang 556 ến 560)
4.3. Tính liên thông của ồ thị (trang 563 ến 570) 13/13
4.4. Đường i Euler và chu trình Hamilton (trang [1] 573 ến 582)
4.5. Các bài toán ường i ngắn nhất (trang 586 ến 594)
14/14 4.5. Các bài toán ường i ngắn nhất (tiếp theo) [1]
4.6. Duyệt cây (trang 647 ến 656)
15/15 4.6. Duyệt cây (tiếp theo) [1] Bài tập Chương 4
• Đối với học kỳ phụ: Môn học này không dạy ở học kỳ phụ.