thaothanh_298
New Member
Download miễn phí Pascal - Thuật toán
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
Để tải bản Đầy Đủ của tài liệu, xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
Tóm tắt nội dung tài liệu:
1. THUẬT TOÁNThuậ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 hay 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 sắp xếp danh
sách theo chiều
tăng dần hay 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 hay 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 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 hay đườ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 hay 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 đư...