Chương 7 - Giải thuật xử lý thông tin
CHƯƠNG 7. GIẢI THUẬT
7.1. KHÁI NIỆM BÀI TOÁN VÀ GIẢI THUẬT
Trước khi xem xét đặc trưng của “bài toán” ta xét một số ví dụ.
Ví dụ 1. Bài toán kiểm tra tính nguyên tố.
Cho: Số nguyên dương N;
Cần biết: N có là số nguyên tố hay không?
Ví dụ 2. Bài toán quản lý hồ sơ cán bộ.
Cho: Hồ sơ gốc của các cán bộ trong cơ quan
Cần biết: Bảng thống kê, phân loại cán bộ theo trình độ văn hoá
Qua các ví dụ trên, ta thấy các bài toán được cấu tạo bởi hai thành phần cơ bản:
 Thông tin vào (input): cái cho trước
 Thông tin ra (output): cái cần tìm
Như vậy, việc cho một bài toán có nghĩa là mô tả rõ input và output của nó. Cho bài toán
nghĩa là làm rõ câu hỏi "Có các dữ kiện gì và phải làm gì?" nhưng không cho biết "Phải
làm thế nào". Việc giải bài toán có nghĩa là xuất phát từ input dùng một số hữu hạn số lần
thực hiện các thao tác thích hợp để tìm được output theo yêu cầu của bài toán đã đề ra.
Lưu ý rằng trong toán học có một xu hướng nghiên cứu định tính các bài toán. Theo xu
hướng này, khi xem xét các bài toán, người ta chỉ cần chứng tỏ sự tồn tại của output khi
cho input và nếu có thể, xét xem có bao nhiêu "lời giải" và nghiên cứu tính chất của chúng.
Trong các nghiên cứu như vậy, nhiều khi ta không cần tìm ra lời giải một cách tường minh
nhưng bằng cách dùng các công cụ toán học khác nhau một cách thích hợp ta vẫn có thể
chứng minh chặt chẽ các điều khẳng định liên quan đến lời giải. Chẳng hạn, định lý của
giải tích khẳng định rằng nếu hàm f(x) liên tục trên đoạn [a, b] và f(a). f(b)<0 thì tồn tại
điểm c nằm giữa a và b sao cho f’(c) = 0. Sự tồn tại lời giải theo nghĩa này không luôn cho
ta cách thức khả thi để tìm ra lời giải.
Ở đây, ta sẽ quan niệm việc giải bài toán là việc xác định tường minh output theo input
bằng một quá trình có thể thực hiện một cách hiệu quả. Đó chính là nội dung cơ bản của lý
thuyết tính toán.
Theo lý thuyết tính toán, một quá trình gồm một dãy hữu hạn các thao tác có thể thực hiện
được sắp xếp theo một trình tự xác định dùng để giải một bài toán được gọi là một giải

định rằng nếu không gặp phép chuyển điều khiển thì bộ xử lý sẽ thực hiện tuần tự: sau
bước thứ i sẽ chuyển sang bước thứ i + 1. Như vậy bước 3 nếu không quay về bước 2 thì sẽ
thực hiện tiếp bước 4.
7.2. MỘT SỐ ĐẶC TRƯNG CỦA GIẢI THUẬT
Người ta thường liệt kê các đặc trưng sau đây của giải thuật:
7.2.1. Tính kết thúc (tính dừng)
Giải thuật phải đưa ra được output sau một số hữu hạn bước thực hiện. Giải thuật Euclid
tìm UCLN thoả mãn tính dừng vì sau mỗi bước ta thấy tổng a+b giảm thực sự nhưng
không được hơn 2. Vì vậy quá trình trên nhất định phải dừng sau một số hữu hạn bước.
Lưu ý rằng số bước của một quy tắc thao tác có thể là hữu hạn nhưng quy tắc đó không có
tính dừng. Ví dụ, Xét quy tắc sau:
Bước 1: Xoá bảng
Bước 2: Vẽ hình tròn
Bước 3: Quay lại bước 1
Quy tắc đó có 3 bước nhưng không có tính dừng
7.2.2. Tính xác định
Tính xác định của giải thuật đòi hỏi ở mỗi bước các thao tác phải hoàn toàn xác định, đơn
trị không có sự nhập nhằng, lẫn lộn, tuỳ tiện. Nói cách khác, trong cùng một điều kiện, các
chủ thể xử lý dù là người hay máy thực hiện cùng một bước của giải thuật thì phải cho
cùng một kết quả.
Nhờ tính chất này mà việc thực hiện thuật toán thuần tuý mang tính cơ học, không cần bất
kỳ một sự chỉ dẫn nào về cách giải bài toán cả.
53
Chương 7 - Giải thuật xử lý thông tin
7.2.3. Tính phổ dụng
Tính phổ dụng có nghĩa là một giải thuật có thể được áp dụng với một lớp các bài toán với
input thay đổi chứ không chỉ áp dụng cho một trường hợp cụ thể. Giải thuật Euclid nói trên
có thể áp dụng cho bất kỳ cặp hai số tự nhiên
Cần lưu ý là trong khi tính dừng và tính xác định là điều kiện cần để một quá trình là một
giải thuật thì tính phổ dụng chỉ là một tính chất thường thấy vì có nhiều bài toán có input

Khối chỉ điêm
kết thúc
Hướng xử lý
Khối input
Khối output
Khối thao
tác tuần tự
Chương 7 - Giải thuật xử lý thông tin
trị ta sẽ dùng dấu gán := với ý nghĩa đại lượng đứng bên trái dấu gán được gán giá trị cho
biểu thức phía phải dấu gán. Khối tính toán có nhiều đường đi đến và 1 đường đi ra.
Khối điều kiện được biểu diễn bằng hình thoi. Trong khối này ta viết một điều kiện. Tuỳ
theo điều kiện này thoả mãn hay không mà việc thực hiện tiếp theo sẽ được chỉ dẫn bởi
một trong hai đường đi ra mang dẫu + (cho trường hợp đúng) hoặc dấu - (cho trường hợp
sai). Như vậy khối điều kiện có một đường đi đến và hai đường đi ra.
Hai khối đặc biệt là khối bắt đầu và khối kết thúc được biểu diễn bằng hình tròn chỉ rõ
điểm bắt đầu và điểm kết thúc của giải thuật. Khối bắt đầu không có đường đi đến và có 1
đường đi ra. Khối kết thúc không có đường đi ra, có thể có một hoặc nhiều đường đi tới.
Trong khối input ghi rõ các đại lượng vào, và ở khối output ghi các đại lượng ra. Khối
input có thể đặt kế tiếp khối bắt đầu, còn khối output có thể đặt liền trước khối kết thúc.
Chúng ta dùng lưu đồ ở Hình 7.2 diễn tả lại giải thuật Euclid tìm UCLN của hai số nguyên
dương.
Hình 7.2. Lưu đồ cho giải thuật Euclid
55
đúng
Nhập a, b
d := a
In d

Lấy 3 que
Ta lấy 4-x que
Đối phương lấy
x que diêm
Số diêm
còn >0 ?
Tuyên bố
thắng cuộc
đúng
sai
Chương 7 - Giải thuật xử lý thông tin
7.4. SƠ LƯỢC VỀ ĐÁNH GIÁ GIẢI THUẬT
Đối với một bài toán, có thể có nhiều giải thuật nhưng chúng phải cho cùng một output đối
với một input. Tuy nhiên chúng có thể khác nhau về hiệu quả:
 Hiệu quả thời gian: Tốc độ xử lý là nhanh hay chậm. Ta có thể đánh giá căn cứ vào
số bước thực hiện.
 Hiệu quả không gian: Có thể đánh giá không gian lưu trữ theo số các đối tượng
dùng để ghi nhớ các kết quả (kể cả kết quả trung gian).
Ví dụ: Để tìm USCLN có thể có nhiều giải thuật như:
Giải thuật 2:
Bước 1: Nhập a và b.
Bước 2: Phân tích các số a và b thành tích của các thừa số nguyên tố.
Bước 3: Lấy tích của các thừa số chung với số mũ nhỏ nhất làm USCLN.
Bước 4: Kết thúc xử lý.
Giải thuật 3 : Giải thuật Euclid cải tiến
Bước 1: Nhập a và b.
Bước 2: Chia a cho b tìm số dư r.
Bước 3: Nếu r = 0 thì thông báo kết quả: UCLN là b rồi chuyển bước 5.
Bước 4: Gán giá trị b cho a, gán giá trị r cho b rồi quay trở lại thực hiện bước 2.
Bước 5: Kết thúc.

d) Dùng một cốc phụ để tráo nước ở hai cốc cho trước.
e) Tìm chu vi và diện tích của hình tròn có bán kính cho trước.
58