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ỳ 2 năm học 2024-2025.

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 (KHDL)
  • Số tín chỉ: 4
  • Thời gian: Học kỳ 1 năm học 2024-2025
    • Lý thuyết: Thứ 4, 07:00 - 09:50 (Tiết 1-3), Phòng 202-T5
    • Bài tập: Thứ 5, 16:00 - 17:50 (Tiết 9-10), Phòng 208-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ố Boole 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/2025/spring/MAT3500/
  • Canvas: 6TED87
  • 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

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

Nội dung

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

Chủ đề Tài liệu Ghi chú
Giới thiệu slides  
Lôgic và Chứng minh slides 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 Chương 2, 2.1–2.5 (Rosen)
Quy nạp và Đệ quy slides Chương 5, 5.1–5.3, Chương 8, 8.1–8.4 (Rosen)
Thuật toán I: Mô tả, chứng minh, đánh giá thuật toán; Tìm kiếm và sắp xếp slides Chương 3, 3.1–3.3, Chương 5, 5.5 (Rosen)
Thuật toán II: Thuật toán đệ quy, thuật toán tham lam slides Chương 5, 5.4 (Rosen)
Lý thuyết số cơ bản slides Chương 4, 4.1–4.4 (Rosen)
Các phương pháp đếm slides 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 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 Chương 10, 10.5–10.8 (Rosen)
Lý thuyết đồ thị III: Cây slides Chương 11, 11.1–11.5 (Rosen)
Đại số Boole slides Chương 12, 12.1–12.4 (Rosen)
Tổng hợp slides, bài tập  

Kiểm tra, đánh giá

  • Kiểm tra giữa kỳ: thông tin cần biết, đề + đáp án
    • Với các mã đề có câu “Cho quan hệ $f \subseteq A \times B$ định nghĩa bởi $f = \{(n, \sqrt{n}) \mid n \in A \land \sqrt{n} \in B \}$ trong đó $A, B$ là các tập con của tập số thực $\mathbb{R}$.” thì đổi thành “Cho quan hệ $f \subseteq A \times B$ định nghĩa bởi $f = \{(n, \sqrt{\vert n\vert}) \mid n \in A \land \sqrt{\vert n\vert} \in B \}$ trong đó $A, B$ là các tập con của tập số thực $\mathbb{R}$.”
    • Với các mã đề có câu tính giá trị của biểu thức $\displaystyle\sum_{i=1}^{n} i \cdot 2^i$, có hai đáp án giống nhau là $(n-1)\cdot 2^{n+1} + 2$. Nếu đáp án này đúng thì chọn cả hai đáp án giống nhau trong phiếu trả lời trắc nghiệm.
    • Với các mã đề có câu tính giá trị biểu thức $\displaystyle\sum_{i=1}^{10}\left(\prod_{j=1}^{i} \frac{j}{j+1}\right)$ thì không có đáp án nào trong số các đáp án đưa ra là đúng. (Bỏ qua đáp án sai trong đề trên.)
    • Với các mã đề có câu tính giá trị biểu thức $\displaystyle\sum_{n=0}^{100}\prod_{k = n}^{2}k$ thì kết quả là $102$ nếu quy ước là $\displaystyle\prod_{k = n}^{2}k = 1$ với mọi $n > 2$ (hoặc tổng quát hơn là $\displaystyle\prod_{k = n}^{m}k = 1$ với mọi $n > m$). (Quy ước này không được đề cập trong bài giảng. Do đó, có thể coi như là không có đáp án nào là đúng trong số các đáp án đưa ra trong đề trên.)
    • Lỗi trong quá trình sinh ngẫu nhiên đề thi dẫn đến có các mã đề giống nhau nhưng nội dung khác nhau.
  • Kiểm tra cuối kỳ: thông tin cần biết, đề + đáp án

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

  • 18/05/2025:
    • Cập nhật nội dung môn học
      • Chỉnh sửa một số nội dung trong “Lý thuyết đồ thị III” và “Đại số Boole”
      • Tổng hợp các bài giảng và bài tập
  • 13/05/2025:
    • Cập nhật nội dung môn học
      • Thông tin về kiểm tra cuối kỳ
  • 18/04/2025:
    • Cập nhật nội dung môn học
      • Chỉnh sửa một số nội dung trong “Lý thuyết đồ thị I”
  • 12/04/2025:
    • Cập nhật nội dung môn học
      • Thêm một số bài tập về “Các phương pháp đếm”
      • Lý thuyết đồ thị I, II, III
      • Đại số Boole
  • 01/04/2025:
    • Cập nhật nội dung môn học
  • 29/03/2025:
    • Cập nhật nội dung môn học
      • Đề và đáp án bài kiểm tra giữa kỳ (trắc nghiệm)
  • 21/03/2025:
    • Cập nhật nội dung môn học
      • Lý thuyết số cơ bản
  • 08/03/2025:
    • Cập nhật nội dung môn học
      • Quy nạp và Đệ quy (Chỉnh sửa một số nội dung nhỏ)
      • Thuật toán I, II
      • Thông tin về kiểm tra giữa kỳ
  • 25/02/2025:
    • Cập nhật nội dung môn học
      • Quy nạp và Đệ quy
  • 16/02/2025:
    • Cập nhật nội dung môn học
      • Các cấu trúc cơ bản: Tập hợp, Hàm, Dãy, Tổng
  • 04/02/2025:
    • Khởi tạo trang web.
    • Sinh viên đăng ký lớp MAT3500 điền thông tin vào form https://forms.office.com/r/AvRmSZT9vS trước 23:59 ngày 27/02/2025 để được mời vào lớp trên Canvas.
    • Cập nhật nội dung môn học
      • Giới thiệu
      • Lôgic và Chứng minh