Thuật toán

Thuật toán là một tập các hướng dẫn nhằm thực hiện một công việc nào đó. Ðối với việc giải quyết một vấn đề - bài toán thì thuật toán có thể hiểu là một tập hữu hạn các hướng dẫn rõ ràng để người giải toán có thể theo đó mà giải quyết được vấn đề.

Thuật toán là gì

Thuật toán là một khái niệm cơ sở của Toán học và Tin học. Hiểu một cách đơn giản, thuật toán là một tập các hướng dẫn nhằm thực hiện một công việc nào đó. Ðối với việc giải quyết một vấn đề - bài toán thì thuật toán có thể hiểu là một tập hữu hạn các hướng dẫn rõ ràng để người giải toán có thể theo đó mà giải quyết được vấn đề. Như vậy, thuật toán là một phương pháp thể hiện lời giải của vấn đề - bài toán.

ML-06.png

Tại sao lại là "Thuật toán"?

Từ thuật toán (Algorithm) xuất phát từ tên một nhà toán học người Trung Á là Abu Abd - Allah ibn Musa al’Khwarizmi, thường gọi là al’Khwarizmi. Ông là tác giả 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, mạch lạc cách giải những bài toán. Sau này, phương pháp mô tả cách giải toán của ông đã được xem là một chuẩn mực và được nhiều nhà toán học khác tuân theo. Từ algorithm ra đời dựa theo cách phiên âm tên của ông.

Các đặc trưng của thuật toán

1. Tính xác định

Việc nghiên cứu về thuật toán có vai trò rất quan trọng trong khoa học máy tính vì máy tính chỉ giải quyết được vấn đề khi đã có hướng dẫn giải rõ ràng và đúng. Nếu hướng dẫn giải sai hoặc không rõ ràng thì máy tính không thể giải đúng được bài toán. Trong khoa học máy tính, thuật toán được định nghĩa là một dãy hữu hạn các bước không mập mờ có thể thực thi được, quá trình hành động theo các bước này phải dừng và cho được kết quả như mong muố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. Ta có thể tìm ở đâu một lời giải vấn đề - bài toán có vô số bước giải ? Tính "không mập mờ" "có thể thực thi được" gọi chung là tính xác định.

Tính "thực thi được" cũng là một tính chất khá hiển nhiên. Rõ ràng nếu trong "thuật toán" tồn tại một bước không thể thực thi được thì làm sao ta có được kết quả đúng như ý muốn? Tuy nhiên, cần phải hiểu là "thực thi được" xét trong điều kiện hiện tại của bài toán. Chẳng hạn, khi nói "lấy căn bậc hai của một số âm" là không thể thực thi được nếu miền xác định của bài toán là số thực, nhưng trong miền số phức thì thao tác "lấy căn bậc hai của một số âm" là hoàn toàn thực thi được. Tương tự, nếu ta chỉ đường cho một người đi xe máy đến một bưu điện nhưng con đường ta chỉ là đường cụt, đường cấm hoặc đường ngược chiều thì người đi không thể đi đến bưu điện được.

2. Tính hữu hạn

Tính "dừng" hay hữu hạn là tính chất dễ bị vi phạm nhất, thường là do sai sót khi trình bày thuật toán. Dĩ nhiên, mọi thuật toán đều nhằm thực hiện một công việc nào đó nên sau một thời gian thi hành hữu hạn thì thuật toán phải cho chúng ta kết quả mong muốn. Khi không thỏa tính chất này, ta nói rằng "thuật toán" bị lặp vô tận hoặc bị quẩn. Ðể tính tổng các số nguyên dương lẻ trong khoảng từ 1 đến n ta có thuật toán sau :

B1. Hỏi giá trị của n.
B2. S = 0
B3. i = 1
B4. Nếu i = n+1 thì sang bước B8, ngược lại sang bước B5
B5. Cộng thêm i vào S
B6. Cộng thêm 2 vào i
B7. Quay lại bước B4.
B8. Tổng cần tìm chính là S.

Ta chú ý đến bước B4. Ở đây ta muốn kết thúc thuật toán khi giá trị của i vượt quá n. Thay vì viết là "nếu i lớn hơn n" thì ta thay bằng điều kiện "nếu i bằng n+1" vì theo toán học "i = n+1" thì suy ra "i lớn hơn n". Nhưng điều kiện "i=n+1" không phải lúc nào cũng đạt được. Vì ban đầu i = 1 là số lẻ, sau mỗi bước, i được tăng thêm 2 nên i luôn là số lẻ. Nếu n là số chẵn thì n+1 là một số lẻ nên sau một số bước nhất định, i sẽ bằng n+1. Tuy nhiên, nếu n là một số lẻ thì n+1 là một số chẵn, do i là số lẻ nên dù có qua bao nhiêu bước đi chăng nữa, i vẫn khác n+1. Trong trường hợp đó, thuật toán trên sẽ bị quẩn.

3. Tính đúng

Tính "đúng" là một tính chất khá hiển nhiên nhưng là tính chất khó đạt tới nhất. Thực vậy, khi giải quyết một vấn đề-bài toán, ta luôn luôn mong muốn lời giải của mình sẽ cho kết quả đúng nhưng không phải lúc nào cũng đạt được. Mọi học sinh khi làm bài kiểm tra đều muốn bài làm của mình có đáp số đúng nhưng trên thực tế, trong lớp học chỉ có một số học sinh nhất định là có khả năng đưa ra lời giải đúng!

4. Tính hiệu quả

Tính hiệu quả của thuật toán được đánh giá dựa trên một số tiêu chuẩn như khối lượng tính toán, không gian và thời gian khi thuật toán được thi hành. Tính hiệu quả của thuật toán là một yếu tố quyết định để đánh giá, chọn lựa cách giải quyết vấn đề-bài toán trên thực tế. Có rất nhiều phương pháp để đánh giá tính hiệu quả của thuật toán. Trong mục 3 của chương , ta sẽ tìm hiểu một tiêu chuẩn được dùng rộng rãi là độ phức tạp của thuật toán.

5. Tính tổng quát

Thuật toán có tính tổng quát là 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 phải chỉ áp dụng được cho một số trường hợp riêng lẻ nào đó. Chẳng hạn giải phương trình bậc hai sau đây bằng Delta đảm bảo được tính chất này vì nó luôn giải được với mọi giá trị số thực a,b,c bất kỳ. Tuy nhiên, không phải thuật toán nào cũng đảm bảo được tính tổng quát. Trong thực tế, có lúc người ta chỉ xây dựng thuật toán cho một dạng đặc trưng của bài toán mà thôi.

Các thuật toán cơ bản

Thuật toán

Trong khoa học máy tính, thuật toán là một tập hợp các hướng dẫn hoặc quy trình được sử dụng để giải quyết một vấn đề tính toán. Dưới đây là một số thuật toán cơ bản:

  1. Thuật toán sắp xếp: Là thuật toán sắp xếp các phần tử trong một danh sách hoặc mảng theo một thứ tự nhất định, ví dụ như sắp xếp theo thứ tự tăng dần hoặc giảm dần.
  2. Thuật toán tìm kiếm: Là thuật toán tìm kiếm một phần tử hoặc một tập hợp các phần tử trong một danh sách hoặc mảng.
  3. Thuật toán đệ quy: Là thuật toán sử dụng một hàm để gọi lại chính nó để giải quyết một vấn đề.
  4. Thuật toán cây: Là thuật toán sử dụng cấu trúc dữ liệu cây để giải quyết một vấn đề.
  5. Thuật toán đồ thị: Là thuật toán sử dụng cấu trúc dữ liệu đồ thị để giải quyết một vấn đề.

ML-06.png

Các thuật toán này là những thuật toán cơ bản và được sử dụng rộng rãi trong lĩnh vực khoa học máy tính. Việc hiểu và biết cách sử dụng chúng sẽ giúp ích rất nhiều trong quá trình giải quyết các vấn đề tính toán.

Các thuật toán sắp xếp
  1. Sắp xếp nổi bọt (Bubble sort): Sắp xếp bằng cách so sánh hai phần tử liền kề và đổi chỗ chúng nếu chúng không đúng thứ tự.
  2. Sắp xếp chọn (Selection sort): Sắp xếp bằng cách lựa chọn phần tử nhỏ nhất và đưa nó về đầu danh sách, tiếp tục với danh sách còn lại.
  3. Sắp xếp chèn (Insertion sort): Sắp xếp bằng cách chèn mỗi phần tử vào vị trí đúng của nó trong danh sách đã sắp xếp trước đó.
  4. Sắp xếp nhanh (Quick sort): Sắp xếp bằng cách chọn một phần tử làm chốt, chia danh sách thành hai phần dựa trên phần tử chốt đó, và tiếp tục sắp xếp các phần tử con.
  5. Sắp xếp trộn (Merge sort): Sắp xếp bằng cách chia danh sách thành nhiều phần, sắp xếp từng phần, sau đó trộn các phần đã sắp xếp lại với nhau.
Các thuật toán tìm kiếm
  1. Tìm kiếm tuyến tính (Linear search): Tìm kiếm bằng cách so sánh từng phần tử trong danh sách với giá trị cần tìm kiếm.
  2. Tìm kiếm nhị phân (Binary search): Tìm kiếm bằng cách chia đôi danh sách và so sánh giá trị cần tìm kiếm với giá trị ở giữa danh sách đã chia đôi.
Các thuật toán đệ quy
  1. Thuật toán đệ quy tuyến tính (Linear recursive algorithm): Giải quyết bài toán bằng cách giải bài toán con của nó và trở về bài toán ban đầu.
  2. Thuật toán đệ quy nhị phân (Binary recursive algorithm): Giải quyết bài toán bằng cách chia đôi bài toán thành những bài toán con nhỏ hơn và giải quyết chúng.
Các thuật toán cây
  1. Cây nhị phân tìm kiếm (Binary search tree): Một cây nhị phân tìm kiếm là một cây nhị phân mà ở mỗi nút, các nút con bên trái có giá trị nhỏ hơn nút hiện tại và các nút con bên phải có giá trị lớn hơn nút hiện tại.
  2. Cây đỏ đen (Red-black tree): Một cây đỏ đen là một cây nhị phân tìm kiếm được cân bằng với một số quy tắc đặc biệt, điều này đảm bảo rằng thời gian truy cập và thêm, xóa các phần tử là O(log n).
  3. Cây AVL (AVL tree): Một cây AVL là một cây nhị phân tìm kiếm được cân bằng với một số quy tắc đặc biệt, điều này đảm bảo rằng thời gian truy cập và thêm, xóa các phần tử là O(log n).
Các thuật toán đồ thị
  1. Thuật toán Dijkstra: Tìm đường đi ngắn nhất trong đồ thị có trọng số không âm.
  2. Thuật toán Bellman-Ford: Tìm đường đi ngắn nhất trong đồ thị có thể có trọng số âm.
  3. Thuật toán Floyd-Warshall: Tìm đường đi ngắn nhất giữa tất cả các cặp đỉnh trong đồ thị có trọng số.
  4. Thuật toán Prim: Tìm cây khung nhỏ nhất trong đồ thị có trọng số.
  5. Thuật toán Kruskal: Tìm cây khung nhỏ nhất trong đồ thị có trọng số.

Thuật giải Heuristic

Trong quá trình nghiên cứu giải quyết các vấn đề – bài toán, người ta đã đưa ra những nhận xét như sau: