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

Đây là trang web hỗ trợ cho môn “Toán rời rạc (VNU-HUS MAT3500 2)” 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 2 (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, 09:00 – 11:50, Phòng 204-T4
    • Bài tập: Thứ 4, 07:00 – 08:50, Phòng 204-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-2/
  • Google Classroom: a3rzf6o
  • 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, Phép kéo theo trong lôgic 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, lời giải Bài 6 trong slides Chương 4, 4.1–4.3 (Rosen)
Lý thuyết số cơ bản II slides, bài tập Chương 4, 4.4 (Rosen)
Các phương pháp đếm I slides, bài tập Chương 6, 6.1–6.2 (Rosen)
Các phương pháp đếm II slides, bài tập Chương 6, 6.3–6.5 (Rosen)
Lý thuyết đồ thị I slides, bài tập Chương 10, 10.1–10.3 (Rosen)
Lý thuyết đồ thị II slides, bài tập Chương 10, 10.4–10.5 (Rosen)
Lý thuyết đồ thị III slides, bài tập Chương 10, 10.6–10.8, Chương 11, 11.1 (Rosen)
Lý thuyết đồ thị IV slides, bài tập Chương 11, 11.4–11.5 (Rosen)
Đại số Boole slides, bài tập Chương 12, 12.1–12.4 (Rosen)

Kiểm tra, đánh giá

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

Thời gian Bài tập Lời giải Tác giả
21/03/2023 slides “Thuật toán II” PDF Phạm Hữu Vang
02/04/2023 Bài 6, slides “Lý thuyết số cơ bản I” PDF Hoàng Anh Đức (GV)

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

  • 21/05/2023:
    • Cập nhật nội dung môn học (xem ở đây)
      • Đại số Boole (lý thuyết + bài tập)
  • 18/05/2023:
    • Cập nhật nội dung môn học (xem ở đây)
      • Bài tập Lý thuyết đồ thị IV
      • Chú ý Về phép kéo theo trong lôgic
      • Nội dung ôn tập cho kiểm tra cuối kỳ
  • 14/05/2023:
    • Cập nhật nội dung môn học (xem ở đây)
      • Lý thuyết đồ thị IV
      • Bài tập Lý thuyết đồ thị III
  • 10/05/2023:
    • Đề bài và lời giải Bài kiểm tra thường xuyên 3
  • 07/05/2023:
    • Cập nhật nội dung môn học (xem ở đây)
      • Lý thuyết đồ thị III
  • 25/04/2023:
    • Cập nhật nội dung môn học (xem ở đây)
      • Sửa một số lỗi trong slides “Lý thuyết đồ thị II”
      • Bài tập Lý thuyết đồ thị I + II
  • 23/04/2023:
    • Cập nhật nội dung môn học (xem ở đây)
      • Lý thuyết đồ thị II
      • Bài tập Các phương pháp đếm II
  • 16/04/2023:
    • Cập nhật nội dung môn học (xem ở đây)
      • Lý thuyết đồ thị I
  • 13/04/2023:
    • Đề bài, lời giải, và nhận xét về Bài kiểm tra thường xuyên 2
    • Sửa lỗi sai trong slides “Các phương pháp đếm II”
      • Trang 25: “Có bao nhiêu cách để $6$ quả bóng có các màu sắc khác nhau vào một túi, trong đó một quả bóng chỉ có thể có màu đỏ (R), xanh lá cây (G), hoặc xanh da trời (B)?” => “Có bao nhiêu cách để $6$ quả bóng vào một túi, biết rằng mỗi quả bóng chỉ có thể có màu đỏ (R), xanh lá cây (G), hoặc xanh da trời (B)?”
      • Trang 28: “Nếu coi tất cả $n$ phần tử đều giống nhau” => “Nếu coi tất cả $n$ phần tử đều khác nhau”
  • 09/04/2023:
    • Cập nhật nội dung môn học (xem ở đây)
      • Bài tập Các phương pháp đếm I
      • Các phương pháp đếm II
  • 05/04/2023:
    • Sửa lỗi sai trong slides “Các phương pháp đếm I”
      • Trang 12, $2^7 + 2^8 - 2^5$ => $2^7 + 2^6 - 2^5$
      • Trang 18, $\frac{5!}{2} = 30$ => $5!/2 = 60$
  • 04/04/2023:
    • Cập nhật nội dung môn học (xem ở đây)
      • Bài tập Lý thuyết số cơ bản II
  • 02/04/2023:
    • Cập nhật nội dung môn học (xem ở đây)
      • Thêm chứng minh tính đúng đắn của quá trình giải mã trong thuật toán RSA ở slides “Lý thuyết số cơ bản II”
      • Lời giải bài tập 6 trong slides “Lý thuyết số cơ bản I”
      • Các phương pháp đếm I
      • Lời khuyên cho các sinh viên trong lớp Math 412 (Douglas B. West)
  • 31/03/2023:
    • Nhận xét về bài Kiểm tra giữa kỳ (xem ở đây)
  • 29/03/2023:
    • Thi giữa kỳ (xem đề bài và gợi ý giải ở đây)
  • 28/03/2023:
    • Cập nhật các hình minh họa cách sử dụng cây đệ quy ở slides “Thuật toán II” (trang 41-42)
  • 27/03/2023:
    • Cập nhật nội dung môn học (xem ở đây)
      • Lý thuyết số cơ bản II
      • Bài tập Lý thuyết số cơ bản I
      • Sửa lỗi sai trong slides “Lý thuyết số cơ bản I”
        • Trang 11: Hệ cơ số $8$ sử dụng các chữ số $0, 1, 2, 3, 4, 5, 6, 7$
        • Trang 25: $n_i = 1$ => $a_i = 1$
  • 22/03/2023:
    • Sửa lỗi sai trong Bài tập Thuật toán I, 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$ …”
  • 21/03/2023:
    • Cập nhật nội dung môn học (xem ở đây)
      • Lời giải các bài tập trong slides “Thuật toán II” của bạn Phạm Hữu Vang
  • 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)
    • 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”: 27/03/2022 => 27/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/KqSgw1kzC8rSVNL77.
    • Cập nhật nội dung môn học (xem ở đây)
      • Giới thiệu