Bạn sẽ học được gì
- Phân tích độ phức tạp thời gian bằng ký hiệu Big-O và giải công thức truy hồi bằng Master theorem
- Thiết kế thuật toán tham lam (greedy) và chứng minh tính đúng đắn bằng lập luận trao đổi
- Thiết kế thuật toán quy hoạch động: xác định trạng thái, viết công thức truy hồi, tối ưu bộ nhớ
- Áp dụng chia để trị cho bài toán mới và phân tích độ phức tạp của thuật toán đệ quy
- Chứng minh một bài toán là NP-đầy đủ bằng quy dẫn đa thức từ bài toán đã biết
- Lựa chọn và đánh đổi giữa các kỹ thuật thiết kế thuật toán phù hợp cho một bài toán mới
Nên học trước
Giới thiệu
Thiết kế và phân tích thuật toán đi từ việc "một thuật toán đúng và chạy được" (Cấu trúc dữ liệu & Giải thuật) sang việc thiết kế thuật toán mới cho bài toán chưa từng gặp, rồi chứng minh nó đúng và đủ nhanh. Đây là môn học về tư duy giải quyết vấn đề nhiều hơn là học thuộc thuật toán có sẵn.
Bốn kỹ thuật thiết kế cốt lõi
- Chia để trị: chia bài toán thành các phần nhỏ hơn, giải độc lập rồi gộp lại (merge sort, tìm cặp điểm gần nhất).
- Quy hoạch động: khi các bài toán con chồng lấp nhau, lưu lại kết quả để không tính lại — chìa khóa là tìm đúng "trạng thái".
- Tham lam: chọn lựa chọn tốt nhất tại mỗi bước và chứng minh không cần quay lui vẫn ra nghiệm tối ưu.
- Quy dẫn: biến một bài toán lạ thành bài toán đã biết cách giải — hoặc đã biết là khó.
Đọc vị một bài toán mới
Khi gặp bài toán chưa quen, luôn hỏi: bài toán con có chồng lấp không (→ Quy hoạch động), có thứ tự tham lam nào luôn đúng không (→ Greedy), có chia đôi được không (→ Chia để trị)? Nếu cả ba đều bế tắc, bài toán có thể là NP-khó — thử quy dẫn từ một bài toán NP-đầy đủ đã biết (3-SAT, Vertex Cover) sang nó.
Từ đúng đắn đến hiệu quả
Chứng minh đúng đắn và phân tích độ phức tạp là hai việc tách biệt nhưng luôn đi cùng nhau: thuật toán nhanh mà sai thì vô dụng, đúng mà chậm cũng vậy. Luyện viết chứng minh ngắn gọn — bất biến cho vòng lặp, quy nạp cho đệ quy — giúp code ít lỗi hơn, không chỉ để qua bài kiểm tra lý thuyết.
Giáo trình & sách tham khảo
Xem tất cả trong tab SáchGiáo trình chính
Algorithms
Jeff Erickson · 2019
Vì sao chọn: Giáo trình mở (CC BY), miễn phí trọn bộ với lời giải chi tiết cho hầu hết bài tập. Trình bày đúng bốn kỹ thuật thiết kế của lộ trình này nên dùng làm sách chính; văn phong nhiều phản ví dụ giúp hiểu sâu vì sao một cách tiếp cận sai.
Nên đọc: Chương 1 Recursion, 3 Dynamic Programming, 4 Greedy Algorithms, 5–9 Graph Algorithms, 12 NP-Hardness
Algorithm Design
Jon Kleinberg, Éva Tardos · 2006
Sách giáo khoa kinh điển đúng tên môn học, mỗi kỹ thuật được giới thiệu qua một bài toán ứng dụng thực tế trước khi tổng quát hóa. Bản tiếng Anh, chưa có bản đọc miễn phí hợp pháp nên dùng tham khảo song song với Erickson.
Nên đọc: Chương 4 Greedy algorithms, 5 Divide and conquer, 6 Dynamic programming, 8 NP and computational intractability, 11 Approximation algorithms
Introduction to Algorithms
Thomas H. Cormen, Charles E. Leiserson và 2 tác giả khác · 2022 · Bản thứ 4
Sách tham khảo chuẩn mực của ngành, phân tích rất chặt chẽ kèm phụ lục toán học đầy đủ. Phù hợp để tra cứu sâu hoặc khi cần chứng minh chi tiết hơn Erickson; không miễn phí.
Nên đọc: Phần Chia để trị, Quy hoạch động, Thuật toán tham lam; phần Lý thuyết NP-đầy đủ
Các bước học
Đăng nhập để đánh dấu các bước đã hoàn thành.
Bước 1: Ôn độ phức tạp và mô hình phân tích
khoảng 5 giờÔn ký hiệu Big-O, cách viết và giải công thức truy hồi bằng Master theorem. Bài tập: viết công thức truy hồi và tính độ phức tạp cho 5 đoạn mã đệ quy khác nhau, kiểm chứng lại bằng cách đo thời gian chạy thực tế.
- Đọc: Chương 0 Introduction và Chương 1 Recursion — Algorithms
Bước 2: Chia để trị
khoảng 6 giờHọc cách chia bài toán thành các phần độc lập rồi gộp nghiệm; phân tích độ phức tạp bằng cây đệ quy và Master theorem. Cài đặt merge sort và thuật toán tìm cặp điểm gần nhau nhất trong mặt phẳng bằng chia để trị.
- Đọc: Chương 1 Recursion (phần chia để trị) — Algorithms
- Đọc: Chương 5 Divide and conquer — Algorithm Design
Bước 3: Thuật toán tham lam
khoảng 7 giờHọc lập luận trao đổi để chứng minh tính tối ưu của lựa chọn tham lam. Cài đặt Dijkstra và Kruskal/Prim, sau đó tự viết chứng minh đúng đắn bằng lập luận trao đổi cho một trong hai thuật toán.
- Đọc: Chương 4 Greedy Algorithms và Chương 8 Shortest Paths — Algorithms
- Đọc: Chương 4 Greedy algorithms — Algorithm Design
Bước 4: Quy hoạch động
khoảng 8 giờLuyện quy trình 5 bước của DP: định nghĩa trạng thái, viết công thức truy hồi, xác định thứ tự tính, khởi tạo, truy vết nghiệm. Giải ba bài toán DP kinh điển (knapsack, longest common subsequence, edit distance) rồi tối ưu từ đệ quy nhớ đệm sang bottom-up dùng O(n) bộ nhớ.
- Đọc: Chương 3 Dynamic Programming — Algorithms
- Đọc: Chương 6 Dynamic programming — Algorithm Design
Bước 5: Đồ thị nâng cao, luồng và NP-đầy đủ
khoảng 9 giờHọc max-flow/min-cut và cách nhiều bài toán ghép cặp, phân công quy về bài toán luồng. Sau đó học định nghĩa NP, NP-đầy đủ, quy dẫn đa thức và Định lý Cook-Levin; tự quy dẫn một bài toán quen thuộc (như lập lịch hoặc Sudoku) về 3-SAT hoặc Vertex Cover để chứng minh nó NP-đầy đủ.
- Đọc: Chương 10–11 Maximum Flows và Chương 12 NP-Hardness — Algorithms
- Đọc: Chương 7 Network flow và Chương 8 NP and computational intractability — Algorithm Design
Bước 6: Thuật toán xấp xỉ và heuristic
khoảng 6 giờKhi bài toán là NP-khó, học cách thiết kế thuật toán xấp xỉ có tỉ lệ đảm bảo hoặc heuristic thực dụng. Cài đặt thuật toán xấp xỉ tỉ lệ 2 cho Vertex Cover và so sánh kết quả với một heuristic tham lam trên cùng bộ dữ liệu thực.
- Đọc: Chương 11 Approximation algorithms — Algorithm Design
Khái niệm chính
- Độ phức tạp tiệm cận (Big-O/Θ/Ω)
- Cách đo tốc độ tăng của thời gian chạy khi kích thước đầu vào lớn dần, bỏ qua hằng số; Θ dùng khi chặn trên và chặn dưới khớp nhau.
- Công thức truy hồi & Master theorem
- Nhiều thuật toán đệ quy có thời gian chạy T(n) = aT(n/b) + f(n); Master theorem cho công thức đóng ước lượng T(n) mà không cần giải tay.
- Cấu trúc con tối ưu (Optimal substructure)
- Nghiệm tối ưu của bài toán lớn được xây từ nghiệm tối ưu của các bài toán con — điều kiện cần để dùng quy hoạch động hoặc tham lam.
- Bài toán con chồng lấp (Overlapping subproblems)
- Cùng một bài toán con xuất hiện lặp lại trong cây đệ quy; quy hoạch động lưu kết quả (nhớ đệm hoặc bottom-up) để tránh tính lại.
- Lập luận trao đổi (Exchange argument)
- Kỹ thuật chứng minh thuật toán tham lam tối ưu: chỉ ra mọi nghiệm khác đều có thể 'đổi' dần thành nghiệm tham lam mà không làm giảm chất lượng.
- NP-đầy đủ & quy dẫn đa thức
- Lớp bài toán khó nhất trong NP; chứng minh một bài toán NP-đầy đủ bằng cách quy dẫn trong thời gian đa thức từ một bài toán NP-đầy đủ đã biết.
- Thuật toán xấp xỉ (Approximation algorithm)
- Khi bài toán NP-khó, thuật toán xấp xỉ đánh đổi nghiệm tối ưu lấy tốc độ, kèm cam kết về tỉ lệ sai khác tối đa so với nghiệm tối ưu.
Học xong để làm gì
- Định tuyến mạng và GPS: thuật toán đường đi ngắn nhất tham lam (Dijkstra) chạy trong hệ thống điều hướng thực tế
- Trình biên dịch và trình soạn thảo: quy hoạch động trong so khớp chuỗi, kiểm tra cú pháp, so sánh phiên bản văn bản
- Lập lịch và logistics: bài toán đóng gói, phân công tài nguyên dùng tham lam hoặc xấp xỉ khi quy mô lớn
- Học máy và thống kê: quy hoạch động trong mô hình chuỗi (Viterbi), chia để trị trong xây cây quyết định
- Bảo mật: nhiều hệ mật mã dựa trên giả định các bài toán NP-khó (như phân tích thừa số) không có thuật toán nhanh
Câu hỏi thường gặp
DAA khác gì với môn Cấu trúc dữ liệu & Giải thuật đã học?
Môn trước dạy cách dùng đúng cấu trúc dữ liệu và các thuật toán kinh điển; DAA dạy cách thiết kế thuật toán mới cho bài toán chưa có sẵn lời giải và chứng minh nó đúng, đủ nhanh.
Có bắt buộc phải chứng minh toán học chặt chẽ không?
Nên tập viết chứng minh ngắn gọn cho từng thuật toán tự thiết kế — đây là kỹ năng được rèn luyện nhiều nhất trong môn này và giúp gỡ lỗi thuật toán hiệu quả hơn.
Làm sao biết nên dùng Greedy hay Quy hoạch động?
Thử chứng minh tham lam trước vì thường nhanh và dễ cài đặt; nếu tìm được phản ví dụ khiến lựa chọn tham lam sai, chuyển sang quy hoạch động.
Gặp bài toán không giải nhanh được thì sao?
Thử quy dẫn từ một bài toán NP-đầy đủ đã biết; nếu quy dẫn được, đó là dấu hiệu bài toán khó về lý thuyết và nên chuyển sang thuật toán xấp xỉ hoặc heuristic.





