Thuật toán trong lập trình - Phần 1: Vài nét về thuật toán
Tất cả chúng ta đều nhận thức được rằng, mọi thứ xung quanh thay đổi theo từng ngày, luôn luôn vân động và phát triển. Ngành lập trình cũng vậy, theo thời gian, chúng ta có thể thấy ngày càng nhiều các thuật toán mới khác nhau giải quyết cho nhiều bài toán phức tạp khác nhau. Bên cạnh đó, vẫn có một số thuật toán vẫn tồn tại và giữ được một vai trò nhất định dù thay đổi có xảy ra. Trong series này, chúng ta sẽ cùng tìm hiểu về khái niệm thuật toán cũng như nói về những thuật toán trường tồn này nhé!
Đây sẽ là danh sách các bài viết:
Series này sẽ là tài liệu tham khảo ngắn gọn và nhanh chóng cho newbie, bao gồm các thuật toán cơ bản nhất nhưng vẫn được sử dụng rộng rãi.
Đây là phần đầu tiên Giới thiệu về Thuật toán, hãy cùng xem xét các định nghĩa của các thuật ngữ khác nhau như thuật toán, lưu đồ và mã giả,... cũng như tầm quan trọng của chúng.
Thuật toán - Algorithms
Mặc dù tất cả chúng ta đều đã nghe nói về thuật toán, nhưng có lẽ phần đông không thực sự nắm rõ được “Thuật toán là gì?”, người ta thường nghĩ đó có lẽ là một thủ tục, một hàm nào đó. Vì vậy, đầu tiên, hãy cùng xem xét định nghĩa về thuật toán.
Định nghĩa: Trong toán học và khoa học máy tính, thuật toán là một chuỗi hữu hạn các hướng dẫn được xác định rõ ràng, có thể thực hiện được bằng máy tính, thường để giải quyết một lớp các vấn đề cụ thể hoặc để thực hiện một phép tính. Các thuật toán luôn rõ ràng và được sử dụng làm thông số kỹ thuật để thực hiện tính toán, xử lý dữ liệu, suy luận tự động và các tác vụ khác.
Ví dụ một tình huống thực tế. Giả sử chúng ta muốn pha trà và chúng ta sẽ sử dụng một công thức bao gồm một số bước phải được hoàn thành theo một trình tự cụ thể nào đó để tạo ra một loại trà béo ngậy. Hãy áp dụng điều này vào lập trình và nói rằng pha trà là đặt vấn đề, công thức là quy trình thực hiện và thành phần để pha trà là input, trong khi sản phẩm cuối cùng là ouput.
Vì vậy, một thuật toán chỉ là một quá trình đơn giản được tuân theo để giải quyết một vấn đề cụ thể hoặc thực hiện một số phép tính hoặc nhiều trường hợp sử dụng khác, ví dụ Thuật toán hồi quy tuyến tính được sử dụng để dự đoán giá trị từ dữ liệu.
Hãy nhớ rằng một thuật toán không nhất thiết phải được viết bằng code; nó có thể bắt đầu bằng những mô tả đơn giản. Sau đó được chuyển đổi thành lưu đồ. Cuối cùng chuyển sang mã giả hoặc chúng ta có thể code trực tiếp bằng bất kỳ ngôn ngữ lập trình nào. Tiếp theo, chúng ta sẽ nói về Lưu đồ & Mã giả.
Lưu đồ - Flowcharts
Chắc hẳn bất kì một lập trình viên nào cũng đã từng nhìn thấy sơ đồ này tại một thời điểm nào đó trong cuộc sống của mình. Cùng xem qua định nghĩa của một lưu đồ:
Định nghĩa: Lưu đồ là một loại sơ đồ đại diện cho một quy trình hoặc quy trình làm việc. Lưu đồ cũng có thể được định nghĩa là biểu diễn sơ đồ của một thuật toán, một cách tiếp cận từng bước để giải quyết một nhiệm vụ.
Đây là ví dụ về một sơ đồ đơn giản phác thảo một thuật toán để xác định xem một số là chẵn hay lẻ. Hãy nhìn vào sơ đồ, bạn sẽ nhận thấy lợi ích mà nó đem lại trong việc hiểu các giai đoạn của một thuật toán. Lưu đồ có nhiều thành phần khác nhau, mỗi thành phần mang một ý nghĩa riêng. Dưới đây là những thứ cơ bản nhất của lưu đồ:
Hình bầu dục hoặc hình viên thuốc - Đại diện cho Bắt đầu hoặc Kết thúc thuật toán
Hình chữ nhật - Đại diện cho một quá trình
Hình dạng kim cương - Đại diện cho một quyết định/điều kiện
Hình bình hành - Đại diện cho đầu vào/đầu ra
Ta thấy, lưu đồ này đơn giản trong một hình nhỏ gọn cho thấy rõ ràng rằng nếu một số chia hết cho 2 thì nó là số chẵn và nếu nó không phải là số lẻ. Do đó, rõ ràng là lưu đồ giúp chúng ta ghi nhớ thông tin lâu hơn bằng cách làm cho các giai đoạn của thuật toán trở nên đơn giản và dễ thực hiện hơn.
Mã giả - Pseudocode
Mã giả là từ khóa cuối cùng mà chúng ta sẽ tìm hiểu trong bài viết này. Khi đọc các bài báo trên các trang web như GFG và W3Schools, chúng ta đều thấy một đoạn mô tả được viết bằng tiếng Anh đơn giản trước khi code - người ta gọi đó là mã giả.
Định nghĩa: Trong khoa học máy tính, mã giả là một mô tả bằng ngôn ngữ đơn giản của các bước trong một thuật toán hoặc một hệ thống khác. Mã giả thường sử dụng các quy ước cấu trúc của một ngôn ngữ lập trình thông thường, nhưng nhằm mục đích giúp con người có thể đọc chứ không phải là máy. Nó thường bỏ qua các chi tiết cần thiết để máy có thể hiểu về thuật toán, chẳng hạn như khai báo biến và một ngôn ngữ cụ thể nào đó.
Đây là một ví dụ về mã giả cho lưu đồ và như bạn thấy, chúng ta vừa chuyển đổi lưu đồ sang một mô tả đơn giản. Lợi ích chính của mã giả so với lưu đồ là nó ngắn gọn hơn và dễ hiểu hơn.
-----------------
Quy trình để thiết kế hoặc triển khai một thuật toán là trước tiên hãy nghĩ về các bước sẽ được thực hiện, sau đó chuyển chúng thành một lưu đồ, và cuối cùng chuyển đổi lưu đồ thành mã giả trước khi thực thi hoặc triển khai thuật toán. Mặc dù tuân theo trình tự các bước là tốt, nhưng hoàn toàn không nên cứng nhắc rằng bắt buộc phải tuân theo quy trình này cho tất cả, bởi vì nó khá mất thời gian. Vì vậy chúng ta có thể sử dụng nó khi chúng ta mới lập trình hoặc khi gặp một thuật toán đặc biệt khó thôi nhé!