Trong cuộc sống cũng như trong lĩnh vực tin học, luôn có những vấn đề hay bài toán mà chúng ta cần sự giải đáp. Có thể cho rằng, thuật toán chính là chìa khóa để giải quyết những bài toán đó. Bài viết này sẽ giúp chúng ta hiểu rõ thuật toán là gì và các vấn đề liên quan mà lập trình viên cần biết. Đừng bỏ qua phần nào sau đây nhé!
Tóm Tắt
I. Thuật toán – Algorithm là gì?
1. Thuật toán là gì?
Thuật toán là một phương thức gồm tập hợp các câu lệnh hay các bước được thực hiện theo một thứ tự nhất định nhằm giải quyết một vấn đề logic nào đó. Từ thuật toán còn được gọi là Algorithm, nó được đặt theo tên của một nhà toán học người Trung Á là al’Khwarizmi. Ông là tác giả của một cuốn sách về số học, trong đó ông đã dùng phương pháp mô tả rất rõ ràng và mạch lạc cách giải những bài toán. Sau này, phương pháp này đã được xem là một chuẩn mực và được nhiều nhà toán học khác áp dụng theo.
2. Thuật toán máy tính là gì?
Trong toán học và khoa học máy tính, thuật toán máy tính, hay còn gọi là giải thuật, là một tập hợp 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, nhằm giải quyết một lớp vấn đề hoặc để thực hiện một phép tính. Các thiết bị máy tính sử dụng thuật toán để thực hiện các chức năng của nó một cách rõ ràng như thực hiện các phép tính, suy luận tự động, xử lý dữ liệu, và các tác vụ khác.
Tìm việc làm, tuyển dụng IT có thể bạn quan tâm:
– Software Developer (ASP.Net MVC / DotNet / Java)
– Software Developer (ReactJs/ React Native)
3. Mối liên hệ giữa thuật toán và cấu trúc dữ liệu
Thuật toán là một tập hợp các bước để giải quyết một vấn đề cụ thể. Còn cấu trúc dữ liệu là một vị trí được đặt tên và có thể được sử dụng để lưu trữ, tổ chức dữ liệu. Thuật toán và cấu trúc dữ liệu cho phép chúng ta viết các chương trình máy tính một cách hiệu quả và tối ưu. Hai thành phần này hỗ trợ nhau, các thuật toán sẽ cần cấu trúc dữ liệu bên trong để làm cho chúng hoạt động theo đúng kỳ vọng. Ví dụ, nếu chúng ta cần sắp xếp một danh sách thì có thể sử dụng cấu trúc dữ liệu mảng để lưu trữ và dùng thuật toán để sắp xếp các phần tử trong danh sách đó theo mong muốn.
II. Tại sao cần dùng thuật toán?
Có thể nói rằng thuật toán được sử dụng trong hầu hết các phương tiện, thiết bị công nghệ, phần mềm mà bạn đang sử dụng hằng ngày. Cụ thể như các ứng dụng liên quan đến giao thông vận tải (Google maps, Grab, Baemin,…), trong các hệ thống mạng, viễn thông để định hướng đường truyền tín hiệu. Và một ứng dụng cũng rất quen thuộc đó chính là công cụ tìm kiếm Google, bằng cách sử dụng những thuật toán, nó sẽ đưa ra đúng thông tin mà bạn cần trong một lượng khổng lồ thông tin trên internet.
Bên cạnh đó, các thuật toán mã hoá được sử dụng để mã hoá thông tin, truyền nhận và lưu trữ giữ liệu, giúp bảo vệ thông tin cá nhân, tổ chức khỏi những cuộc tấn công hay khai thác. Qua đó, có thể thấy rằng thuật toán đóng vai trò quan trọng và không thể thiếu trong thời đại công nghệ ngày nay để giúp cuộc sống của chúng ta trở nên dễ dàng và năng suất hơn.
III. Các đặc trưng của thuật toán
1. Tính xác định
Tính “không mập mờ” và “có thể thực thi được” được gọi chung là tính xác định. Trong khoa học máy tính, thuật toán phải là một dãy hữu hạn các bước rõ ràng, không mập mờ và có thể thực thi được, theo đúng trình tự để ra được kết quả như ta mong muốn. Vì vậy, bất kỳ thuật toán nào cũng phải có những bước được xác định, theo một trình tự nhất định, được thiết lập ngay từ ban đầu.
2. Tính hữu hạn
Số bước hữu hạn của thuật toán và tính chất dừng của nó được gọi chung là tính hữu hạn. Số bước hữu hạn của thuật toán là một tính chất khá hiển nhiên. Tính “dừng” hay hữu hạn là tính chất rất dễ bị vi phạm vì sai sót khi trình bày thuật toán. Mọi thuật toán đều nhằm thực hiện một công việc nhất định và cho ra kết quả khi thực hiện xong. Nếu thuật toán không thỏa được tính hữu hạn thì ta nói rằng thuật toán bị lặp vô tận hoặc bị quẩn, không cho ra được kết quả cuối cùng.
3. Tính đúng
Khi giải một bài toán, tất nhiên chúng ta đều mong muốn đạt được kết quả đúng đắn. Và thuật toán được sinh ra chính là để tìm ra được kết quả đúng cho bài toán hay vấn đề cụ thể. Tuy nhiên tính “đúng” dù là một tính chất khá hiển nhiên nhưng cũng khó để đạt tới. Bởi vì trong thực tế, có những vấn đề mà chúng ta cần phải nghiên cứu và thử nghiệm nhiều lần mới tìm ra được thuật toán hoàn hảo nhất để đưa ra đúng kết quả.
4. Tính hiệu quả
Tính hiệu quả của thuật toán là một yếu tố được đánh giá để chọn lựa cách giải quyết cho vấn đề bài toán trên thực tế. Tính hiệu quả của thuật toán được đánh giá dựa trên các tiêu chuẩn như khối lượng tính toán, thời gian và không gian khi thi hành thuật toán. Ngoài ra, một tiêu chuẩn cũng được sử dụng nhiều để đánh giá tính hiệu quả của thuật toán đó là độ phức tạp và logic của thuật toán.
5. Tính tổng quát
Tính tổng quát của thuật toán nói đến việc thuật toán phải áp dụng được cho mọi trường hợp của bài toán chứ không chỉ áp dụng được cho một số trường hợp riêng biệt nào đó. Có thể hiểu rằng thuật toán phải giống như các công thức toán học, có thể áp dụng nhiều. Tuy nhiên trong thực tế, cũng có các thuật toán được xây dựng dành riêng cho một bài toán, một vấn đề. Vì vậy, không phải thuật toán nào cũng cần đảm bảo được tính tổng quát mà phải tùy vào trường hợp sử dụng.
IV. Làm thế nào để viết một thuật toán?
– Phân tích và phác thảo thuật toán: Bước đầu tiên, chúng ta cần phân tích rõ vấn đề, sau đó hình dung được hướng giải quyết và chiến thuật thiết kế thuật toán. Để hoàn thành được này, ta cần đến khá nhiều kiến thức căn bản của môn Cấu trúc dữ liệu và giải thuật, cụ thể, tiêu biểu là 5 chiến thuật thiết kế thuật toán sau: Chia để trị – divide and conquer, Giải thuật tham ăn – Greedy Method
Lập trình quy hoạch động – Dynamic Programming, Back Tracking và Branch and Bound. Trong đó, chiến thuật chia để trị là được sử dụng phổ biến nhất.
– Kiểm tra thuật toán: Sau khi thiết kế xong thuật toán, ta cần kiểm tra tính đúng đắn của nó bằng cách đưa thuật toán vào máy tính. Sau đó, nhập input, tức tài liệu nguồn vào ở định dạng tương thích. Bước kiểm tra này là để đảm bảo thuật toán sẽ hoạt động trơn tru trên mọi ngôn từ lập trình.
– Đánh giá thuật toán: Để biết được thuật toán có hiệu quả hay không thì chúng ta cần phải đánh giá nó. Ta có thể đánh giá hiệu năng thuật toán theo 2 yếu tố là thời hạn thực thi và bộ nhớ sử dụng. Vì trong quá trình chạy thuật toán thì CPU cần tiêu tốn thời gian quyết và xử lý để thực thi những phép toán, còn bộ nhớ sẽ là nơi chứa tài liệu và chương trình thực thi.
– Test chương trình thuật toán: Việc test chương trình được chia thành 2 giai đoạn là debugging và profiling. Debugging là quá trình thực thi chương trình dựa trên một tập dữ liệu mẫu để xác định các lỗi xảy ra (loại lỗi, vị trí lỗi,…) và khắc phục chúng. Tuy nhiên giai đoạn này hầu như không bao giờ phát hiện được 100% lỗi. Profiling cũng là quá trình thực thi chương trình trên một tập dữ liệu mẫu nhưng trong giai đoạn này, người ta sẽ đo thời gian cũng như dung lượng bộ nhớ.
– Hoàn thiện thuật toán và ứng dụng: Sau khi đã hoàn tất các bước trên thì ta sẽ một lần nữa kiểm thử lại, đảm bảo thuật toán không còn lỗi hay sai sót nào. Và cuối cùng là sử dụng thuật toán để giải quyết vấn đề hay bài toán mà bạn hay công ty đang gặp phải.
V. Phương pháp biểu diễn thuật toán
1. Ngôn ngữ tự nhiên
Dùng ngôn ngữ tự nhiên là phương pháp biểu diễn thuật toán bằng cách mô tả các bước thực thi theo ngôn ngữ thường ngày. Phương pháp này không đòi hỏi người viết và người đọc thuật toán phải nắm các nguyên tắc. Tuy nhiên nó khiến cho việc biểu diễn thuật toán trở nên dài dòng, không trực quan, không thể hiện được cấu trúc thuật toán nên có thể gây khó hiểu hoặc hiểu lầm. Vì không có nguyên tắc nào cho phương pháp này nên nếu sử dụng thì bạn nên phân cấp từng bước theo số thứ tự một cách dễ hiểu nhất.
2. Lưu đồ – sơ đồ khối
– Thao tác chọn lựa (decision): Thao tác chọn lựa được biểu diễn bằng một hình thoi, ở trong chứa biểu thức điều kiện.
– Thao tác xử lý (process): Thao tác xử lý được biểu diễn bằng một hình chữ nhật, ở trong chứa nội dung xử lý.
– Ðường đi (route): Để thể hiện trình tự thực hiện các thao tác, người ta sử dụng đường cung nối các bước kế tiếp nhau. Trên đường cung có mũi tên để chỉ hướng hay thứ tự thực hiện.
– Ðiểm cuối (terminator): Ðiểm cuối là điểm khởi đầu và cũng là điểm kết thúc của thuật toán, nó được biểu diễn bằng hình ovan, bên trong có ghi chữ start/begin/bắt đầu hoặc end/kết thúc. Nếu là điểm khởi đầu thì điểm cuối chỉ có cung đi ra còn là điểm kết thúc thì có cung đi vào.
– Ðiểm nối (connector): Ðiểm nối dùng để nối các phần khác nhau của một lưu đồ. Bên trong điểm nối, người ta đặt một ký hiệu để biết sự liên hệ giữa các điểm nối đó.
– Ðiểm nối sang trang (off-page connector): Điểm nối sang trang cũng giống như điểm nối nhưng nó được dùng khi lưu đồ quá lớn, phải vẽ trên nhiều trang. Bên trong điểm nối sang trang, người ta cũng đặt một ký hiệu để biết được sự liên hệ giữa điểm nối của các trang.
3. Mã giả
Phương pháp biểu diễn thuật toán thứ ba chính là mã giả. Khi sử dụng phương pháp này để biểu diễn thuật toán, ta cần vay mượn các cú pháp của một ngôn ngữ lập trình nào đó và vẫn sử dụng một phần ngôn ngữ tự nhiên. Tất nhiên, mọi ngôn ngữ lập trình đều có những thao tác cơ bản là xử lý, rẽ nhánh và lặp. Phương pháp dùng mã giả để biểu diễn thuật toán vừa tận dụng được các khái niệm trong ngôn ngữ lập trình, vừa giúp người cài đặt dễ dàng nắm bắt nội dung thuật toán.
VI. Lập trình viên không học thuật toán được không?
Có một sự thật là lập trình viên nếu không học thuật toán thì vẫn có thể lập trình được. Tuy nhiên, nó chỉ dừng lại ở mức “được” mà thôi. Nếu các bạn không phải làm những bài toán có độ phức tạp cao, có dữ liệu người dùng lớn, cần có đáp án nhanh và chính xác cao thì bạn vẫn có thể giải quyết được vấn đề. Tuy nhiên, nếu bạn phải giải quyết một bài toán khó, cần sự chính xác thì cần phải học thuật toán. Bên cạnh đó, nếu muốn trở thành lập trình viên giỏi, nổi bật hơn so với những người khác thì bạn cần đầu tư cho việc học thuật toán càng sớm càng tốt. Điều đó sẽ giúp cho bạn có nhiều cơ hội hơn trong con đường phát triển sự nghiệp.
Có kiến thức tốt về thuật toán sẽ giúp bạn rất nhiều trong việc lựa chọn cấu trúc dữ liệu phù hợp. Sau đây là 25 thuật toán hàng đầu mà mọi lập trình viên nên biết: Thuật toán tìm kiếm nhị phân, Thuật toán tìm kiếm đầu tiên theo chiều rộng (BFS),Thuật toán Kadane, Thuật toán Lee, Thuật toán lấp đầy lũ, Thuật toán phát hiện chu kỳ của Floyd, Thuật toán tìm Union, Thuật toán sắp xếp tôpô, Thuật toán KMP, Thuật toán sắp xếp chèn, Thuật toán tìm kiếm đầu tiên theo chiều sâu (DFS), Thuật toán Sắp xếp Hợp nhất, Thuật toán Quicksort, Thuật toán Kruskal, Thuật toán Floyd Warshall Thuật toán Dijkstra, Thuật toán Bellman Ford, Thuật toán sắp xếp lựa chọn, Thuật toán sắp xếp đếm, Thuật toán sắp xếp đống, Thuật toán Kahn’s Topological Sort, Thuật toán nén mã hóa Huffman, Thuật toán chọn nhanh, Thuật toán bỏ phiếu cho đa số Boyer – Moore và Thuật toán Euclid
Xem thêm:
– Data Analyst là gì? Yếu tố cần để trở thành một Data Analyst giỏi
– Big Data là gì? Đặc điểm, vai trò và ứng dụng Big Data hiện nay
– BackEnd là gì? Sự khác nhau giữa FrontEnd và BackEnd
Hy vọng rằng, qua bài viết này bạn đã có cái nhìn rõ ràng hơn về thuật toán để áp dụng trong công việc của mình. Nếu thấy bài viết này hay và có ích thì đừng quên chia sẻ hoặc bình luận bên dưới nhé!
Nguồn tham khảo: https://vi.wikipedia.org/wiki/Thuật_toán
