Một vài kỹ thuật lập trình
Bùi Việt Hà
Bài viết này là lược dịch từ chương 10 ″Algorithm Design Techniques″ của quyển sách nổi
tiếng ″Data Structure and Algorithms″ của các tác giả Aho A.V., Hopcroft J.E. và Ullman
J.D. Tiêu đề do người biên soạn bài viết tự đặt.
Các bạn trẻ thân mến.
Thuật toán, kỹ thuật lập trình luôn là một điều bí ẩn và hấp dẫn đối với các bạn trẻ, các bạn
học sinh và sinh viên đang ngồi trên ghế nhà trường. Nhiều bài toán khó, đa dạng tưởng
chừng như không thể tìm được lời giải lại ẩn chứa bên trong những thuật toán đơn giản,
tuyệt đẹp đến không ngờ. Cuốn sách ″Data Structure and Algorithms″ của các tác giả Aho
A.V., Hopcroft J.E. và Ullman J.D đã ra đời cách đây 20 năm nhưng giờ đây đọc lại vẫn
thấy rất mới mẻ và chứa đựng nhiều ý tưởng hay. Đặc biệt chương ″Một vài kỹ thuật thiết
kế thuật toán″ chứa đựng nhiều ý tưởng xác định cho toàn bộ định hướng nghiên cứu và
giải quyết bài toán của ngày hôm nay. Nhân dịp số báo đặc biệt Tết Quí Mùi, chúng tôi
chân trọng giới thiệu với bạn đọc, đặc biệt là các bạn học sinh, sinh viên chuyên tin lược
dịch của chương này. Trong quá trình biên soạn, chúng tôi đã thay đổi chút ít cho phù hợp
với đối tượng của độc giả Tin học & Nhà trường. Trong khi trình bày thuật toán các tác giả
đã sử dụng khá nhiều kỹ thuật phân tích đánh giá độ phức tạp, đối với các bạn lần đầu làm
quen với những khái niệm này có thể hoàn toàn bỏ qua chúng mà không ảnh hưởng gì đến
việc đọc các phần khác của bài viết. Chúc các bạn một năm mới với nhiều sáng tạo mới, và
mong rằng những ý tưởng của bài viết này được các bạn tiếp nhận và áp dụng sáng tạo
trong công việc của mình.
1. Thuật toán Chia để Trị (Divide & Conquer) Có lẽ thuật toán được sử dụng nhiều
nhất, quan trọng nhất là kỹ thuật ″Chia để Trị″. Kỹ thuật này sẽ chia bài toán hiện thời
thành N bài toán nhỏ hơn, thực hiện lời giải cho từng bài toán nhỏ này và từ đó xây dựng
thuật toán cho bài toán lớn tổng hợp. Ví dụ cho các thuật toán này là Sắp xếp Trộn
(1)
hoặc
Tìm kiếm Nhị phân
(2)
mà các bạn đã đã được biết trong chương trình Tin học Cơ bản.

X = A | B (X = A2
n/2
+ B)
Y = C | D (Y = C2
n/2
+ D)
Khi đó tích XY sẽ có dạng:
XY = AC2
n
+ (AD+BC)2
n/2
+ BD (1)
Dựa trên công thức (1) ta có thể suy luận đơn giản như sau cho việc tính tích XY: chúng ta
sẽ tính 4 phép nhân với các số n/2-bit là AC, AD, BC và BD, sau đó thực hiện 3 phép cộng
với các số 2n-bit, cuối cùng là 2 phép chuyển chữ số (2 phép nhân với lũy thừa của 2) Các
phép cộng và phép chuyển chữ số đều được thực hiện với thời gian O(n), do đó ta thu được
công thức tính độ phức tạp của phép toán trên T(n) là:
T(1) = 1
T(n) = 4T(n/2) + C.n (C-const) (2)
Công thức (2) cho ta T(n) = O(n
2
) và như vậy ta chưa thu được kết quả gì mới so với
phương pháp tính từ nhà trường phổ thông.
Bây giờ ta biến đổi công thức (1) dưới dạng:
XY = AC2
n
+ ((A-B)(D-C) + AC + BD)2
n/2
+ BD (2)
Công thức (2) mặc dù phức tạp hơn (1) nhưng chúng có thể được tính bởi:

thể tổng quát quá trình này cho trường hợp tổng quát n=2
k
bất kỳ.
2.Thuật toán Qui Hoạch Động (Dynamic Programming)
Trong phần trên chúng ta đã thấy sức mạnh của kỹ thuật Chia để Trị bằng cách chia nhỏ
bài toán cần làm. Tuy nhiên không phải bao giờ cũng có thể chia nhỏ bài toán thành các bài
toán con và từ đó tìm ra lời giải của bài toán lớn. Trong các trường hợp như vậy, mặc dù
chúng ta vẫn có thể chia nhỏ bài toán thành nhiều bài toán con, nhưng thời gian thu được
sẽ tăng theo số mũ và thuật toán trở nên vô giá trị.
Trên thực tế, việc chia thành các bài toán con thường chỉ chiếm thời gian là đa thức. Trong
trường hợp này một bài toán con sẽ được lặp lại nhiều lần trong quá trình tìm kiếm lời giải.
Để khỏi mất thời gian mỗi khi giải quyết các bài toán con, các bạn sẽ lưu trữ các lời giải
này để tra cứu về sau mỗi khi cần đến. Công việc này sẽ đòi hỏi độ phức tạp thuật toán là
đa thức.
Có một cách làm còn đơn giản hơn cách đã nêu trên. Chúng ta sẽ lưu giữ tất cả các lời giải
của các bài toán con lại không cần biết rằng chúng có được dùng lại nhiều lần về sau hay
không, không quan tâm đến việc các lời giải này có cần thiết cho lời giải của bài toán chính
của chúng ta hay không. Cách làm như vậy có tên gọi là Qui hoạch động. Bản thân từ qui
hoạch động được lấy từ lý thuyết điều khiển.
Cách cài đặt thực tế của thuật toán qui hoạch động không thống nhất nhưng điều chung
nhất ở chúng là có một cái bảng và chúng ta cần lần lượt điền các thông số vào cái bảng
này. Để minh họa chúng ta hãy xét một vài ví dụ.
Ví dụ 3: Trò chơi Tán thủ
(5)
Giả sử có hai tán thủ A, B cần đấu trực diện với nhau, qui định chung là người thắng trước
n ván sẽ là người thắng cuộc. Trên thực tế thường giá trị n = 4. Giả sử hai tán thủ A, B là
mạnh ngang nhau và do đó sác xuất thắng, thua trong mỗi ván là 50/50. Giả sử P(i,j) là sác
xuất sao cho A cần thắng thêm i ván nữa , B cần thắng thêm j ván nữa thì A sẽ chắc chắn
thắng chung cuộc. Chúng ta cần tính những giá trị P(i,j) này với i, j bất kỳ.
Nếu i=0, j>0, tức là A đã thắng rồi và do đó P(0,j)=1. Nếu i>0, j=0, tức là B đã thắng và A