VNU-HUS MAT3500: Toán rời rạc

Đây là trang web hỗ trợ cho môn “Toán rời rạc (VNU-HUS MAT3500)” tôi tham gia giảng dạy ở Đại học KHTN, ĐHQG Hà Nội trong Học kỳ hè năm học 2023-2024.

Các thông tin cơ bản
Giáo trình, tài liệu tham khảo
Tài liệu từ các năm trước
Nội dung
Lịch sử các thông báo

Thông báo

10/8/2024:
- Đề thi cuối kỳ và gợi ý giải

Xem các thông báo cũ ở đây.

Các thông tin cơ bản

Trường: Đại học KHTN, ĐHQG Hà Nội
Mã học phần: MAT3500
Mã lớp học phần: MAT3500
Số tín chỉ: 4
Thời gian: Học kỳ hè năm học 2023-2024
- Lý thuyết: Thứ 2 + Thứ 4, 14:00 – 17:50 (Tiết 7–10), Phòng 302-T5 (Từ 8/7/2024, chuyển sang phòng 102-T5)
- Bài tập: Thứ 3 + Thứ 6, 14:00 – 17:50 (Tiết 7–10), Phòng 302-T5 (Từ 8/7/2024, chuyển sang phòng 102-T5)
Giảng viên (Lý thuyết + Bài tập): Hoàng Anh Đức (Đại học KHTN, ĐHQG Hà Nội, hoanganhduc[at]hus.edu.vn (thay [at] bằng @))
Nội dung: Cung cấp các kiến thức toán học cơ sở cho ngành công nghệ thông tin bao gồm các cấu trúc toán học rời rạc và các nguyên lí toán học áp dụng cho các cấu trúc này (cơ sở của lô gíc toán học, lí thuyết tập hợp, hàm và quan hệ, lí thuyết số, lí thuyết đếm, lí thuyết đồ thị, phép tính xác suất, đại số Bool và mạch tổ hợp, ôtô mát, ngôn ngữ hình thức và khả năng tính toán)
Trang web hỗ trợ: https://hoanganhduc.github.io/teaching/VNU-HUS/2024/summer/MAT3500/
Google Classroom: 5f2622i
Kiểm tra, đánh giá:
- Phần tự học, tự nghiên cứu, bài tập: 20%
- Thi giữa kỳ: 20%
- Thi cuối kỳ: 60%

Giáo trình, tài liệu tham khảo

Học liệu bắt buộc:
- K. H. Rosen (2012), Discrete Mathematics and Its applications, 7th edition, Mc Graw-Hill, https://highered.mheducation.com/sites/0073383090 [Tài liệu giảng dạy chính]
  - Google Drive: bản tiếng Anh, bản dịch tiếng Việt phiên bản cũ (cần tài khoản với email đuôi @hus.edu.vn)
  - VNU-LIC: bản tiếng Anh 8th edition, bản dịch tiếng Việt phiên bản cũ, Student’s solutions guide (cần tài khoản VNU)
- Tom Jenkyns, Ben Stephenson (2018), Fundamentals of Discrete Math for Computer Science: A Problem-Solving Primer, 2nd edition, Springer-Verlag London, doi:10.1007/978-3-319-70151-6
Học liệu tham khảo thêm:
- Nguyễn Hữu Điển (2019), Toán rời rạc và ứng dụng, NXB Đại học Quốc gia Hà Nội
  - Google Drive
- Vũ Đình Hòa (2010), Toán rời rạc, NXB Đại học Sư Phạm Hà Nội
  - Bài giảng Toán rời rạc của cùng tác giả
- Oscar Levin (2021), Discrete Mathematics: An Open Introduction, 3rd edition, https://discrete.openmathbooks.org/
- Thomas VanDrunen (2013), Discrete Mathematics and Functional Programming, Franklin, Beedle and Associates, https://cs.wheaton.edu/~tvandrun/dmfp/
- Harry Lewis and Rachel Zax (2019), Essential Discrete Mathematics for Computer Science, Princeton University Press
- Mordechai Ben-Ari (2012), Mathematical Logic for Computer Science, 3rd edition, Springer, London, doi:10.1007/978-1-4471-4129-7
Một số tài liệu khác
- Math Study Tips, by Gary MacGillivray
- Lời khuyên cho các sinh viên trong lớp Math 412, by Douglas B. West (Bản dịch tiếng Việt thực hiện bởi Hoàng Anh Đức)
  - 2024-05-27: Xem bản dịch khác của Nguyễn Trọng Đức, lớp K68A5 (KHDL), Đại học Khoa học Tự nhiên, ĐHQG Hà Nội.

Tài liệu từ các năm trước

Học kỳ 2, năm học 2023-2024: MAT3500 1, MAT3500 2
Học kỳ 2, năm học 2022-2023: MAT3500 2, MAT3500 3

Nội dung

Bài giảng và bài tập

Chú ý: Một phần các bài giảng dựa trên các slides của Jan Stelovsky cho môn ICS141: Discrete Mathematics for Computer Science I ở Đại học Hawaii mùa thu năm 2011.

Chủ đề	Tài liệu	Ghi chú
Giới thiệu	slides
Lôgic và Chứng minh	slides, bài tập	Chương 1, 1.1–1.5, 1.7 (Rosen)
Các cấu trúc cơ bản: Tập hợp, Hàm, Dãy, Tổng	slides, bài tập	Chương 2, 2.1–2.5 (Rosen)
Quy nạp và Đệ quy	slides, bài tập	Chương 5, 5.1–5.3 (Rosen)
Thuật toán I: Giới thiệu, một số thuật toán tìm kiếm và sắp xếp, độ tăng của hàm	slides, bài tập	Chương 3, 3.1–3.2 (Rosen)
Thuật toán II: Độ phức tạp tính toán, thuật toán tham lam, thuật toán đệ quy	slides, bài tập	Chương 3, 3.1, 3.3, Chương 5, 5.4, Chương 8, 8.1–8.4 (Rosen)
Lý thuyết số cơ bản	slides, bài tập	Chương 4, 4.1–4.4 (Rosen)
Các phương pháp đếm	slides, bài tập	Chương 6, 6.1–6.5 (Rosen)
Lý thuyết đồ thị I: Giới thiệu, Biểu diễn đồ thị và sự đẳng cấu, Tính liên thông	slides, bài tập	Chương 10, 10.1–10.4 (Rosen)
Lý thuyết đồ thị II: Đường đi ngắn nhất, Đồ thị phẳng, Tô màu đồ thị	slides, bài tập	Chương 10, 10.5–10.8 (Rosen)
Lý thuyết đồ thị III: Cây	slides, bài tập	Chương 11, 11.1–11.5 (Rosen)
Đại số Boole	slides, bài tập	Chương 12, 12.1–12.4 (Rosen)

Kiểm tra, đánh giá

Kiểm tra giữa kỳ: nội dung ôn tập, đề bài + gợi ý giải, nhận xét, đề dự phòng + gợi ý giải
Kiểm tra cuối kỳ: nội dung ôn tập, đề số 1 và gợi ý giải, đề số 2 và gợi ý giải (Phòng đào tạo chọn một trong hai đề làm đề thi chính thức)

Lời giải các bài tập

Thời gian	Bài tập	Lời giải	Tác giả
16/03/2024	Bài 8, danh sách bài tập “Quy nạp và đệ quy”	PDF	Hoàng Anh Đức (GV)

Lịch sử các thông báo

26/7/2024:
- Cập nhật nội dung môn học (xem ở đây)
  - Lý thuyết đồ thị I, II, III
  - Đại số Boole
  - Nội dung ôn tập cho kiểm tra cuối kỳ
19/7/2024:
- Đề và gợi ý giải bài thi giữa kỳ
15/7/2024:
- Cập nhật nội dung môn học (xem ở đây)
  - Lý thuyết số cơ bản
  - Các phương pháp đếm
6/7/2024:
- Cập nhật nội dung môn học (xem ở đây)
  - Quy nạp và Đệ quy
  - Thuật toán I: Giới thiệu, một số thuật toán tìm kiếm và sắp xếp, độ tăng của hàm
  - Thuật toán II: Độ phức tạp tính toán, thuật toán tham lam, thuật toán đệ quy
  - Nội dung ôn tập cho kiểm tra giữa kỳ
30/6/2024:
- Cập nhật nội dung môn học (xem ở đây)
  - Giới thiệu
  - Lôgic và Chứng minh
  - Các cấu trúc cơ bản
23/6/2024:
- Khởi tạo trang web