Công nghệ sử dụng các thuật toán được thực hiện bằng máy tính

Trong những năm gần đây, nhu cầu tuyển dụng ngành lập trình nhiều nên rất nhiều bạn theo học ngành công nghệ thông và cũng rất nhiều bạn từ ngành khác chuyển sang. Do thời gian học ngắn hoặc thiếu tập trung trong quá trình học, các bạn gặp rất nhiều khó khăn khi đi phỏng vấn, nhất là phỏng vấn với thuật toán.

Trong chuỗi bài viết này, mình sẽ trình bày một cách rất cơ bản về thuật toán và những thuật toán thường gặp để giúp các bạn dễ hiểu, dễ áp dụng và tự tin trong quá trình tham gia phỏng vấn tìm việc cũng như tạo nền tảng cho quá trình học lập trình.

Thuật toán là gì?

Thuật toán/Thuật giải/Giải thuật/Algorithm nói chung đó là cách giải một bài toán bằng chương trình máy tính. Kỹ năng về thuật toán là nền tảng trong lập trình nên các lập trình viên phải nắm vững phần này thì mới làm việc tốt được.

Ví dụ: Để giải một phương trình bật nhất ax+b =0. Cần các bước:

Khai báo các biến a, b và x

Nhập hai tham số a và b

Kiểm tra a:

    Nếu a =0

      Kiểm tra b

         Nếu b= 0 thì in ra phương trình có vô số nghiệm

         Nếu b<>0 thì in ra phương trình vô nghiệm

    Nếu a<>0

       In ra phương trình có một nghiệm x=-b/a

Cái trên gọi là thuật toán để giải phương trình bậc nhất ax+b=0

Cách biểu diễn thuật toán

Đôi khi bạn biết cách giải nhưng lại không nắm được cách trình bày cũng là một vấn đề khác bạn phải đối mặt. Có 03 cách cơ bản để biểu diễn thuật toán:

• • – Sử dụng ngôn ngữ giả (Pseudo Code)
  • – Sử dụng sơ đồ khối (Flow Chart)
  • – Sử dụng code của một ngôn ngữ lập trình nào đó.

1. Ngôn ngữ giả (Pseudo Code)

Ngôn ngữ giả, ở đây có nghĩa là không phải ngôn ngữ lập trình, bạn có thể sử dụng ngôn ngữ tiếng Anh hoặc tiếng Việt để biểu diễn thuật toán. Ví dụ ở trên tôi sử dụng tiếng Việt để biểu diễn thuật toán giải phương trình bậc nhất ax + b =0 . Ở các bài tiếp theo chúng ta sử dụng thường xuyên ngôn ngữ giả để biểu diễn thuật toán.

2. Sơ đồ khối (Flowchart)

Sơ đồ khối sử dụng các ký hiệu để biểu diễn các khối lệnh trong thuật toán.

a. Bảng ký hiệu của sơ đồ khối

b. Khối lệnh điều khiển (if)

c. Khối lệnh điều khiển (if..else)

d. Khối lệnh lặp 

e. Ví dụ: Sử dụng sơ đồ khối để biểu diễn thuật giải để giải bài toán ax+b=0 ở trên.

3. Code

Bạn có thể sử dụng ngôn ngữ lập trình mình đã học để biểu diễn thuật toán.

Ví dụ: Sử dụng ngôn ngữ lập trình Java để biểu diễn thuật toán giải phương trình ax+b=0 ở trên.

package firstdegreeequation;

import java.util.Scanner;

public class FirstDegreeEquation {

public static void main(String[] args) {
   System.out.println("Giai phuong trinh bac nhat ax + b =0");
   int a, b;
   double x;
   Scanner sc= new Scanner(System.in);
   System.out.print("Nhap bien so a:");
   a= sc.nextInt();
   System.out.print("Nhap bien so b:");
   b= sc.nextInt();

   if(a==0)
      if(b==0)
         System.out.println("Phuong trinh co vo so nghiem");
      else
         System.out.println("Phuong trinh vo nghiem");
   else{
       x=(double)-b/a;
       System.out.println("Phuong trinh co nghiem x=" + x);
   }
}

}

Việc nắm rõ cách biểu diễn thuật toán ngoài việc giúp bạn biểu diễn thuật toán bạn muốn viết ra, nó còn giúp bạn đọc, hiểu các thuật toán do người khác viết hoặc đọc các đề thi tuyển.

Cách giải quyết một bài toán liên quan đến thuật toán

Có thể tóm tắt các bước để giải một bài toán liên quan đến thuật toán như sau:

1. – Tìm hiểu kỹ về yêu cầu
2. – Tìm ra cách giải
3. – Phân ra từng bước thực hiện
4. – Biểu diễn

a. Tìm hiểu kỹ về yêu cầu

Đây làm bước đọc đề, bạn cần đọc kỹ để nắm bắt được yêu cầu và đảm bảo hiểu được yêu cầu.

b. Tìm ra cách giải

Bước này khó nhất, tùy thuật vào kỹ năng tư duy và kinh nghiệm của bạn. Phần lớn phụ thuộc nhiều và khả năng làm toán của bạn. Tuy nhiên, nếu bạn chịu khó đọc kỹ các bài toán liên quan hoặc lập trình nhiều kỹ năng này cũng tăng lên.

c. Phân ra từng bước thực hiện

Lập trình là quá trình chia nhỏ các bước thực hiện của một thuật toán đến mức có thể viết thành các lệnh trong ngôn ngữ lập trình. Nên bạn cần chia nhỏ các bước thực hiện của thuật giải ra thành từng bước nhỏ nhất có thể biểu diễn.

d. Biểu diễn

Tùy theo nhu cầu mà bạn có thể biểu diễn thuật toán theo các hình thức đã nêu ở trên.

Thuật toán và cấu trúc dữ liệu

Mỗi kiểu dữ liệu sẽ định hình trên đó các bài toán cơ bản và thuật giải trên đó. Do vậy, khi nói về thuật toán chúng ta thường phải đi kèm với cấu trúc dữ liệu. Trong các bài tiếp theo chúng ta sẽ làm quen với các thuật toán thông dụng trên các kiểu dữ liệu thường gặp như:

Trên đây là những nội dung cơ bản về thuật toán, hy vọng giúp bạn dễ dàng hơn trong việc học hoặc ôn tập về thuật toán.

Bài tiếp: Các thuật toán về số học

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é!

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 (database), và các tác vụ khác.

Tìm việc làm, tuyển dụng software developer có thể bạn quan tâm:

- Software Developer (ASP.Net MVC / DotNet / Java)

- Software Developer (ReactJs/ React Native)

- Tuyển dụng lập trình viên

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 rên laptop 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 mật 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 kỹ thuật phần mềm, 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 thực hiện bởi các Tester sẽ 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

Hiện nay, có rất nhiều các phần mềm vẽ lưu đồ nhanh và tốt nên sẽ thuận tiện cho việc biểu diễn thuật toán. Bên cạnh đó, bạn nên áp dụng theo các thao tác sau đây để có một lưu đồ hoàn chỉnh nhất.

- 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): Ðifể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 các loại 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 đó, tố chất để trở thành một lập trình viên thành công là 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 việc làm ngành IT.

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:

- Cách viết CV xin việc ngành IT, CNTT đơn giản mà chuẩn nhất

- ICT là gì? Ứng dụng trong ngành IT và mọi lĩnh vực đời sống

- Tuyển tập bài test và bộ câu hỏi phỏng vấn IT thường gặp

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