Thuật toán là gì: hiểu qua công thức pha một cốc nước chanh

Thuật toán là một dãy bước rõ ràng, làm đúng thứ tự thì từ những thứ có sẵn lúc đầu sẽ ra được kết quả mình muốn. Công thức pha một cốc nước chanh là một thuật toán: đầu vào là chanh, đường, nước, đá; đầu ra là cốc nước chanh vừa miệng. Chương trình máy tính cũng chỉ là thuật toán, có điều được viết bằng thứ ngôn ngữ mà máy hiểu.

Nói gọn: thuật toán gồm ba phần

Dù là bấm máy giặt, giải một phép chia hay chỉ đường cho người lạ, thuật toán nào cũng có ba phần:

• Đầu vào: những thứ mình có trước khi bắt đầu. Với nước chanh là một quả chanh, hai thìa đường, một cốc nước, vài viên đá.
• Các bước xử lý: làm gì, làm theo thứ tự nào, làm bao nhiêu lần.
• Đầu ra: kết quả cuối cùng, thứ mà ai cũng kiểm tra được là đúng hay sai.

Điểm quan trọng nhất: một người không biết gì về nước chanh, chỉ cần đọc đúng các bước và làm đúng như thế, cũng phải pha ra được cốc nước chanh. Nếu phải đoán, phải "tự hiểu", thì đó chưa phải thuật toán tốt.

Viết thử thuật toán pha nước chanh

Thử viết như thể đang dặn một người chưa vào bếp bao giờ. Lần đầu, phần lớn mọi người viết kiểu này:

1. Vắt chanh.
2. Cho đường vào.
3. Đổ nước, khuấy đều.
4. Cho đá.

Đọc lên thấy ổn. Nhưng nếu đưa cho một người làm đúng từng chữ, chuyện sẽ khác: vắt chanh vào đâu? Cả quả chanh nguyên vỏ à? Bao nhiêu đường? Nước nóng hay nguội? Khuấy bằng gì, bao lâu thì gọi là "đều"? Bản viết lại cẩn thận hơn sẽ thế này:

1. Lấy một cốc thuỷ tinh sạch, đặt lên bàn.
2. Lấy nửa quả chanh đã được người lớn cắt sẵn.
3. Cầm nửa quả chanh, mặt cắt úp xuống miệng cốc, bóp cho nước chảy vào cốc. Gạt hạt chanh rơi vào cốc ra ngoài.
4. Múc hai thìa cà phê đường, đổ vào cốc.
5. Rót nước lọc nguội vào cốc tới khi cách miệng cốc khoảng hai đốt ngón tay.
6. Dùng thìa khuấy cho tới khi không còn thấy hạt đường dưới đáy cốc.
7. Nếm thử. Nếu chua quá thì thêm nửa thìa đường và quay lại bước 6. Nếu vừa thì sang bước 8.
8. Thả bốn viên đá vào cốc.

Bản thứ hai dài gấp đôi, nhưng ai cầm nó cũng ra gần như cùng một cốc nước. Để ý bước 7: nó có một điều kiện (nếu chua quá thì…) và một vòng lặp (quay lại bước 6). Hai thứ này là những viên gạch cơ bản của mọi chương trình máy tính, và mỗi thứ có một bài riêng trong danh mục này.

Năm đặc điểm của một thuật toán tốt

Các sách nhập môn khoa học máy tính thường nêu những đặc điểm sau. Bảng dưới đối chiếu từng đặc điểm với cốc nước chanh:

Đặc điểm	Nghĩa là	Với cốc nước chanh
Rõ ràng	Mỗi bước chỉ hiểu được một cách	"Hai thìa cà phê đường" chứ không phải "ít đường"
Có thứ tự	Bước nào trước, bước nào sau là cố định	Khuấy tan đường rồi mới thả đá, vì đường tan chậm trong nước lạnh
Hữu hạn	Chắc chắn dừng sau một số bước	Vòng "nếm, thêm đường" phải có lúc kết thúc khi đã vừa
Có đầu vào, đầu ra	Biết cần gì và sẽ ra cái gì	Chanh, đường, nước, đá thành một cốc nước chanh
Làm được	Mỗi bước nằm trong khả năng người làm	Không ghi "vắt cho nước chanh thật ngon", vì đó không phải động tác

Đặc điểm "hữu hạn" nghe thì hiển nhiên mà hay bị quên nhất. Hãy tưởng tượng bước 7 ghi: "Nếm thử, thêm đường, quay lại bước 6". Không có điều kiện dừng, người làm theo sẽ thêm đường mãi cho tới khi cốc tràn. Máy tính gặp lỗi kiểu này thì treo, đứng hình, quạt chạy ầm ầm.

Chữ "thuật toán" từ đâu ra

Trong tiếng Anh, thuật toán là algorithm. Chữ này bắt nguồn từ tên một nhà toán học sống ở Baghdad vào thế kỷ thứ 9: Muhammad ibn Musa al-Khwarizmi. Ông làm việc ở Ngôi nhà Trí tuệ, một trung tâm dịch thuật và nghiên cứu lớn thời đó, và viết sách hướng dẫn cách làm tính với các chữ số Ấn Độ, chính là những chữ số 0 đến 9 ta dùng hôm nay. Khi sách được dịch sang tiếng Latinh ở châu Âu, tên ông bị đọc chệch thành "Algoritmi", rồi dần dần chữ này dùng để chỉ chính những quy tắc tính toán từng bước. Cũng từ một cuốn sách của ông mà có chữ algebra, tức đại số.

Nhưng con người dùng thuật toán từ lâu trước khi có tên gọi. Khoảng năm 300 trước Công nguyên, nhà toán học Hy Lạp Euclid đã ghi lại cách tìm ước chung lớn nhất của hai số bằng cách trừ đi trừ lại số nhỏ khỏi số lớn. Cách ấy đến nay vẫn được dạy và vẫn chạy trong máy tính. Phép chia đặt tính dọc mà học sinh tiểu học Việt Nam học cũng là một thuật toán: hạ chữ số, chia, nhân, trừ, rồi lặp lại.

Năm 1843, Ada Lovelace, một nhà toán học người Anh, viết những ghi chú dài cho chiếc Máy Giải tích mà Charles Babbage thiết kế nhưng chưa bao giờ hoàn thành. Trong đó có một bảng các bước để máy tính ra một dãy số gọi là số Bernoulli. Bảng ấy thường được nhắc tới như một trong những chương trình máy tính đầu tiên được viết ra, dù các nhà sử học vẫn còn bàn cãi phần đóng góp của bà và của Babbage.

Thuật toán đang ở quanh bạn

Khi đã biết nhìn, bạn sẽ thấy thuật toán ở khắp nơi:

• Gấp áo phông: trải áo, gập hai tay áo vào giữa, gập đôi từ dưới lên. Cửa hàng quần áo dạy nhân viên đúng một cách gấp để chồng áo nào cũng bằng nhau.
• Chỉ đường: "Đi thẳng đến ngã tư thứ hai, rẽ phải, qua cây xăng thì nhà thứ ba bên trái." Đây là thuật toán có đầu vào (chỗ đang đứng) và đầu ra (cổng nhà).
• Nồi cơm điện: nấu tới khi hết nước thì tự chuyển sang giữ ấm. Bên trong là một quy tắc "nếu… thì…" làm bằng linh kiện cảm nhận nhiệt.
• Đèn giao thông: xanh một khoảng, vàng vài giây, đỏ một khoảng, rồi quay lại từ đầu.
• Xếp hàng lấy số ở ngân hàng, bệnh viện: ai đến trước lấy số nhỏ, gọi theo thứ tự số.

Điểm chung: một người chưa từng làm, đọc đúng hướng dẫn, vẫn làm được. Đó là lý do thuật toán quan trọng. Nó cho phép đóng gói kinh nghiệm của một người thành thứ mà người khác, hoặc cỗ máy, làm lại được.

Vì sao máy tính cần được dặn kỹ đến thế

Người làm theo công thức có thể tự đoán: "đổ nước" thì chắc là nước lọc, không phải nước mắm. Máy tính không đoán. Nó làm đúng y như được viết, không hơn không kém, và làm rất nhanh, có thể hàng tỉ phép tính mỗi giây. Nhanh mà không biết đoán, nên chỉ cần một bước viết mơ hồ là máy làm sai, sai rất nhanh và sai rất nhiều lần.

Vì vậy người lập trình dành phần lớn thời gian không phải để gõ, mà để nghĩ: tình huống nào có thể xảy ra? Nếu hết đường thì sao? Nếu cốc đã đầy thì sao? Thói quen tự hỏi những câu như thế có ích cả khi bạn không bao giờ viết một dòng mã nào, ví dụ khi lên kế hoạch cho một chuyến dã ngoại hay viết hướng dẫn cho em nhỏ tự pha sữa.

Một thuật toán tốt không đòi người làm theo phải thông minh. Nó đòi người viết ra phải nghĩ kỹ.

Thử làm: "Robot làm theo từng chữ"

Đây là hoạt động được nhiều thầy cô dạy tin học dùng trong buổi học đầu tiên, vì nó cho thấy ngay chỗ khó của việc viết thuật toán. Cần hai người trở lên và khoảng 20 phút.

Chuẩn bị

• Một cốc, một bình nước lọc, đường, thìa, vài nửa quả chanh đã được người lớn cắt sẵn (bạn nhỏ không tự dùng dao).
• Giấy và bút.

Cách làm

1. Một bạn đóng vai người viết: ngồi quay lưng lại bàn, viết ra giấy các bước pha nước chanh.
2. Một người khác, có thể là bố mẹ, đóng vai robot: làm đúng từng chữ trên giấy, không đoán, không tự thêm. Giấy ghi "cho đường vào" mà không nói vào đâu thì robot đứng yên và hỏi: "Vào đâu?"
3. Mỗi lần robot dừng lại hoặc làm sai, người viết sửa bước đó trên giấy rồi robot làm lại từ đầu.
4. Khi robot pha xong một cốc uống được, đếm xem bản cuối có bao nhiêu bước và đã sửa bao nhiêu lần.

Hoạt động này vui nhất khi robot "ngốc" một cách nghiêm túc. Mục đích không phải để chê người viết mà để thấy những điều mình tưởng hiển nhiên hoá ra cần nói rõ. Sau đó thử đổi vai, hoặc đổi đề: buộc dây giày, đánh răng, gói một món quà.

Câu hỏi để bàn sau khi làm xong: bước nào bị sửa nhiều nhất? Có bước nào thừa không? Nếu cần pha mười cốc thì bản hướng dẫn nên thay đổi thế nào? Câu cuối dẫn thẳng tới ý tưởng về vòng lặp.

Câu hỏi thường gặp

Thuật toán là gì, giải thích cho trẻ em thế nào?

Thuật toán là một danh sách các bước rõ ràng để làm xong một việc, ai làm đúng theo cũng ra cùng kết quả. Công thức nấu ăn, cách gấp máy bay giấy hay cách đặt phép chia đều là thuật toán. Máy tính chạy được là vì có người viết sẵn thuật toán cho nó.

Thuật toán và chương trình máy tính khác nhau thế nào?

Thuật toán là cách làm, có thể viết bằng lời, bằng hình vẽ hay bằng sơ đồ. Chương trình là thuật toán đã được viết lại bằng một ngôn ngữ lập trình để máy tính chạy được. Một thuật toán có thể viết thành nhiều chương trình bằng nhiều ngôn ngữ khác nhau.

Chữ algorithm có nguồn gốc từ đâu?

Chữ này bắt nguồn từ tên nhà toán học al-Khwarizmi, sống ở Baghdad vào thế kỷ thứ 9. Sách của ông về cách tính bằng chữ số Ấn Độ được dịch sang tiếng Latinh, tên ông bị đọc thành "Algoritmi", rồi dần trở thành tên gọi của các quy tắc tính toán từng bước.

Một thuật toán tốt cần có những đặc điểm gì?

Mỗi bước phải rõ ràng, chỉ hiểu được một cách; các bước có thứ tự; thuật toán phải dừng sau một số bước; có đầu vào và đầu ra xác định; và mỗi bước phải là việc người làm hoặc máy làm được. Thiếu điều kiện dừng là lỗi hay gặp nhất.

Học thuật toán có cần máy tính không?

Không. Phần cốt lõi là cách nghĩ: chia việc thành bước, sắp thứ tự, lường trước tình huống. Những việc này học được bằng giấy bút, bằng hoạt động trong bếp hay ngoài sân. Máy tính chỉ cần đến khi muốn cho máy chạy thuật toán đó.