Bạn sẽ học được gì
- Viết và kiểm tra chứng minh toán học bằng phương pháp trực tiếp, phản chứng và quy nạp
- Dùng ngôn ngữ tập hợp, quan hệ và hàm để mô tả chính xác các cấu trúc rời rạc
- Áp dụng lý thuyết đồ thị cơ bản để mô hình hóa và giải các bài toán quen thuộc trong CS
- Đếm bằng các kỹ thuật tổ hợp (hoán vị, chỉnh hợp, nguyên lý chuồng bồ câu, nhị thức) và ước lượng xác suất rời rạc
- Giải hệ thức truy hồi để phân tích độ phức tạp của các thuật toán đệ quy
Nên học trước
Giới thiệu
Toán học cho khoa học máy tính (toán rời rạc) khác Giải tích ở chỗ nó nghiên cứu các đối tượng rời rạc, đếm được — số nguyên, tập hợp, đồ thị, chuỗi bit — thay vì các đại lượng biến thiên liên tục. Đây là toán học đứng sau gần như mọi thuật toán, cấu trúc dữ liệu và chứng minh về độ đúng đắn của chương trình.
Chứng minh: từ niềm tin đến chắc chắn
Kỹ năng cốt lõi của môn này là viết chứng minh chặt chẽ. Quy nạp toán học đặc biệt quan trọng với dân CS vì nó phản chiếu chính cấu trúc đệ quy của thuật toán: chứng minh đúng cho trường hợp cơ sở, rồi chứng minh nếu đúng cho n thì đúng cho n+1 — giống hệt cách một hàm đệ quy tự gọi lại với đầu vào nhỏ hơn.
Cấu trúc rời rạc là ngôn ngữ mô hình hóa
Tập hợp, quan hệ, hàm và đặc biệt là đồ thị (graph) là ngôn ngữ chung để mô tả chính xác gần như mọi bài toán CS: mạng máy tính là đồ thị, quan hệ cơ sở dữ liệu là tập hợp bộ giá trị, trạng thái chương trình là một hàm. Học cách "dịch" một bài toán thực tế sang ngôn ngữ này là kỹ năng dùng suốt sự nghiệp.
Đếm, xác suất và truy hồi
Đếm chính xác số cách một việc có thể xảy ra (tổ hợp) là nền tảng của xác suất rời rạc và phân tích thuật toán ngẫu nhiên. Hệ thức truy hồi — phương trình mô tả một đại lượng qua chính nó ở bước trước — là công cụ chuẩn để tính thời gian chạy của thuật toán đệ quy như chia để trị (ví dụ Merge Sort chạy trong O(n log n) suy ra trực tiếp từ giải một hệ thức truy hồi).
Giáo trình & sách tham khảo
Xem tất cả trong tab SáchGiáo trình chính
Mathematics for Computer Science
Eric Lehman, F. Thomson Leighton, Albert R. Meyer · 2018
Vì sao chọn: Giáo trình toán rời rạc của MIT (môn 6.042J/6.1200), miễn phí (CC BY-SA), luôn gắn lý thuyết với ứng dụng thuật toán cụ thể. Cấu trúc theo 5 phần khớp gần trọn lộ trình; đây là sách chính để đọc theo thứ tự bước.
Nên đọc: Part I–III, V
Discrete Mathematics: An Open Introduction
Oscar Levin · 2025 · Bản thứ 4
Giáo trình toán rời rạc mở khác (CC BY-NC-SA), trình bày chậm rãi hơn với nhiều bài tập có lời giải mẫu. Dùng làm nguồn thứ hai khi một khái niệm trong sách MIT chưa rõ, đặc biệt phần logic và đồ thị ở bước 1–3.
Nên đọc: Phần Logic; phần Lý thuyết đồ thị; phần Phép đếm
Các bước học
Đăng nhập để đánh dấu các bước đã hoàn thành.
Bước 1: Logic và các phương pháp chứng minh
khoảng 7 giờMệnh đề, lượng từ, chứng minh trực tiếp, phản chứng, phản ví dụ. Tự viết chứng minh trực tiếp và chứng minh phản chứng cho hai mệnh đề số học đơn giản (ví dụ: tổng hai số chẵn là số chẵn; căn bậc hai của 2 là số vô tỉ).
- Đọc: Part I: Proofs — Mathematics for Computer Science
Bước 2: Quy nạp toán học
khoảng 6 giờQuy nạp yếu, quy nạp mạnh, quy nạp cấu trúc. Chứng minh bằng quy nạp công thức tổng 1+2+...+n, rồi chứng minh một loop invariant đơn giản cho một thuật toán sắp xếp chèn (insertion sort) viết bằng giả mã.
- Đọc: Part I: Proofs (phần quy nạp) — Mathematics for Computer Science
Bước 3: Tập hợp, quan hệ, hàm và đồ thị
khoảng 9 giờTập hợp, quan hệ hai ngôi, tính chất (phản xạ, đối xứng, bắc cầu), hàm đơn ánh/toàn ánh; nhập môn đồ thị: đỉnh, cạnh, đường đi, tính liên thông. Mô hình hóa một mạng xã hội nhỏ (5–6 người) thành đồ thị trên giấy và trả lời các câu hỏi về đường đi ngắn nhất, thành phần liên thông bằng tay.
- Đọc: Part II: Structures — Mathematics for Computer Science
Bước 4: Phép đếm và xác suất rời rạc
khoảng 8 giờQuy tắc đếm, hoán vị, tổ hợp, nguyên lý chuồng bồ câu, nhị thức Newton; xác suất rời rạc cơ bản. Giải 5 bài toán đếm cổ điển (ví dụ: số cách chia bài, số cách sắp xếp có ràng buộc) và một bài toán chứng minh bằng nguyên lý chuồng bồ câu.
- Đọc: Part III: Counting — Mathematics for Computer Science
Bước 5: Hệ thức truy hồi và phân tích thuật toán
khoảng 8 giờThiết lập và giải hệ thức truy hồi (thế lặp, cây truy hồi, Master Theorem ở mức trực giác). Thiết lập hệ thức truy hồi cho thời gian chạy của Merge Sort và giải nó để suy ra O(n log n), so với việc chỉ đo thời gian chạy thực nghiệm bằng code.
- Đọc: Part V: Recurrences — Mathematics for Computer Science
Khái niệm chính
- Chứng minh quy nạp (induction)
- Kỹ thuật chứng minh một mệnh đề đúng với mọi số tự nhiên n bằng cách chứng minh nó đúng với trường hợp cơ sở, rồi chứng minh nếu đúng với n thì đúng với n+1.
- Tập hợp, quan hệ, hàm
- Tập hợp là một bộ sưu tập các phần tử phân biệt; quan hệ mô tả sự liên kết giữa các phần tử của (các) tập hợp; hàm là quan hệ đặc biệt gán mỗi đầu vào với đúng một đầu ra.
- Đồ thị (graph)
- Cấu trúc gồm các đỉnh (vertex) và cạnh (edge) nối chúng, dùng để mô hình hóa mạng, quan hệ, bản đồ; nền tảng của rất nhiều thuật toán (tìm đường, luồng, tô màu).
- Nguyên lý đếm cơ bản và tổ hợp
- Quy tắc nhân, hoán vị (permutation), chỉnh hợp/tổ hợp (combination) và hệ số nhị thức dùng để đếm chính xác số cách sắp xếp hoặc chọn phần tử.
- Nguyên lý chuồng bồ câu (pigeonhole)
- Nếu nhét n+1 vật vào n hộp, ít nhất một hộp chứa từ 2 vật trở lên; nguyên lý đơn giản nhưng dùng để chứng minh nhiều kết quả tồn tại bất ngờ trong CS.
- Xác suất rời rạc
- Xác suất định nghĩa trên không gian mẫu đếm được (hữu hạn hoặc vô hạn đếm được); dùng đếm tổ hợp để tính xác suất các biến cố — nền tảng phân tích thuật toán ngẫu nhiên.
- Hệ thức truy hồi (recurrence relation)
- Phương trình định nghĩa một dãy số qua các số hạng trước đó (ví dụ T(n) = 2T(n/2) + n); giải hệ thức truy hồi cho biết thời gian chạy của thuật toán đệ quy.
Học xong để làm gì
- Chứng minh độ đúng đắn của thuật toán (loop invariant thường dùng quy nạp)
- Phân tích độ phức tạp thuật toán đệ quy bằng cách giải hệ thức truy hồi (ví dụ Master Theorem)
- Mô hình hóa mạng máy tính, mạng xã hội, bản đồ giao thông bằng lý thuyết đồ thị
- Thiết kế hệ mật mã và mã sửa lỗi dựa trên số học modular và tổ hợp
- Phân tích xác suất trong hashing, thuật toán ngẫu nhiên, học máy xác suất
Câu hỏi thường gặp
Môn này khác gì Giải tích?
Giải tích nghiên cứu đại lượng biến thiên liên tục (dùng giới hạn, đạo hàm, tích phân); môn này nghiên cứu đối tượng rời rạc, đếm được (số nguyên, tập hợp, đồ thị) và dùng logic, chứng minh làm công cụ chính thay vì tính toán số.
Cần biết lập trình trước khi học môn này không?
Không bắt buộc, nhưng có ích — nhiều khái niệm (đệ quy, hệ thức truy hồi, độ phức tạp) sẽ dễ cảm nhận hơn nếu bạn đã viết qua vài chương trình đệ quy, đó là lý do lộ trình gợi ý học sau môn Lập trình.
Phần khó nhất với người mới thường là gì?
Viết chứng minh chặt chẽ, đặc biệt là quy nạp — khác hẳn việc giải bài toán tính toán. Luyện bằng cách đọc nhiều chứng minh mẫu trước khi tự viết, và luôn tự hỏi "bước này vì sao đúng?" thay vì chỉ chép công thức.
Mất bao lâu để hoàn thành lộ trình?
Khoảng 46 giờ, tương đương 7–8 tuần nếu học 6 giờ mỗi tuần — đây là môn nặng về tư duy và luyện chứng minh nên cần thời gian làm bài tập nhiều hơn đọc lý thuyết.