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 2023-2024.

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 1 (KHDL)
  • Số tín chỉ: 4
  • Thời gian: Học kỳ 2 năm học 2023-2024
    • Lý thuyết: Thứ 4, 07:00 – 08:50 (Tiết 1–3), Phòng 203-T5
    • Bài tập: Thứ 5, 16:00 – 17:50 (Tiết 9–10), Phòng 206-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/MAT3500-1/
  • Google Classroom: 7gnoxt2
  • Kiểm tra, đánh giá:
    • Phần tự học, tự nghiên cứu, bài tập: 10%
    • Thi giữa kỳ: 20%
    • Thi cuối kỳ: 70%

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, 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)
Tổng hợp slides, bài tập  

Kiểm tra, đánh giá

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 “Quy nạp và đệ quy” PDF Hoàng Anh Đức (GV)

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

  • 24/5/2024:
    • Cập nhật nội dung môn học (xem ở đây)
      • Tổng hợp các bài giảng + bài tập
  • 15/5/2024:
    • Cập nhật nội dung môn học (xem ở đây)
      • Lý thuyết + bài tập Đại số Boole
      • Nội dung ôn tập cho kiểm tra cuối kỳ
  • 14/5/2024:
    • Cập nhật nội dung môn học (xem ở đây)
      • Lý thuyết + bài tập Lý thuyết đồ thị II
    • Lịch học trong tuần 20/5 - 25/5 (Nếu như bị trùng với giờ học của các lớp khác ở phòng tương ứng thì sẽ đổi sang phòng trống gần đó.)
      • Thứ 4, 7:00 - 12:00 ở 203-T5
      • Thứ 5: 13:00 - 18:00 ở 206-T5
  • 10/5/2024:
    • Đề bài và gợi ý giải Bài kiểm tra thường xuyên 3
    • Nhận xét Bài kiểm tra thường xuyên 3
  • 9/5/2024:
    • Cập nhật nội dung môn học (xem ở đây)
      • Chỉnh sửa một số nội dung trong slides “Lý thuyết đồ thị II”
  • 1/5/2024:
    • Cập nhật nội dung môn học (xem ở đây)
      • Lý thuyết + bài tập Lý thuyết đồ thị II
  • 19/4/2024:
    • Nhận xét Bài kiểm tra thường xuyên 2
  • 18/4/2024:
    • Đề bài và gợi ý giải Bài kiểm tra thường xuyên 2
  • 16/4/2024:
    • Cập nhật nội dung môn học (xem ở đây)
      • Chỉnh sửa một số nội dung trong slides “Các phương pháp đếm”
      • Lý thuyết + bài tập Lý thuyết đồ thị I
  • 9/4/2024:
    • Cập nhật nội dung môn học (xem ở đây)
      • Lý thuyết + bài tập Các phương pháp đếm
  • 2/4/2024:
    • Nhận xét Bài kiểm tra giữa kỳ
    • Cập nhật nội dung môn học (xem ở đây)
      • Chỉnh sửa một số nội dung trong slides “Lý thuyết số cơ bản”
  • 31/3/2024:
    • Đề bài và gợi ý giải Bài kiểm tra giữa kỳ
  • 23/3/2024:
    • Cập nhật nội dung môn học (xem ở đây)
      • Lý thuyết + bài tập Lý thuyết số cơ bản
      • Chỉnh sửa một số nội dung trong slides “Thuật toán II”
  • 16/3/2024:
    • Cập nhật nội dung môn học (xem ở đây)
      • Lý thuyết + bài tập 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ỳ
      • Gợi ý giải Bài 8 trong danh sách bài tập quy nạp và đệ quy
  • 5/3/2024:
    • Cập nhật nội dung môn học (xem ở đây)
      • 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
  • 4/3/2024:
    • Nhận xét Bài kiểm tra thường xuyên 1
  • 22/2/2024:
    • Đề bài và gợi ý giải Bài kiểm tra thường xuyên 1
  • 21/2/2024:
    • Chỉnh sửa slides bài giảng “Quy nạp và Đệ quy”
      • Trang 7, 16, 17: $n \in \mathbb{Z}^+$ => $n \in \mathbb{Z}$
    • Chỉnh sửa slides bài giảng “Các cấu trúc cơ bản”
      • Trang 53: $\sum_{j=0}^{\infty} 2^i$ => $\sum_{j=0}^{\infty} 2^j$
  • 20/2/2024:
    • Cập nhật nội dung môn học (xem ở đây)
      • Quy nạp và Đệ quy
  • 6/2/2024:
    • Chỉnh sửa slides bài giảng “Lôgic và Chứng minh”
      • Thêm phần Phụ lục: Các quy tắc suy luận
  • 31/1/2024:
    • Chỉnh sửa slides bài giảng “Lôgic và Chứng minh”
      • Chuyển trang 50 (cũ) lên sau trang 45 (cũ)
      • Đánh số các tương đương lôgic liên quan đến phép kéo theo và tương đương
      • Sửa lại phát biểu của Bài tập 14 (trang 28)
      • Đánh số các dòng cho các chứng minh trình bày trong phần “Chứng minh”
    • Chỉnh sửa slides bài giảng “Các cấu trúc cơ bản”
      • Trang 9, Bài tập 5: thêm gợi ý
      • Trang 27, Bài tập 11, phần 3: $\mathcal{B}(\neg A_1)$ và $\overline{\mathcal{B}(A_1)}$ => $\mathcal{B}(\overline{A_1})$ và $\neg \mathcal{B}(A_1)$
  • 30/1/2024:
    • Cập nhật nội dung môn học (xem ở đây)
      • Các cấu trúc cơ bản: Tập hợp, Hàm, Dãy, Tổng
  • 20/1/2024:
    • Khởi tạo trang web
    • [Chú ý] Các bạn đăng ký học môn này điền các thông tin cần thiết vào Google Form https://forms.gle/MDyS9xvaD4QuNCip9
    • Cập nhật nội dung môn học (xem ở đây)
      • Giới thiệu
      • Lôgic và Chứng minh