Thuật toán ở khắp mọi nơi

Khi nghe đến từ "thuật toán", chúng ta thường nghĩ ngay đến toán học một cách rất tự nhiên. Tuy nhiên trên thực tế, nhiều thuật toán không đòi hỏi toán học phức tạp, mà phụ thuộc nhiều hơn vào logic cơ bản, vốn hiện diện khắp nơi trong cuộc sống hàng ngày của chúng ta.

Trước khi chính thức đi sâu tìm hiểu về thuật toán, có một sự thật thú vị đáng chia sẻ: bạn đã học được nhiều thuật toán từ lúc nào không hay và đã quen áp dụng chúng vào cuộc sống hàng ngày. Dưới đây, tôi sẽ đưa ra một vài ví dụ cụ thể để minh họa cho điều này.

Ví dụ 1: Tra từ điển. Trong một cuốn từ điển, các từ được sắp xếp theo thứ tự bảng chữ cái. Giả sử chúng ta đang tìm kiếm một từ bắt đầu bằng chữ cái \(r\), quy trình này thường được thực hiện theo cách sau:

1. Mở từ điển đến khoảng giữa và kiểm tra từ đầu tiên trên trang đó; giả sử nó bắt đầu bằng chữ cái \(m\).
2. Vì \(r\) đứng sau \(m\) trong bảng chữ cái, ta có thể bỏ qua nửa đầu và thu hẹp phạm vi tìm kiếm ở nửa sau.
3. Lặp lại bước 1. và 2. cho đến khi bạn tìm thấy trang có từ bắt đầu bằng chữ cái \(r\).

<1><2><3><4><5>

Tra từ điển, một kỹ năng cơ bản của học sinh tiểu học, thực chất chính là thuật toán "Tìm kiếm nhị phân" (Binary Search) nổi tiếng. Dưới góc độ cấu trúc dữ liệu, chúng ta có thể xem cuốn từ điển là một "mảng" (array) đã được sắp xếp; dưới góc độ thuật toán, chuỗi thao tác tra từ điển kể trên có thể được xem là thuật toán "Tìm kiếm nhị phân".

Ví dụ 2: Sắp xếp quân bài. Khi chơi bài, chúng ta cần sắp xếp các quân bài trên tay theo thứ tự tăng dần, quy trình thực hiện như hình dưới đây.

1. Chia các quân bài thành hai phần: "đã sắp xếp" và "chưa sắp xếp", giả định ban đầu quân bài ngoài cùng bên trái đã được sắp xếp.
2. Rút một quân bài từ phần chưa sắp xếp và chèn nó vào vị trí chính xác trong phần đã sắp xếp; sau khi hoàn thành, hai quân bài ngoài cùng bên trái đã được sắp xếp.
3. Lặp lại bước 2 cho đến khi tất cả các quân bài đều được sắp xếp.

Phương pháp sắp xếp quân bài nói trên về bản chất là thuật toán "Sắp xếp chèn" (Insertion Sort), vốn rất hiệu quả khi xử lý các tập dữ liệu nhỏ. Nhiều hàm sắp xếp tích hợp sẵn trong các ngôn ngữ lập trình sử dụng thuật toán sắp xếp chèn này ở bên dưới.

Ví dụ 3: Trả tiền thừa. Giả sử chúng ta mua hàng hết \(69\) đồng tại siêu thị. Nếu đưa cho nhân viên thu ngân \(100\) đồng, họ sẽ cần trả lại cho bạn \(31\) đồng tiền thừa. Quá trình này có thể được hình dung một cách rõ ràng qua hình minh họa dưới đây.

1. Các mệnh giá có sẵn nhỏ hơn \(31\) là \(1\), \(5\), \(10\) và \(20\).
2. Lấy ra mệnh giá lớn nhất là \(20\) từ các lựa chọn, còn lại \(31 - 20 = 11\).
3. Lấy ra mệnh giá lớn nhất là \(10\) từ các lựa chọn còn lại, còn lại \(11 - 10 = 1\).
4. Lấy ra mệnh giá lớn nhất là \(1\) từ các lựa chọn còn lại, còn lại \(1 - 1 = 0\).
5. Hoàn tất việc trả tiền thừa, phương án giải quyết là \(20 + 10 + 1 = 31\).

Trong các bước trên, ở mỗi bước chúng ta đều đưa ra lựa chọn có vẻ là tốt nhất ở thời điểm đó (cố gắng sử dụng mệnh giá lớn nhất có thể), từ đó tìm ra phương án trả tiền thừa khả thi. Dưới góc độ cấu trúc dữ liệu và thuật toán, cách tiếp cận này về bản chất là thuật toán "Tham lam" (Greedy).

Từ những việc nhỏ như nấu một bữa ăn cho đến việc lớn như du hành vũ trụ, hầu hết mọi vấn đề được giải quyết đều cần đến thuật toán. Sự xuất hiện của máy tính giúp chúng ta lưu trữ các cấu trúc dữ liệu trong bộ nhớ, đồng thời viết mã để gọi CPU và GPU thực thi thuật toán. Bằng cách này, chúng ta có thể chuyển các bài toán ngoài đời thực vào máy tính và giải quyết nhiều vấn đề phức tạp khác nhau một cách hiệu quả hơn.

Tip

Nếu các khái niệm như cấu trúc dữ liệu, thuật toán, mảng và tìm kiếm nhị phân vẫn còn khiến bạn cảm thấy mơ hồ, hãy tiếp tục đọc. Cuốn sách này sẽ dẫn dắt bạn bước vào thế giới của cấu trúc dữ liệu và thuật toán.