THUẬT TOÁN – ĐỘ PHỨC TẠP CỦA THUẬT TOÁN
Mục lục
THUẬT TOÁN – ĐỘ PHỨC TẠP CỦA THUẬT TOÁN........................................................................1
Mục lục........................................................................................................................................................1
1. THUẬT TOÁN........................................................................................................................................2
2. CÁC PHƯƠNG PHÁP BIỂU DIỄN THUẬT TOÁN...........................................................................7
3. ĐỘ PHỨC TẠP CỦA THUẬT TOÁN................................................................................................12
4. PHÂN LOẠI VẤN ĐỀ - BÀI TOÁN...................................................................................................15
5. THUẬT TOÁN ĐỆ QUY.....................................................................................................................17
6.THUẬT GIẢI.........................................................................................................................................20
7. CÂU HỎI...............................................................................................................................................26
8.Bài viết khác: SỰ PHÂN LỚP VẤN ĐỀ - BÀI TOÁN........................................................................27
1. THUẬT TOÁN
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.
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

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

3.1. Tính giá trị D = b
2
-4ac
3.2. Nếu D > 0 thì
3.2.1. Phương trình có hai nghiệm phân biệt x
1
và x
2
3.2.2. Giá trị của hai nghiệm được tính theo công thức sau

3.2.3. Kết thúc thuật toán.
3.3. Nếu D = 0 thì
3.3.1. Phương trình có nghiệm kép x
0

3.3.2. Giá trị của nghiệm kép là

3.3.3. Kết thúc thuật toán
3.4. Nếu D < 0 thì
3.4.1. Phương trình vô nghiệm.
3.4.2. Kết thúc thuật toán.
Thuật toán tìm hộp có trọng lượng nặng nhất
Vấn đề : Có n hộp có khối lượng khác nhau và một cái cân dĩa. Hãy chỉ ra cách cân để
tìm được hộp có trọng lượng nặng nhất. Vấn đề này là thể hiện của một bài toán tổng quát : Cho một
tập hợp A hữu hạn và một thứ tự toàn phần trên A. Hãy xây dựng thuật toán tìm phần tử lớn nhất của
A. Bài toán trong toán học có vẻ rất phức tạp nhưng một thể hiện trên thực tế lại rất dễ hiểu, và cách
giải quyết cũng đơn giản. Từ đó ta có thể dễ dàng suy ra cách giải bài toán tổng quát.
1. Nếu chỉ có 1 hộp (n=1) thì
1.1. Hộp đó chính là hộp nặng nhất.
1.2. Kết thúc thuật toán.

thì
a
i
= a
i-1
- b
i-1
b
i
= b
i-1

5.3. Ngược lại
b
i
= b
i-1
- a
i-1
a
i
= a
i-1
6. Trở lại bước 5.
7. Ước số chung lớn nhất của a, b là a
i
.
2. CÁC PHƯƠNG PHÁP BIỂU DIỄN THUẬT TOÁN
Khi chứng minh hoặc giải một bài toán trong toán học, ta thường dùng những ngôn từ
toán học như : "ta có", "điều phải chứng minh", "giả thuyết", ... và sử dụng những phép suy luận toán

2.2.3.Ðường đi (route)
Khi dùng ngôn ngữ tự nhiên, ta mặc định hiểu rằng quá trình thực hiện sẽ lần lượt đi từ bước
trước đến bước sau (trừ khi có yêu cầu nhảy sang bước khác). Trong ngôn ngữ lưu đồ, do thể hiện các
bước bằng hình vẽ và có thể đặt các hình vẽ này ở vị trí bất kỳ nên ta phải có phương pháp để thể hiện
trình tự thực hiện các thao tác.
Hai bước kế tiếp nhau được nối bằng một cung, trên cung có mũi tên để chỉ hướng thực hiện.
Chẳng hạn trong hình dưới, trình tự thực hiện sẽ là B1, B2, B3.
Từ thao tác chọn lựa có thể có đến hai hướng đi, một hướng ứng với điều kiện thỏa và một
hướng ứng với điều kiện không thỏa. Do vậy, ta dùng hai cung xuất phát từ các đỉnh hình thoi, trên
mỗi cung có ký hiệu Ð/Ðúng/Y/Yes để chỉ hướng đi ứng với điều kiện thỏa và ký hiệu S/Sai/N/No để
chỉ hướng đi ứng với điều kiện không thỏa.

2.2.4. Ðiểm cuối (terminator)
Ðiểm cuối là điểm khởi đầu và kết thúc của thuật toán, được biểu diễn bằng hình ovan, bên
trong có ghi chữ bắt đầu/start/begin hoặc kết thúc/end. Ðiểm cuối chỉ có cung đi ra (điểm khởi đầu)
hoặc cung đi vào (điểm kết thúc). Xem lưu đồ thuật toán giải phương trình bậc hai ở trên để thấy cách
sử dụng của điểm cuối.
2.2.5. Ðiểm nối (connector)
Ðiểm nối được dùng để nối các phần khác nhau của một lưu đồ lại với nhau. Bên trong điểm
nối, ta đặt một ký hiệu để biết sự liên hệ giữa các điểm nối.
2.2.6. Ðiểm nối sang trang (off-page connector)
Tương tự như điểm nối, nhưng điểm nối sang trang đượ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 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.
Ở trên chỉ là các ký hiệu cơ bản và thường được dùng nhất. Trong thực tế, lưu đồ còn có
nhiều ký hiệu khác nhưng thường chỉ dùng trong những lưu đồ lớn và phức tạp. Ðối với các thuật toán
trong cuốn sách này, ta chỉ cần sử dụng các ký hiệu trên là đủ.
2.3. Mã giả
Tuy sơ đồ khối thể hiện rõ quá trình xử lý và sự phân cấp các trường hợp của thuật toán
nhưng lại cồng kềnh. Ðể mô tả một thuật toán nhỏ ta phải dùng một không gian rất lớn. Hơn nữa, lưu