1.2 Kiến thức về Thuật toán

Dưới đây là những kiến thức liên quan đến thuật toán (Algorithms) do tác giả tổng hợp.
Mục tiêu là liệt kê đầy đủ các thuật toán phổ biến. Nếu có thiếu sót, hoan nghênh mọi người góp ý hoặc gửi PR.
Các bài toán liên quan hiện vẫn đang được bổ sung dần, và các bài viết giải thích chi tiết cũng đang trong quá trình hoàn thiện.

Việc luyện giải bài tập chỉ là một phương tiện để nâng cao năng lực thuật toán,
mục tiêu cuối cùng phải là nâng cao tư duy.
Kiến thức cần được kết tinh thành từng khối, vì vậy hãy tổng hợp chúng trong hai phần đầu của chương một để nâng tầm hiểu biết.
Tác giả hy vọng rằng sau khi bạn đã luyện xong các bài tập, khi quay lại xem bảng tổng hợp này,
bạn có thể hệ thống hóa kiến thức một cách rõ ràng, phát hiện phần còn thiếu và nhanh chóng hoàn thiện nền tảng của mình.

Thuật toánPhân loại / Biến thểBài toán liên quanBài viết giải thích
Thuật toán sắp xếp (Sorting Algorithms)1. Sắp xếp nổi bọt (Bubble Sort)
2. Sắp xếp chèn (Insertion Sort)
3. Sắp xếp chọn (Selection Sort)
4. Sắp xếp Shell (Shell Sort)
5. Sắp xếp nhanh (Quick Sort)
6. Sắp xếp trộn (Merge Sort)
7. Sắp xếp heap (Heap Sort)
8. Thuật toán sắp xếp tuyến tính (Linear Time Sorting)
9. Sắp xếp tự thích nghi (Introspective Sort / IntroSort)
10. Sắp xếp gián tiếp (Indirect Sort)
11. Sắp xếp đếm (Counting Sort)
12. Sắp xếp cơ số (Radix Sort)
13. Sắp xếp theo thùng (Bucket Sort)
14. Sắp xếp ngoài – k-way merge với Loser Tree
15. Sắp xếp ngoài – Cây trộn tối ưu (Optimal Merge Tree)
Đệ quy & Chia để trị (Recursion & Divide and Conquer)1. Tìm kiếm nhị phân (Binary Search)
2. Nhân số nguyên lớn (Large Integer Multiplication)
3. Nhân ma trận Strassen (Strassen Matrix Multiplication)
4. Bài toán phủ bàn cờ (Chessboard Covering)
5. Sắp xếp trộn (Merge Sort)
6. Sắp xếp nhanh (Quick Sort)
7. Lựa chọn thời gian tuyến tính (Linear Time Selection)
8. Bài toán cặp điểm gần nhất (Closest Pair of Points)
9. Lập lịch thi đấu vòng tròn (Round-Robin Tournament Scheduling)
Quy hoạch động (Dynamic Programming)1. Nhân chuỗi ma trận (Matrix Chain Multiplication)
2. Dãy con chung dài nhất (Longest Common Subsequence – LCS)
3. Tổng đoạn con lớn nhất (Maximum Subarray Sum)
4. Chia tam giác đa giác lồi tối ưu (Optimal Polygon Triangulation)
5. Trò chơi đa giác (Polygon Game)
6. Nén ảnh (Image Compression)
7. Bố trí dây mạch (Circuit Wiring)
8. Lập lịch dây chuyền sản xuất (Flow Shop Scheduling)
9. Bài toán ba lô 0-1 (0-1 Knapsack Problem)
10. Cây tìm kiếm nhị phân tối ưu (Optimal BST)
11. Kỹ thuật tăng tốc DP (DP Optimization Techniques)
12. Quy hoạch động trên cây (Tree DP)
Thuật toán tham lam (Greedy Algorithms)1. Bài toán sắp xếp hoạt động (Activity Selection)
2. Bài toán chất hàng tối ưu (Optimal Loading)
3. Mã hóa Huffman (Huffman Coding)
4. Đường đi ngắn nhất đơn nguồn (Single-Source Shortest Path)
5. Cây khung nhỏ nhất (Minimum Spanning Tree)
6. Bài toán lập lịch đa máy (Multi-Machine Scheduling)
Quay lui (Backtracking)1. Bài toán chất hàng
2. Lập lịch công việc theo lô (Batch Job Scheduling)
3. Bài toán tam giác ký hiệu (Symbol Triangle Problem)
4. Bài toán N-Queens
5. Ba lô 0-1
6. Bài toán clique lớn nhất (Maximum Clique)
7. Tô màu đồ thị m-màu (Graph m-Coloring)
8. Bài toán người du lịch (Travelling Salesman Problem – TSP)
9. Bài toán sắp xếp vòng tròn (Circular Arrangement)
10. Bố trí bảng mạch (Circuit Board Arrangement)
11. Bài toán tem bưu chính liên tiếp (Consecutive Postage)
Tìm kiếm (Search)1. Liệt kê (Enumeration)
2. DFS (Depth-First Search)
3. BFS (Breadth-First Search)
4. Tìm kiếm heuristic (Heuristic Search)
Thuật toán ngẫu nhiên (Randomized Algorithms)1. Số ngẫu nhiên (Random Numbers)
2. Thuật toán ngẫu nhiên số học (Numerical Randomized Algorithms)
3. Thuật toán Sherwood
4. Thuật toán Las Vegas
5. Thuật toán Monte Carlo		1. Tính số π
2. Tính tích phân xác định
3. Giải hệ phương trình phi tuyến
4. Thuật toán lựa chọn thời gian tuyến tính
5. Skip List
6. Bài toán N-Queens
7. Phân tích thừa số nguyên
8. Bài toán phần tử chủ đạo (Majority Element)
9. Kiểm tra số nguyên tố
Lý thuyết đồ thị (Graph Theory)1. Duyệt đồ thị DFS / BFS
2. Mạng AOV / AOE
3. Kruskal (MST)
4. Prim (MST)
5. Borůvka (MST)
6. Dijkstra (SSSP)
7. Bellman-Ford (SSSP)
8. SPFA (SSSP)
9. Floyd-Warshall (APSP)
10. Johnson (APSP)
11. Fleury (Chu trình Euler)
12. Ford-Fulkerson (Max Flow)
13. Edmonds-Karp (Max Flow)
14. Dinic (Max Flow)
15. Push-Relabel
16. HLPP (Highest Label Preflow Push)
17. Primal-Dual (Min-Cost Flow)
18. Kosaraju (SCC)
19. Tarjan (SCC)
20. Gabow (SCC)
21. Hungarian (Bipartite Matching)
22. Hopcroft-Karp
23. Kuh-Munkres (Assignment Problem)
24. Edmonds’ Blossom Algorithm		1. Duyệt đồ thị
2. Liên thông mạnh/yếu
3. Đỉnh cắt / Cạnh cắt
4. AOV & sắp xếp topo
5. AOE & đường găng
6. MST & MST thứ hai
7. Đường đi ngắn nhất / K-shortest paths
8. Max Flow
9. Min-Cost Flow
10. Tô màu đồ thị
11. Hệ ràng buộc sai phân
12. Chu trình Euler
13. Bài toán người đưa thư Trung Quốc
14. Chu trình Hamilton
15. Bao phủ cạnh / đỉnh
16. Ghép cặp đồ thị hai phía
17. Đồ thị xương rồng (Cactus Graph)
18. Đồ thị dây (Chordal Graph)
19. Bài toán hôn nhân ổn định (Stable Marriage)
20. Clique lớn nhất
Số học (Number Theory)1. Ước chung lớn nhất (GCD)
2. Bội chung nhỏ nhất (LCM)
3. Phân tích thừa số nguyên tố
4. Kiểm tra số nguyên tố
5. Chuyển đổi cơ số
6. Tính toán độ chính xác cao
7. Bài toán chia hết
8. Đồng dư (Congruence)
9. Hàm Euler φ(n)
10. Thuật toán Euclid mở rộng
11. Nhóm hoán vị (Permutation Group)
12. Hàm sinh (Generating Function)
13. Biến đổi rời rạc
14. Khai triển Cantor
15. Ma trận
16. Vector
17. Hệ phương trình tuyến tính
18. Quy hoạch tuyến tính
Hình học tính toán (Computational Geometry)1. Bao lồi – Gift Wrapping Algorithm
2. Bao lồi – Graham Scan
3. Bài toán đoạn thẳng
4. Đa giác & đa diện
NP-Complete1. Mô hình tính toán
2. Lớp P và NP
3. Bài toán NP-Complete
4. Thuật toán xấp xỉ cho NP-Complete		1. RAM Model
2. RASP Model
3. Máy Turing
4. Máy Turing không xác định
5. Ngôn ngữ P & NP
6. Kiểm chứng đa thức
7. Biến đổi đa thức
8. Định lý Cook
9. CNF-SAT
10. 3-SAT
11. CLIQUE
12. VERTEX-COVER
13. SUBSET-SUM
14. HAM-CYCLE
15. TSP
16. Xấp xỉ Vertex-Cover
17. Xấp xỉ TSP
18. TSP thỏa bất đẳng thức tam giác
19. TSP tổng quát
20. Xấp xỉ Set-Cover
21. Xấp xỉ Subset-Sum
22. Thuật toán mũ cho Subset-Sum
23. Lược đồ xấp xỉ đa thức
Phép toán bit (Bit Manipulation)Các phép toán gồm:
1. NOT
2. OR
3. XOR
4. AND
5. Dịch bit (Bit Shift)		1. AND theo phạm vi số
2. Kiểm tra UTF-8 hợp lệ
3. Chuyển số sang hệ thập lục phân
4. Chuỗi con “siêu tuyệt vời” dài nhất
5. XOR mảng
6. Tập lũy thừa (Power Set)
7. Đếm số bit 1
8. Đếm bit nguyên tố
9. Truy vấn XOR mảng con		LeetCode: Bit Manipulation
-------------------------------------------------------------------------------------------------------------------------------------------------------------------