Thuật toán là một khái niệm cơ bản của Toán học và Tin học. Khi viết một chương trình máy tính, người ta thường cài đặt một phương pháp đã được nghĩ ra trước đó để giải quyết một vấn đề. Từ "thuật toán" được dùng trong khoa học máy tính để để chỉ sự mô tả một phương pháp giải bài toán thích hợp cho việc cài đặt thành các chương trình nhờ các ngôn ngữ lập trình. Một thuật toán thường được thể hiện bởi một thủ tục gồm một dãy hữu hạn bước mà theo đó ta sẽ đạt đến lời giải cho bài toán. Người ta có thể trình bày thuật toán bằng cách liệt kê ra các bước của thuật toán sử dụng ngôn ngữ tự nhiên hay một ngôn ngữ qui ước nào đó chẳng hạn sử dụng một ngôn ngữ lập trình nào đó gần với ngôn ngữ tự nhiên.
Ví dụ 1: thuật toán tìm phần tử lớn nhất trong một dãy hữu hạn các số nguyên.
Bài toán tìm phần tử lớn nhất trong một dãy hữu hạn tương đối tầm thường. Tuy nhiên đây là một trong những ví dụ khá tốt để minh họa cho khái niệm về thuật toán. Có nhiều vấn đề mà trong đó đòi hỏi phải tìm số nguyên lớn nhất trong một dãy số. Chẳng hạn như việc tìm ra một học sinh có điểm cao nhất trong một kỳ thi, hay tìm ra một nhân viên có năng suất cao nhất trong một xí nghiệp, v.v....
Chúng ta có nhiều cách để giải bài toán này. Một trong những phương pháp để tìm phần tử lớn nhất trong một dãy số nguyên là thực hiện một thủ tục theo các bước sau đây:
1. Trước hết ta đặt cho giá trị lớn nhất tạm thời bằng số nguyên đầu tiên. (Giá trị lớn nhất tạm thời này chính là giá trị lớn nhất ở mỗi giai đoạn của thủ tục.)
2. So sánh số nguyên kế tiếp trong dãy với giá trị lớn nhất tạm thời, và nếu nó lớn hơn giá trị lớn nhất tạm thời thì đặt cho giá trị lớn nhất tạm thời bằng số nguyên này.
3. Lặp lại bước 2 nếu còn số nguyên trong dãy chưa được xét tới.
4. Dừng nếu không còn số nguyên nào trong dãy chưa được xét. Giá trị lớn nhất tạm thời lúc này chính là giá trị lớn nhất trong dãy số.
Ví dụ 2: Thuật toán tính nghiệm của phương trình bậc hai: ax2 + bx + c = 0 khi biết 3 hệ số a, b, c (a # 0).
Bước 1: Tính giá trị D theo công thức
D = b2 - 4ac
Bước 2: Xét dấu D , ta có kết quả tùy thuộc một trong 3 trường hợp sau đây:
Trường hợp D > 0: Phương trình có 2 nghiệm được tính theo công thức
x =
Trường hợp D = 0: Phương trình có nghiệm kép được tính theo công thức
Ngôn ngữ lưu đồ hay sơ đồ khối là một công cụ rất trực quan để diễn đạt các thuật toán. Biểu diễn bằng lưu đồ sẽ giúp ta có được một cái nhìn tổng quan về toàn cảnh của quá trình xử lý theo thuật toán.
Lưu đồ là một hệ thống các nút có hình dạng khác nhau, thể hiện các chức năng khác nhau và được nối với nhau bởi các cung. Lưu đồ được tạo thành bởi 4 thành phần chủ yếu sau đây:
1/ Nút giới hạn: được biểu diễn bởi hình ôvan có ghi chữ bên trong như :
Các nút trên còn được gọi là nút đầu và nút cuối của lưu đồ.
2/ Nút thao tác: là một hình chữ nhật có ghi các lệnh cần thực hiện. Ví dụ:
3/ Nút điều kiện: thường là một hình thoi có ghi điều kiện cần kiểm tra. Trong các cung nối với nút này có 2 cung ra chỉ hướng đi theo 2 trường hợp: điều kiện đúng và điều kiện sai. Ví dụ:
4/ Cung: là các đường nối từ nút này đến nút khác của lưu đồ.
Hoạt động của thuật toán theo lưu đồ được bắt đầu từ nút đầu tiên. Sau khi thực hiện các thao tác hoặc kiểm tra điều kiện ở mỗi nút thì bộ xử lý sẽ theo một cung để đến nút khác. Quá trình thực hiện thuật toán dừng khi gặp nút kết thúc hay nút cuối.
Trong bài này chúng ta chủ yếu là sử dụng ngôn ngữ tự nhiên và mã giả để trình bày thuật toán. Trong cách sử dụng ngôn ngữ tự nhiên ta sẽ liệt kê các bước thực hiện các thao tác hay công việc nào đó của thuật toán bằng ngôn ngữ mà con người sử dụng một cách phổ thông hàng ngày. Các thuật toán được trình bày trong hai ví dụ trên chính là cách biểu diễn thuật toán dùng ngôn ngữ tự nhiên. Mặc dù cách biểu diễn này khá tự nhiên và không đòi hỏi người viết thuật toán phải biết nhiều quy ước khác, nhưng nó không thể hiện rõ tính cấu trúc của thuật toán nên không thuận lợi cho việc thiết kế và cài đặt những thuật toán phức tạp. Hơn nữa trong nhiều trường hợp việc biểu diễn thuật toán bằng ngôn ngữ tự nhiên tỏ ra dài dòng và dẽ gây ra sự nhầm lẫn đối với người đọc. Còn việc sử dụng lưu đồ sẽ rất cồng kềnh đối với các thuật toán phức tạp => chúng ta cần chọn phương thức thích hợp để biểu diễn thuật toán.
Ðể biểu diễn thuật toán một cách hiệu quả, người ta thường dùng mã giả (pseudocode). Theo cách này, ta sẽ sử dụng một số qui ước của một ngôn ngữ lập trình, chẳng hạn là ngôn ngữ lập trình PASCAL, nhất là các cấu trúc điều khiển của ngôn ngữ lập trình như các cấu trúc chọn, các cấu trúc lặp.
Trong mã giả ta còn sử dụng cả các ký hiệu toán học, các biến, và đôi khi cả cấu trúc kiểu thủ tục. Cấu trúc thuật toán kiểu thủ tục thường được sử dụng để trình bày các thuật toán đệ qui hay các thuật toán quá phức tạp cần phải được trình bày thành nhiều cấp độ.
Cùng với việc sử dụng các biến, trong thuật toán rất thường gặp một phát biểu hành động đặt (hay gán) một giá trị cho một biến. Ví du:?hành động tăng biến i lên 1 đơn vị có thể được viết như sau:
i := i + 1
hay
i ? i + 1 (ít dùng)
Các cấu thường được sử dụng trong mã giả dựa theo ngôn ngữ lập trình PASCAL gồm:
1/ Cấu trúc chọn:
if (điều kiện) then (hành động)
if (điều kiện) then (hành động)
else (hành động)
2/ Cấu trúc lặp:
while (điều kiện) do (hành động)
Repeat
(hành động)
Until (điều kiện)
for (biến đếm) := (giá trị đầu) to (giá trị cuối) do (hành động)
for (biến đếm) := (giá trị cuối) downto (giá trị đầu) do (hành động)
3/ Cấu trúc nhảy goto. Ngoài ra người ta còn sử dụng lệnh ngắt vòng lặp break.
Dưới đây là các thuật toán được biểu diễn bằng mã giả (sử dụng các cấu trúc điều khiển của ngôn ngữ lập trình PASCAL). Trước khi viết các bước thực hiện thuật toán ta thường ghi rõ những gì được cho trước (phần nhập) và kết quả cần đạt được (phần xuất).
Thuật toán tìm phần tử lớn nhất trong một dãy hữu hạn các số nguyên:
Nhập: dãy số a1, a2, . . ., an
Xuất: max là giá trị lớn nhất trong dãy số đã cho trong input.
Thuật toán:
1. max := a1
2. for i := 2 to n do
if max < a1 then max := a1
3. max là giá trị lớn nhất trong dãy số.
Thuật toán giải phương trình bậc hai ax2 + bx + c = 0 (a ≠ 0):
Nhập : 3 hệ số a, b, c
Ðiều kiện : a ≠ 0
Xuất : nghiệm của phương trình
Thuật toán:
1. delta := b2 - 4*a*c
2. if delta > 0 then
begin
x1 := (-b - sqrt(delta)) / (2*a);
x2 := (-b+sqrt(delta)) / (2*a);
Xuất kết quả: phương trình có hai nghiệm là x1 và x2;
end
3. esle if delta = 0 then
Xuất kết quả: phương trình có nghiệm kép là -b / (2*a)
4. else { trường hợp delta < 0}
Xuất kết quả: phương trình vô nghiệm;
(Trong thuật toán này, ký hiệu sqrt(delta) dùng để chỉ căn bậc hai dương của delta)
Thuật toán có vai trò rất quan trọng trong khoa học máy tính. Ðể có thể lập trình giải bài toán trên máy tính, ta cần có một thuật toán bảo đảm những tính chất nhất định. Khi mô tả một thuật toán chúng ta cần chú ý đến các tính chất sau đây:
Nhập (input): Các thuật giải có các giá trị đầu vào (input values) từ một tập hợp nhất định nào đó.
Xuất (output): Từ mỗi tập hợp các giá trị được nhập một thuật toán thường tạo ra những giá trị kết quả (output values) thuộc một tập hợp nhất định nào đó thể hiện lời giải cho bài toán.
Tính xác định (definiteness): Các bước trong thuật toán phải chính xác rõ ràng.
Tính hữu hạn (finiteness): Thuật toán phải cho ra lời giải (hay kết quả) sau một số hữu hạn bước.
Tính hiệu quả (về thời gian): Thuật toán cần phải được thực hiện một cách chính xác và trong một khoảng thời gian cho phép.
Tính tổng quát. Thuật toán phải áp dụng được cho tất cả các bài toán có dạng như mong muốn, chứ không phải chỉ áp dụng được cho một số trường hợp đặc biệt nào đó.
Tính đúng: Thuật toán phải cho kết quả như mong muốn.
Trong các tính chất trên, 3 tính chất cơ bản của thuật toán đòi hỏi phải được thỏa mãn là tính xác định, tính hữu hạn và tính đúng.
Các thuật toán trong hai ví dụ 1 và 2 được trình bày ở trên đều thỏa mãn các tính chất nêu trên.
Dưới đây chúng ta xét thêm một số ví dụ về các thuật toán.
Ví dụ 3: Thuật toán tìm kiếm tuyến tính (Linear Search)
Bài toán được đặt ra là xác định xem một phần tử x có trong một dãy a1, a2, . . ., an hay không? Lời giải của bài toán này là giá trị chỉ vị trí (hay chỉ số) của một phần tử trong dãy bằng phần tử x, hoặc là 0 nếu x không có trong dãy.
Một thuật toán đơn giản để giải bài toán này là thuật toán tìm kiếm tuyến tính (hay còn gọi là tìm kiếm tuần tự). Thuật toán bắt đầu bằng việc so sánh x với a1, và nếu x = a1 thì lời giải là vị trí của a1(tức là 1). Khi x ≠ a1, ta tiếp tục so sánh x với a2. Nếu x = a2, thì lời giải là vị trí của a2(tức là 2). Khi x ≠ a2, ta tiếp tục so sánh x với a3. Cứ tiếp tục quá trình này: lần lượt so sánh x với từng phần tử của dãy cho tới khi gặp một phần tử bằng x hoặc là cho tới khi đạt đến cuối dãy. Lời giải là vị trí của phần tử trong dãy bằng x; hoặc là 0 nếu không có phần tử nào trong dãy bằng x. Thuật toán này có thể được viết dưới dạng mã giả như dưới đây.
Thuật toán: Tìm kiếm tuyến tính (hay tuần tự)
Nhập : dãy a1, a2, . . ., an, và phần tử x.
Xuất : vị trí của x trong dãy (chỉ số của phần tử trong dãy bằng với x), hoặc 0
Thuật toán:
1. i := 1
2. while ( i ≤ n and x ≠ ai ) do
i := i + 1;
3. if i ≤ n then location := i
else location := 0
4. location là một lời giải (ví trí cần tìm).
Trong thuật toán nầy từ "location" là một biến nguyên.
Ghi chú : Trong trường hợp dãy a1, a2, . . ., an có thứ tự thì ta có thể tìm kiếm theo thuật toán tìm kiếm nhị phân (binary search). Ta có thể tham khảo thuật toán này trong các sách về "cấu trúc dữ liệu và thuật toán".
Ví dụ 4:
Thuật toán kiểm tra tính đối xứng của một ma trận.
Nhập : ma trận M cấp n.
Xuất : Yes nếu ma trận M là ma trận đối xứng.
No nếu M không đối xứng.
Thuật toán:
1. for i := 1 to n-1 do
2. for j := i + 1 to n do
3. if Mij ≠ Mij then Kết xuất "No", và dừng thuật toán.
đệ quy là cách để gọi các thuật toán gọi lại chính nó. vd: với thuật toán tính n! thì ta có thể viết bằng vòng lặp tuy nhiên ta còn có thể viết theo kiểu đệ quy như sau: nhận xét n!=n*(n-1)! nên ta có
Code
function giaithua(n:integer):longint; begin if n=1 then giaithua:=1 else giaithua:=n*giaithua(n-1); end;
trong hàm giaithua(n) em thấy nó sẽ gọi lại hàm giaithua(n-1). Chúng ta sẽ được học về cái này kỹ hơn về sau. còn Ma Trận chính là Array đó em! ^^ thường Ma Trận được dùng để gọi mảng hai chiều.
Bước 1: Tính giá trị D theo công thức
Trường hợp D > 0: Phương trình có 2 nghiệm được tính theo công thức
Dùng ngôn ngữ tự nhiên.
Lưu đồ:
if (điều kiện) then (hành động)
Thuật toán tìm phần tử lớn nhất trong một dãy hữu hạn các số nguyên:
