MỤC LỤC
1. THUẬT TOÁN
2. CÁC PHƯỢNG PHÁP BIỂU DIỄN THUẬT TOÁN
3. ĐỘ PHỨC TẠP CỦA THUẬT TOÁN
4.PHÂN LOẠI VẤN ĐỀ - BÀI TOÁN
5. THUẬT TOÁN ĐỆ QUY
6.THUẬT GIẢI
5.1.GIỚI THIỆU NGÔN NGỮ PASCAL
5.2. CÁC PHẦN TỬ CƠ BẢN CỦA NGÔN NGỮ PASCAL
5.3. CẤU TRÚC CHUNG CỦA CHƯƠNG TRÌNH PASCAL
5.4. SỬ DỤNG PHẦN MỀM TURBO PASCAL
5.5 CÂU HỎI TRẮC NGHIỆM
5.6. BÀI TẬP
6.1. KHÁI NIỆM VỀ KIỂU DỮ LIỆU
6.2. KIỂU SỐ NGUYÊN
6.3. KIỂU SỐ THỰC
6.4. KIỂU KÝ TỰ (CHAR)
6.5. KIỂU LÔGIC (BOOLEAN)
6.6. CHUỖI KÝ TỰ (STRING)
6.7. CÂU HỎI TRẮC NGHIỆM
7.1. HẰNG, BIẾN và BIỂU THỨC
7.2. CÂU LỆNH và LỜI CHÚ GIẢI
7.3.1. NHẬP DỮ LIỆU, THỦ TỤC “READLN”
7.3.2. XUẤT DỮ LIỆU, THỦ TỤC “WRITE” và “WRITELN”
7.4. KIỂU LIỆT KÊ và KIỂU ÐOẠN CON
7.5. CÂU HỎI TRẮC NGHIỆM
7.6. BÀI TẬP
Trang 1/287
8.1. CÂU LỆNH IF
8.2. CÂU LỆNH CASE
8.3. CÂU HỎI TRẮC NGHIỆM

15.2. DỮ LIỆU KIỂU TẬP TIN
15.3. CÂU HỎI TRẮC NGHIỆM
15.4. BÀI TẬP
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
đị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

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.
Trang 4/287
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.

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.
2. Ngược lại nếu có từ hai hộp trở lên (n>1)
2.1. Chọn hai hộp bất kỳ và đặt lên bàn cân.
2.2. Giữ lại hộp nặng hơn, cất hộp nhẹ hơn sang chỗ khác.
3. Nếu còn hộp chưa được cân thực hiện các bước sau, nếu không còn hộp nào nữa, sang bước 5.
3.1. Chọn một hộp bất kỳ và để lên dĩa cân còn trống.
3.2. Giữ lại hộp nặng hơn, cất hộp nhẹ hơn sang chỗ khác.
Trang 6/287
4. Trở lại bước 3.
5. Hộp còn lại trên cân chính là hộp nặng nhất. Kết thúc.

Thuật toán Euclid tìm ước số chung lớn nhất
Bài toán : Cho hai số nguyên dương a và b. Tìm ước số chung lớn nhất của a và b.
1. Yêu cầu cho biết giá trị của a, b.

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 học như phép suy ra, tương
đương, ...Thuật toán là một phương pháp thể hiện lời giải bài toán nên cũng phải tuân theo một số quy tắc nhất
định. Ðể có thể truyền đạt thuật toán cho người khác hay chuyển thuật toán thành chương trình máy tính, ta
phải có phương pháp biểu diễn thuật toán. Có 3 phương pháp biểu diễn thuật toán :
1. Dùng ngôn ngữ tự nhiên.
2. Dùng lưu đồ-sơ đồ khối (flowchart).
3. Dùng mã giả (pseudocode).
2.1. Ngôn ngữ tự nhiên
Trang 7/287
Trong cách biểu diễn thuật toán theo ngôn ngữ tự nhiên, người ta sử dụng ngôn ngữ thường ngày để liệt kê
các bước của thuật toán (Các ví dụ về thuật toán trong mục 1 của chương sử dụng ngôn ngữ tự nhiên). Phương
pháp biểu diễn này không yêu cầu người viết thuật toán cũng như người đọc thuật toán phải nắm các quy tắc.
Tuy vậy, cách biểu diễn này thường dài dòng, không thể hiện rõ cấu trúc của thuật toán, đôi lúc gây hiểu lầm
hoặc khó hiểu cho người đọc. Gần như không có một quy tắc cố định nào trong việc thể hiện thuật toán bằng

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.
Trang 9/287
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 đồ chỉ phân biệt hai thao tác là
rẽ nhánh (chọn lựa có điều kiện) và xử lý mà trong thực tế, các thuật toán còn có thêm các thao tác lặp (Chúng
ta sẽ tìm hiểu về thao tác lặp trong các bài sau).
Khi thể hiện thuật toán bằng mã giả, ta sẽ vay mượn các cú pháp của một ngôn ngữ lập trình nào đó để thể hiện
thuật toá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. Dùng mã
giả vừa tận dụng được các khái niệm trong 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. Tất nhiên là trong mã giả ta vẫn dùng một phần ngôn ngữ tự nhiên. Một khi đã vay mượn cú
pháp và khái niệm của ngôn ngữ lập trình thì chắc chắn mã giả sẽ bị phụ thuộc vào ngôn ngữ lập trình đó.
Chính vì lý do này, chúng ta chưa vội tìm hiểu về mã giả trong bài này (vì chúng ta chưa biết gì về ngôn ngữ
lập trình!). Sau khi tìm hiểu xong bài về thủ tục - hàm bạn sẽ hiểu mã giả là gì !
Một đoạn mã giả của thuật toán giải phương trình bậc hai
if Delta > 0 then begin
Trang 10/287
x
1
=(-b-sqrt(delta))/(2*a)
x

của thuật toán và chi phí (số thao tác, số phép tính cộng,trừ, nhân, chia, rút căn,...) để thực hiện thuật toán. Sở dĩ
người ta không quan tâm đến thời gian tuyệt đối của thuật toán vì yếu tố này phụ thuộc vào tốc độ của máy
tính, mà các máy tính khác nhau thì có tốc độ rất khác nhau. Một cách tổng quát, chi phí thực hiện thuật toán là
một hàm số phụ thuộc vào dữ liệu đầu vào :T = f(input)
Tuy vậy, khi phân tích thuật toán, người ta thường chỉ chú ý đến mối liên quan giữa độ lớn của dữ liệu đầu
vào và chi phí. Trong các thuật toán, độ lớn của dữ liệu đầu vào thường được thể hiện bằng một con số nguyên
n. Chẳng hạn : sắp xếp n con số nguyên, tìm con số lớn nhất trong n số, tính điểm trung bình của n học sinh, ...
Lúc này, người ta thể hiện chi phí thực hiện thuật toán bằng một hàm số phụ thuộc vào n :
T = f(n)
Trang 11/287
Việc xây dựng một hàm T tổng quát như trên trong mọi trường hợp của thuật toán là một việc rất khó khăn,
nhiều lúc không thể thực hiện được. Chính vì vậy mà người ta chỉ xây dựng hàm T cho một số trường hợp đáng
chú ý nhất của thuật toán, thường là trường hợp tốt nhất và xấu nhất.
Chúng ta trở lại ví dụ về thuật toán tìm hộp nặng nhất trong n hộp cho trước, nhưng lần này ta làm việc trên
một thể hiện khác của vấn đề. Ðây là một thuật toán tương đối đơn giản nên chúng ta có thể tiến hành phân tích
được độ phức tạp. Trước khi phân tích độ phức tạp, ta nhắc lại đôi điều về thuật toán này.
Tìm số lớn nhất trong một dãy số
Bài toán : Cho một dãy số a có n phần tử a
1
, a
2
, ...a
n
. Hãy xây dựng thuật toán để tìm con số lớn nhất trong
dãy a.
Nhận xét
1. Nếu dãy chỉ có 1 phần tử thì phần tử đó là số lớn nhất.
2. Giả sử dãy có n phần tử và ta đã xác định được phần tử lớn nhất là amax . Nếu bổ sung thêm phần tử thứ
an+1 vào dãy mà an+1 > amax thì an+1 chính là phần tử lớn nhất của dãy có n+1 phần tử. Trường hợp ngược
lại, nghĩa là an+1 £ amax thì amax vẫn là phần tử lớn nhất của dãy có n+1 phần tử.

n
) và dãy được sắp xếp theo thứ tự tăng dần.
Trang 12/287

Dựa theo sơ đồ khối của thuật toán, ta nhận thấy rằng, trong mọi trường hợp của bài toán, phép "ghi nhớ" ở
bước 3.1 luôn được thực hiện và số lần thực hiện là n-1 (ứng với việc xét từ phần tử a
2
đến a
n
). Ta gọi đây là chi
phí cố định hoặc bất biến của thuật toán.
Trường hợp tốt nhất : do a
max
= a
1
suy ra, với mọi i ³ 2, a
i
< a
max
. Do đó, điều kiện a
i
>a
max
ở bước 3.1 luôn
không thỏa nên bước 3.1.1 không bao giờ được thực hiện. Như vậy, chi phí chung cho trường hợp này chính là
chi phí cố định của bài toán. T = f(n) = n-1
Trường hợp xấu nhất :
Ta có : với mọi i>1, a
i
-1< a

toán đều có thể chia làm 2 lớp lớn là : giải được và không giải được. Lớp giải được chia làm 2 lớp con. Lớp con
đầu tiên là các bài toán có độ phức tạp đa thức : nghĩa là bài toán có thể giải được bằng thuật toán có độ phức
tạp đa thức (hay nói ngắn gọn : lớp đa thức) được xem là có lời giải thực tế. Lớp con thứ hai là những bài toán
có độ phức tạp không phải là đa thức mà lời giải của nó được xem là thực tế chỉ cho những số liệu đầu vào có
chọn lựa cẩn thận và tương đối nhỏ. Cuối cùng là những bài toán thuộc loại NP chưa thể phân loại một cách
chính xác là thuộc lớp bài toán có độ phức tạp đa thức hay có độ phức tạp không đa thức.
4.1. Lớp bài toán có độ phức tạp đa thức
Các bài toán thuộc lớp này có độ phức tạp là O(nk) hoặc nhỏ hơn O(nk). Chẳng hạn như các bài toán có độ
phức tạp là O(nlog2n) được xem là các bài toán thuộc lớp đa thức vì nlog2n bị chặn bởi n2 ( nlog2n £ n2 với
mọi n>0). Như vậy các bài toán có độ phức tạp hằng O(1), phức tạp tuyến tính O(n) và logarith O(nlogan) đều
là các bài toán thuộc lớp đa thức. Còn các bài toán có độ phức tạp lũy thừa O(an) hoặc giai thừa O(n!) là không
thuộc lớp đa thức.
Tuy độ phức tạp chỉ là số đo về độ tăng của chi phí ứng với độ tăng của dữ liệu đầu vào nhưng nó cũng cho
chúng ta có một đánh giá tương đối về thời gian thi hành thuật toán. Các thuật toán thuộc lớp đa thức được xem
là các bài toán có lời giải thực tế. Lời giải thực tế được hiểu rằng là chi phí về mặt thời gian và không gian cho
việc giải bài toán là chấp nhận được trong điều kiện hiện tại. Bất kỳ một bài toán nào không thuộc lớp này thì
đều có chi phí rất lớn.
Trang 14/287
Có thể giải được hay không?
Người ta đã ước tính thời gian cần thiết để giải một mật mã được mã hóa bằng khóa 128-bit là trên 1 triệu năm
với điều kiện làm việc trên các siêu máy tính mạnh nhất hiện nay!
Chính vì lý do này, một bài toán được xem là có thể giải được trên thực tế hay không phụ thuộc vào độ phức
tạp của bài toán đó có phải là đa thức hay không.
4.2. Lớp bài toán có độ phức tạp không đa thức
Thật không may mắn, nhiều bài toán thực sự có lời giải lại không thuộc lớp của bài toán đa thức. Ví dụ : cho
một tập hợp có n phần tử, hãy liệt kê tất cả các tập con khác trống của tập hợp này. Bằng toán học, người ta đã
chứng minh được rằng số tập con của một tập hợp có n phần tử là 2
n-1
. Lời giải tuy đã có nhưng khi thể hiện lời
giải này bằng bất kỳ thuật toán nào thì phải tốn ít nhất 2

toán học, người ta đã chứng minh được rằng độ phức tạp của thuật toán này là O(n!). Như vậy, với số đại lý lớn
thì thuật toán trên được xem là không thực tế. Bây giờ, chúng ta xem qua một thuật toán không tự quyết.
1. Chọn một con đường có thể và tính chiều dài của nó.
Trang 15/287
2. Nếu chiều dài này không lớn hơn giới hạn thì báo là thành công, ngược lại báo chọn lựa sai.
Quan điểm của ta trong cách giải quyết này là nếu chọn sai thì là do lỗi của người chọn chứ không phải lỗi của
thuật toán !.
Theo thuật toán này thì chi phí để tính chiều dài của con đường được chọn sẽ tỷ lệ với số đại lý; chi phí để so
sánh chiều dài quãng đường với giới hạn cho phép thì không liên quan đến số thành phố. Như vậy, chi phí của
thuật toán này là một hàm có dạng T = an+b với n là số đại lý và a,b là các hằng số. Ta kết luận rằng, độ phức
tạp của thuật toán này là O(n) hay độ phức tạp thuộc lớp đa thức.
Như vậy, nếu dùng thuật toán tự quyết thì bài toán người bán hàng sẽ có độ phức tạp không thuộc lớp đa thức,
còn nếu dùng thuật toán không tự quyết thì bài toán sẽ có độ phức tạp đa thức.
Ðịnh nghĩa
Một bài toán khi được giải bằng một thuật toán không tự quyết mà có độ phức tạp thuộc lớp đa thức thì được
gọi là một bài toán đa thức không tự quyết hay viết tắt là bài toán NP.
Theo định nghĩa trên thì bài toán người bán hàng là bài toán thuộc lớp NP.
Cho đến nay người ta chưa chứng minh được rằng tồn tại hay không một thuật toán tự quyết có độ phức tạp đa
thức cho bài toán người bán hàng rong. Vì vậy, bài toán này (là một bài toán NP) chưa thể xếp được vào lớp đa
thức hay không đa thức. Do đó, lớp bài toán NP chưa thể phân loại là thuộc lớp đa thức hay không.
Dĩ nhiên, lớp bài toán NP cũng chứa những bài toán thuộc lớp đa thức thực sự, bởi vì nếu một bài toán được
giải bằng thuật toán tự quyết có độ phức tạp đa thức thì chắc chắn khi dùng thuật toán không tự quyết thì cũng
sẽ có độ phức tạp đa thức.
5. THUẬT TOÁN ĐỆ QUY
Thuật toán đệ quy là một trong những sự mở rộng cơ bản nhất của khái niệm thuật toán. Như đã biết, một
thuật toán cần phải thỏa mãn 3 tính chất :
– Tính hữu hạn.
– Tính xác định
– Tính đúng đắn
Trang 16/287

đệ quy có sự liên hệ rất chặt chẽ với quy nạp toán học.
Ðệ quy mạnh ở điểm nó có thể định nghĩa một tập vô hạn các đối tượng chỉ bằng một số hữu hạn các mệnh đề.
Tuy nhiên, đặc tính này của đệ quy lại vi phạm tính xác định của thuật toán. Về nguyên tắc, một bước trong
thuật toán phải được xác định ngay tại thời điểm bước đó được thi hành, nhưng với thuật toán đệ quy, bước thứ
n không được xác định ngay trong ngữ cảnh của nó mà phải xác định thông qua một bước thấp hơn. Chẳng hạn,
để tính được giá trị phần tử thứ 5 của dãy Fibonacci theo định nghĩa ở trên, ta phải tính f
3
+f
4
, nhưng ta chưa biết
giá trị f
3
và f
4
tại thời điểm này. Ðến đây, ta phải lùi lại để tính f
3
và f
4
. Ðể tính f
3
ta lại phải lùi về để tính
f
2
,...Tất nhiên, là quá trình tính lùi này phải dừng sau một số hữu hạn bước. Trong trường hợp này, điểm dừng
chính là giá trị f
1
và f
0
.
Trang 17/287

năm thì chúng ta có thể sẵn lòng chấp nhận một giải pháp gần tối ưu mà chỉ cần máy tính chạy trong vài ngày
hoặc vài giờ.
Các cách giải chấp nhận được nhưng không hoàn toàn đáp ứng đầy đủ các tiêu chuẩn của thuật toán thường
được gọi là các thuật giải. Khái niệm mở rộng này của thuật toán đã mở rộng cửa cho chúng ta trong việc tìm
kiếm phương pháp để giải quyết các bài toán được đặt ra.
Một trong những thuật giải thường được đề cập đến và sử dụng trong khoa học trí tuệ nhân tạo là các cách giải
theo kiểu Heuristic.
6.2. Thuật giải Heuristic
Thuật giải Heuristic là một sự mở rộng khái niệm thuật toán. Nó thể hiện cách giải bài toán với các đặc tính
sau :
Thường tìm được lời giải tốt (nhưng không chắc là lời giải tốt nhất)
Giải bài toán theo thuật giải Heuristic thường dễ dàng và nhanh chóng đưa ra kết quả hơn so với giải thuật
tối ưu, vì vậy chi phí thấp hơn.
Trang 19/287
Thuật giải Heuristic thường thể hiện khá tự nhiên, gần gũi với cách suy nghĩ và hành động của con người.
Có nhiều phương pháp để xây dựng một thuật giải Heuristic, trong đó người ta thường dựa vào một số
nguyên lý cơ sở như sau:
Nguyên lý vét cạn thông minh :
Trong một bài toán tìm kiếm nào đó, khi không gian tìm kiếm lớn, ta thường tìm cách giới hạn lại không gian
tìm kiếm hoặc thực hiện một kiểu dò tìm đặc biệt dựa vào đặc thù của bài toán để nhanh chóng tìm ra mục tiêu.
Nguyên lý tham lam (Greedy):
Lấy tiêu chuẩn tối ưu (trên phạm vi toàn cục) của bài toán để làm tiêu chuẩn chọn lựa hành động cho phạm vi
cục bộ của từng bước (hay từng giai đoạn) trong quá trình tìm kiếm lời giải.
Nguyên lý thứ tự :
Thực hiện hành động dựa trên một cấu trúc thứ tự hợp lý của không gian khảo sát nhằm nhanh chóng đạt được
một lời giải tốt.
Hàm Heuristic:
Trong việc xây dựng các thuật giải Heuristic, người ta thường dùng các hàm Heuristic. Ðó là các hàm đánh giá
thô, giá trị của hàm phụ thuộc vào trạng thái hiện tại của bài toán tại mỗi bước giải. Nhờ giá trị này, ta có thể
chọn được cách hành động tương đối hợp lý trong từng bước của thuật giải.

1
,
P
2
, ...P
n
. Mọi chi tiết đều có thể được gia công trên bất kỳ máy nào. Một khi đã gia công một chi tiết trên một
máy, công việc sẽ tiếp tục cho đến lúc hoàn thành, không thể bị ngắt ngang. Ðể gia công một công việc J
i
trên
một máy bất kỳ ta cần dùng một thời gian tương ứng là t
i
. Nhiệm vụ của công ty là phải làm sao gia công xong
toàn bộ n chi tiết trong thời gian sớm nhất.
Chúng ta xét bài toán trong trường hợp có 3 máy P
1
, P
2
, P
3
và 6 công việc với thời gian là t
1
=2, t
2
=5, t
3
=8, t
4
=1,
t

tương đối tốt.

Bài toán Ta-canh - ứng dụng của hàm Heuristic
Bài toán Ta-canh đã từng là một trò chơi khá phổ biến, đôi lúc người ta còn gọi đây là bài toán 9-puzzle. Trò
chơi bao gồm một hình vuông kích thước 3x3 ô. Có 8 ô có số, mỗi ô có một số từ 1 đến 8. Một ô còn trống.
Mỗi lần di chuyển chỉ được di chuyển một ô nằm cạnh ô trống về phía ô trống. Vấn đề là từ một trạng thái ban
đầu bất kỳ, làm sao đưa được về trạng thái cuối là trạng thái mà các ô được sắp lần lượt từ 1 đến 8 theo thứ tự
từ trái sang phải, từ trên xuống dưới, ô cuối dùng là ô trống.

Cho đến nay, người ta vẫn chưa tìm được một thuật toán chính xác, tối ưu để giải bài toán này. Tuy nhiên, cách
giải theo kiểu Heuristic lại khá đơn giản. Nhận xét rằng : tại mỗi thời điểm ta chỉ có tối đa 4 ô có thể di chuyển.
Vấn đề là tại thời điểm đó, ta sẽ chọn lựa di chuyển ô nào? Chẳng hạn ở hình trên, ta nên di chuyển (1), (2), (6)
hay (7)?
Gọi T
0
là trạng thái đích của bài toán và T
K
là trạng thái hiện tại. Ta gọi V(i,j) là con số nằm ở ô (i,j), với ô
trống V(i,j)=0.

Ta đặt d(i,j) là số ô cần di chuyển để đưa con số ở ô (i,j) về đúng vị trí của nó ở trạng thái TO .
Hàm F
K
tại trạng thái T
K
bằng tổng của các d(i,j) sao cho vị trí (i,j) không phải là ô trống.
Trang 23/287
Như vậy đối với trạng thái ở hình ban đầu, hàm FK sẽ có giá trị là
FK = 2+1+3+1+0+1+2+2=12.
Một cách tổng quát, giá trị hàm FK tại trạng thái TK sẽ là

PASCAL là ngôn ngữ lập trình cấp cao được giáo sư Niklaus Wirth ở trường đại học Kỹ thuật Zurich
(Thụy sĩ) thiết kế và công bố vào năm 1971. Ông đặt tên cho ngôn ngữ của mình là Pascal để tưởng nhớ nhà
toán học nổi tiếng người Pháp ở thế kỷ 17: Blaise Pascal, người đã sáng chế ra chiếc máy tính cơ khí đầu tiên
của nhân loại. Qua thời gian sử dụng, Pascal ngày càng được đông đảo người dùng đánh gía cao, và trở thành
một trong các ngôn ngữ thảo chương phổ biến nhất hiện nay.
Thành công của ngôn ngữ Pascal là ở chỗ: nó là ngôn ngữ đầu tiên đưa ra và thể hiện được khái niệm
lập trình có cấu trúc. Ý tưởng về một chương trình có cấu trúc xuất phát từ suy nghĩ cho rằng có thể chia một
bài toán lớn, phức tạp thành nhiều bài toán nhỏ, đơn giản hơn. Nếu mỗi bài toán nhỏ được giải quyết bằng một
chương trình con, thì khi liên kết các chương trình con này lại sẽ tạo nên một chương trình lớn giải quyết được
bài toán ban đầu?.
Bằng cách chia một chương trình thành các chương trình con như vậy, người thảo chương có thể lập
trình để giải quyết riêng lẻ từng phần một, từng khối một, hoặc có thể tổ chức để nhiều người cùng tham gia,
Trang 24/287
mỗi người phụ trách một vài khối. Ðặc biệt khi phải thay đổi hay sửa chữa trong một khối thì điều đó sẽ ít ảnh
hưởng đến các khối khác.
Tính cấu trúc của ngôn ngữ Pascal còn thể hiện trong việc tổ chức các câu lệnh và tổ chức dữ liệu. Từ
các lệnh đã có, người thảo chương có thể nhóm chúng lại với nhau và đặt giữa hai từ khóa Begin và End tạo
thành một câu lệnh mới phức tạp hơn gọi là câu lệnh ghép. Ðến lượt mình, hai hay nhiều lệnh ghép lại có thể
được nhóm lại để tạo thành một câu lệnh ghép phức tạp hơn nữa,.v.v. Tương tự như thế, ngôn ngữ Pascal cũng
cho phép xây dựng các kiểu dữ liệu phức tạp hơn từ các kiểu dữ liệu đã có.
Pascal là một ngôn ngữ không chỉ chặt chẽ về mặt cú pháp mà còn chặt chẽ về mặt dữ liệu. Mỗi biến,
mỗi hằng tham gia trong chương trình luôn có một kiểu dữ liệu xác định và chỉ nhận những gía trị có cùng kiểu
dữ liệu với nó. Ðiều này buộc người lập trình phải nắm chắc cú pháp và luôn chú ý đến tính tương thích của các
biểu thức về mặt kiểu dữ liệu. Chính vì thế, thảo chương bằng ngôn ngữ Pascal là một cơ hội tốt không chỉ rèn
luyện tư duy mà còn rèn luyện tính cẩn thận và chính xác.
Ngày nay, Ngôn ngữ Pascal được dùng để viết các chương trình ứng dụng trong nhiều lĩnh vực. Với văn
phạm sáng sủa, dễ hiểu, với khả năng đủ mạnh, Pascal được xem là ngôn ngữ thích hợp nhất để giảng dạy ở các
trường phổ thông và đại học.
II.CÁC PHẦN TỬ CƠ BẢN CỦA NGÔN NGỮ PASCAL
1.Tập ký tự cơ bản