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.
Thuật toán giải phương trình bậc 2 |
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.
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ờ và 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ờ" và "có thể thực thi được" gọi
chung là tính xác định.
Giả
sử khi nhận một lớp học mới, Ban Giám hiệu yêu cầu giáo viên chủ nhiệm chọn lớp
trưởng mới theo các bước sau :
1. Lập danh sách tất các học sinh trong lớp.
2. Sắp thứ tự danh sách học sinh.
3.Chọn
học sinh đứng đầu danh sách để làm lớp trưởng.
Khi
nhận được thông báo này, giáo viên chắc chắn sẽ rất bối rối vì không hiểu là
trong danh sách học sinh cần có những thông tin gì? Danh sách chỉ cần họ tên,
hay cần thêm ngày tháng năm sinh? Có cần thêm điểm trung bình không? Yêu cầu 2
lại càng gây nhiều thắc mắc. Cần phải sắp xếp danh sách theo chiều tăng dần
hoặc giảm dần ? Sắp theo chỉ tiêu gì ? Theo tên, theo ngày tháng năm sinh hay
theo điểm trung bình chung, ...Giả sử sắp theo điểm trung bình thì nếu có hai
học sinh cùng điểm trung bình thì học sinh nào sẽ sắp trước, học sinh nào sẽ
sắp sau ? ...
Hướng
dẫn ở trên vi phạm tính chất "không mập mờ" của
thuật toán. Nghĩa là, có quá nhiều thông tin còn thiếu để làm cho các bước 1,2
được hiểu đúng và hiểu theo một nghĩa duy nhất. Nếu
sửa lại một chút ít thì hướng dẫn trên sẽ trở nên rõ ràng hơn rất nhiều và có
thể gọi là một thuật toán chọn lớp trưởng !
1. Lập danh sách tất
các học sinh trong lớp theo hai thông tin: Họ và Tên; Ðiểm trung bình cuối năm.
2. Sắp hạng học sinh theo
điểm trung bình theo thứ tự giảm dần (từ điểm cao đến điểm thấp). Hai học sinh
có cùng điểm trung bình sẽ có cùng hạng.
3. Nếu chỉ có một học sinh có hạng nhất
thì chọn học sinh đó làm lớp trưởng. Trường hợp có nhiều học sinh đồng hạng
nhất thì chọn học sinh có điểm môn Toán cao nhất làm lớp trưởng.
Nếu vẫn còn nhiều hơn một
học sinh đồng hạng nhất và có cùng điểm môn Toán cao nhất thì tiến hành bốc
thăm.
Ở
đây chúng ta cần phân biệt mập mờ và sự chọn lựa có
quyết định. Mập mờ là thiếu thông tin hoặc có nhiều chọn
lựa nhưng không đủ điều kiện để quyết định. Còn chọn lựa có quyết
định là hoàn toàn xác định duy nhất trong điều kiện cụ thể của vấn đề. Chẳng
hạn trong vấn đề chọn lớp trưởng ở trên, bước 3 thể hiện một sự lựa chọn có
quyết định. Tất nhiên, khi chưa lập danh sách, chưa xếp hạng theo điểm trung
bình thì giáo viên không thể biết được sẽ chọn lớp trưởng theo cách nào. Nhưng
khi đã sắp xong danh sách thì chỉ có một phương án chọn duy nhất.
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.
Tính "dừng" 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.
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!
Thuật toán thì cứng nhắc !
Các tính chất của thuật
toán rất chặt chẽ và cứng nhắc. Nhưng điều đó cũng có nghĩa là khả năng giải
quyết vấn đề theo kiểu thuật toán cũng bị giới hạn. Sau này, người ta đã
"làm mềm" đi hai tính chất quan trọng của thuật toán làtính xác
định và tính đúng để giải quyết những vấn
đề phức tạp hơn mà với các tính chất chặt chẽ của thuật toán thì không thể giải
quyết được. Ðó là các thuật toán đệ quy và thuật giải. Ta sẽ tìm hiểu về điều
này ngay trong các mục 4 và 5 của chương này.
Các đặc trưng
khác của thuật toán
Bên cạnh 3 đặc trưng chính là xác định, hữu hạn và đúng, thuật toán còn có thêm
3 đặc trưng phụ khác.
1. Ðầu vào và đầu ra (input/output)
: mọi
thuật toán, dù có đơn giản đến mấy cũng phải nhận dữ liệu đầu vào, xử lý nó và
cho ra kết quả cuối cùng.
2. Tính hiệu quả
(effectiveness) : 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.
3. Tính tổng quát (generalliness) : 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!
Tags
Algorithm