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


Đây là trang web hỗ trợ cho môn “Toán rời rạc (VNU-HUS MAT3500 3)” 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 2022-2023.

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 3 (KHMT&TT)
  • Số tín chỉ: 4
  • Thời gian: Học kỳ 2 năm học 2022-2023
    • Lý thuyết:
      • Thứ 2, 07:00 – 08:50, Phòng 201-T4
      • Thứ 4, 09:00 – 09:50, Phòng 202-T4
    • Bài tập: Thứ 4, 10:00 – 11:50, Phòng 202-T4
  • 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/2023/MAT3500-3/
  • Google Classroom: cp3tejs
  • 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

Nội dung

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

Chủ đề Tài liệu Ghi chú
Giới thiệu slides, handout  
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 I: Tập hợp, Hàm slides, bài tập Chương 2, 2.1–2.3, 2.5 (Rosen)
Các cấu trúc cơ bản II: Dãy, Tổng slides, bài tập Chương 2, 2.4 (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 I slides, bài tập Chương 4, 4.1–4.3 (Rosen)
Lý thuyết số cơ bản II slides Chương 4, 4.4 (Rosen)

Kiểm tra, đánh giá


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

  • 22/03/2023:
    • Sửa lỗi sai trong Bài tập Thuật toán 1, Bài 11: $O(g)$ => $\Theta(g)$ và “… các hằng số $C_1$, $C_2$, $k$ …” => “… các hằng số dương $C_1$, $C_2$, $k$ …”
  • 20/03/2023:
    • Cập nhật nội dung môn học (xem ở đây)
      • Lý thuyết số cơ bản I
      • Bài tập Thuật toán II
  • 16/03/2023:
    • Sửa lỗi sai trong định nghĩa $\Omega$-lớn ở slides “Thuật toán I” và “Thuật toán II”: hằng số $C$ phải dương ($f$ là $\Omega(g)$ nếu tồn tại các hằng số $C > 0$ và $k$ sao cho $\vert f(x)\vert \geq C\vert g(x)\vert$ với mọi $x > k$).
  • 14/03/2023:
    • Cập nhật nội dung môn học (xem ở đây)
      • Nội dung ôn tập cho kiểm tra giữa kỳ
  • 12/03/2023:
    • Cập nhật nội dung môn học (xem ở đây)
      • Thuật toán II: Độ phức tạp tính toán, thuật toán tham lam, thuật toán đệ quy
  • 06/03/2023:
    • 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
  • 01/03/2023:
    • Sửa lỗi trong slides “Quy nạp và Đệ quy”
      • Trang 27, $0 \leq i \leq k$ => $1 \leq i \leq k$
      • Trang 28, $3 \leq i \leq k$ => $4 \leq i \leq k$
  • 27/02/2023:
    • Sửa lỗi trong slides “Quy nạp và Đệ quy”
      • Trang 10, $\displaystyle\frac{1(1+2)}{2}$ => $\displaystyle\frac{1(1+1)}{2}$
      • Trang 16, $\displaystyle \bigwedge_{j=1}^kP(j)$ => $\displaystyle \bigwedge_{j=b}^kP(j)$
      • Trang 20, $a, b \in \mathbb{Z}^+$ => $a, b \in \mathbb{Z}$
      • Trang 26, $f(n-2)$ => $f_{n-2}$
  • 26/02/2023:
    • Thêm tài liệu tham khảo
      • Ebook “Toán rời rạc và ứng dụng” (Nguyễn Hữu Điển)
      • Math Study Tips, by Gary MacGillivray
    • Cập nhật nội dung môn học (xem ở đây)
      • Quy nạp và Đệ quy
  • 21/02/2023:
    • Nhận xét về bài Kiểm tra thường xuyên 1 (xem ở đây)
  • 20/02/2023:
    • Sửa lỗi trong slides “Các cấu trúc cơ bản II” (trang 9) $\displaystyle\sum_{j=m}^na_i$ => $\displaystyle\sum_{j=m}^na_j$
    • Kiểm tra thường xuyên 1 (xem đề bài và gợi ý giải ở đây)
  • 12/02/2023:
    • 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 và Tổng
  • 06/02/2023:
    • Sửa lỗi trong slides và handout “Giới thiệu”: 29/03/2022 => 29/03/2023
  • 05/02/2023:
    • Cập nhật nội dung môn học (xem ở đây)
      • Lôgic và Chứng minh
  • 02/02/2023:
    • 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/zR7mjEbox8mrYX866.
    • Cập nhật nội dung môn học (xem ở đây)
      • Giới thiệu