Bài 6. Thuật toán: những bước ai làm theo cũng ra đúng

Nhắc lại thật nhanh

Ở Bài 5, phép cộng có nhớ luôn đi theo cùng một chuỗi bước: bắt đầu từ cột đơn vị, cộng, nhớ nếu cần, sang cột bên trái. Ai làm đúng từng bước cũng ra cùng kết quả. Bài này đặt tên cho kiểu chỉ dẫn đó: thuật toán.

1. Thuật toán là gì?

Thuật toán là một dãy bước để giải một việc, sao cho:

1. Rõ ràng: mỗi bước chỉ có một cách hiểu.
2. Có thứ tự: biết bước nào làm trước, bước nào làm sau.
3. Có điểm kết thúc: biết chắc lúc nào là xong.

Thiếu một trong ba điều, người làm theo sẽ lúng túng, mỗi người làm một kiểu, hoặc làm mãi không xong.

2. Vì sao máy bay giấy của Bông không bay?

Năm bước của Lan:

1. Gấp đôi tờ giấy theo chiều dọc rồi mở ra.
2. Gấp hai góc trên vào đường giữa.
3. Gấp hai mép xiên vào đường giữa thêm lần nữa.
4. Gấp đôi lại theo đường giữa.
5. Gấp mỗi bên xuống thành một cánh.

Bông mới 7 tuổi, không cần hiểu vì sao máy bay bay được. Bông chỉ cần làm đúng từng bước. Đó chính là sức mạnh của thuật toán.

3. Đầu vào và đầu ra

Mỗi thuật toán nhận vào một thứ và trả ra một thứ:

Điều quan trọng: cùng một đầu vào, làm đúng cùng một thuật toán, thì luôn ra cùng một đầu ra, bất kể ai làm, làm ở đâu, làm lúc nào.

4. Thuật toán cộng của al-Khwārizmī

Khoảng năm 820, ở Baghdad, học giả al-Khwārizmī viết sách dạy tính bằng mười chữ số kiểu Ấn Độ, có cả số 0 (Bài 4). Ông không chỉ đưa đáp án, mà viết ra từng bước:

1. Viết hai số thẳng cột, hàng đơn vị dưới hàng đơn vị.
2. Cộng từ cột bên phải.
3. Nếu được mười hoặc hơn, viết chữ số cuối và nhớ một sang cột bên trái.
4. Làm tiếp cột kế bên, cho đến hết các cột.

Làm thử với 275 + 148:

Kết quả: 423. Một thương nhân và một cậu học trò, ở hai nơi khác nhau, làm đúng các bước này thì đều ra 423.

5. Bước có kiểm tra điều kiện

Hãy để ý bước 3: "Nếu được mười hoặc hơn, thì…". Đây là một bước kiểm tra điều kiện: người làm nhìn vào tình huống rồi chọn việc phù hợp. Điều kiện phải rõ ràng, có câu trả lời chắc chắn là đúng hoặc sai.

Ví dụ một thuật toán tính tiền ở cửa hàng:

1. Lấy giá một món nhân với số lượng, được tổng tiền.
2. Nếu tổng tiền từ 100.000 đồng trở lên thì trừ đi 10.000 đồng.
3. Đọc ra số tiền phải trả.

Mua 3 quyển sách, mỗi quyển 35.000 đồng: tổng 105.000 đồng, từ 100.000 trở lên nên trừ 10.000, phải trả 95.000 đồng.

6. Từ tên một người thành tên một khái niệm

Khoảng 300 năm sau, vào thế kỷ 12, sách của al-Khwārizmī được dịch sang tiếng Latin ở châu Âu. Một bản dịch mở đầu bằng câu "Dixit Algorizmi", nghĩa là "Algorizmi đã nói rằng". Dần dần, tên ông biến thành từ "algorism", rồi "algorithm" trong tiếng Anh, mà tiếng Việt gọi là thuật toán.

Một cuốn sách khác của ông có chữ "al-jabr" trong tên sách. Từ đó sinh ra chữ "algebra", tức là đại số. Một người mà để lại tên cho hai từ quan trọng của toán học!

7. Máy tính chỉ làm đúng những gì được viết ra

Con người đọc "cho nước vừa đủ" vẫn đoán được đại khái. Máy tính thì không đoán. Nó chỉ làm đúng những bước được viết cho nó, theo đúng thứ tự.

Bản đồ trên điện thoại, chương trình máy giặt, công thức nấu ăn đều là thuật toán. Người viết chương trình máy tính, gọi là lập trình viên, có nhiệm vụ viết thuật toán rõ hơn cả năm bước gấp máy bay của Lan.

Ghi nhớ

• Thuật toán: dãy bước rõ ràng, có thứ tự, có điểm kết thúc.
• Cùng đầu vào, làm đúng cùng thuật toán thì luôn ra cùng đầu ra. Người làm không cần hiểu vì sao nó đúng.
• Một bước có thể kiểm tra điều kiện ("nếu… thì…"), nhưng điều kiện phải có câu trả lời chắc chắn đúng hoặc sai.
• Từ "algorithm" đến từ tên al-Khwārizmī (Baghdad, khoảng năm 820), qua bản dịch Latin "Dixit Algorizmi".
• Máy tính không đoán: thuật toán cho máy phải rõ ràng tuyệt đối.