Thuật toán chia để trị

Trong khoa học máy tính, chia để trị là một mô hình thiết kế thuật toán quan trọng dựa trên đệ quy với nhiều phân nhánh. Thuật toán chia để trị hoạt động bằng cách chia bài toán thành nhiều bài toán nhỏ hơn thuộc cùng thể loại, cứ như vậy lặp lại nhiều lần, cho đến khi bài toán thu được đủ đơn giản để có thể giải quyết trực tiếp. Sau đó lời giải của các bài toán nhỏ được tổng hợp lại thành lời giải cho bài toán ban đầu.

Kĩ thuật này là cơ sở cho nhiều thuật toán hiệu quả, chẳng hạn như thuật toán sắp xếp (sắp xếp nhanh, sắp xếp trộn), thuật toán nhân (thuật toán Karatsuba), thuật toán phân tích cú pháp, thuật toán biến đổi Fourier rời rạc.

Tuy nhiên, khả năng hiểu và thiết kế thuật toán chia để trị là một kĩ năng đòi hỏi nhiều thời gian để làm chủ. Tương tự như chứng minh quy nạp, trong một số trường hợp, ta phải thay thế bài toán ban đầu bằng một bài toán tổng quát hơn để có thể tạo ra mối liên hệ đệ quy. Không có một phương pháp có hệ thống nào để tìm ra bài toán tổng quát thích hợp trong mọi trường hợp.

Tên gọi "chia để trị" đôi khi cũng được áp dụng cho các thuật toán quy bài toán ban đầu về đúng một bài toán nhỏ hơn, chẳng hạn như thuật toán tìm kiếm nhị phân, dùng cho việc tìm khóa trong một danh sách đã sắp xếp.^[1] Những thuật toán này có thể được lập trình hiệu quả hơn thuật toán chia để trị thông thường: đặc biệt, nếu các thuật toán này dùng đệ quy đuôi thì có thể chuyển chúng thành một vòng lặp thay vì đệ quy. Vì vậy nhiều tác giả cho rằng tên "chia để trị" chỉ nên dùng cho trường hợp mỗi bài toán có thể được chia thành hai hay nhiều hơn bài toán nhỏ.^[2] Có tác giả đã đề xuất tên "giảm để trị" cho trường hợp quy về đúng một bài toán nhỏ hơn.^[3]

Chứng minh tính đúng đắn của thuật toán chia để trị thường sử dụng quy nạp. Thời gian chạy của chúng thường được tính thông qua hệ thức truy hồi.

Một số ví dụ

Một ví dụ lâu đời của thuật toán chia để trị là thuật toán Cooley-Tukey cho biến đổi Fourier rời rạc. Thuật toán này được phát hiện bởi Gauss năm 1805 nhưng ông không phân tích số phép tính của thuật toán và thuật toán này chỉ trở nên phổ biến khi được phát hiện lại hơn một thế kỉ sau đó.

Một ví dụ lâu đời khác là thuật toán sắp xếp trộn, phát hiện bởi John von Neumann năm 1945.

Một ví dụ quan trọng nữa là thuật toán của Anatolii A. Karatsuba phát hiện năm 1960 cho việc nhân hai số nguyên n chữ số trong ${\displaystyle O(n^{\log _{2}3})}$ phép tính. Thuật toán này bác bỏ giả thuyết của Andrey Kolmogorov năm 1956 rằng nhân hai số nguyên n chữ số đòi hỏi ${\displaystyle \Omega (n^{2})}$ phép tính.

Ghi chú

1. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein (2009). Introduction to Algorithms. MIT Press.
2. G. Brassard,P. Bratley (1996). Fundamental of Algorithmics. Prentice-Hall.
3. Anany V. Levitin (2002). Introduction to the Design and Analysis of Algorithms. Addison Wesley.