Giáo Trình Cấu Trúc Dữ Liệu Và Giải Thuật PDF

Giới thiệu giáo trình ” Giáo Trình Cấu Trúc Dữ Liệu Và Giải Thuật “

1.4. GIẢI THUẬT – PHÂN TÍCH VÀ ĐÁNH GIÁ GIẢI THUẬT

1.4.1. Giải thuật

Giải thuật (algorithm) là một trong những khái niệm quan trọng nhất trong tin học. Giải thuật chỉ ra một quy trình để thực hiện một công việc. Một trong những giải thuật nổi tiếng nhất, có từ thời cổ Hy Lạp là giải thuật Euclid, tìm ước số chung lớn nhất của hai số nguyên. Có thể mô tả giải thuật này như sau:

Giải thuật Euclid

Vào: m, n nguyên dương

Ra: d, ước chung lớn nhất của m và n.

Phương pháp

Bước 1: Tìm r, phần dư của phép chia m cho n

Bước 2: Nếu r = 0, thì d – n (gán giá trị của n cho d) và dừng lại

Ngược lại, thì m← n, n – r và quay lại bước 1

1.4.1.1. Khái niệm

Giải thuật là một dãy hữu hạn các bước, mỗi bước mô tả chính xác các phép toán hoặc hành động cần thực hiện để giải quyết vấn đề đặt ra.

1.4.1.2. Đặc trưng của giải thuật

Để hiểu đầy đủ ý nghĩa của giải thuật, chúng ta nêu ra 5 đặc trưng của nó:

i) Bộ dữ liệu vào: Mỗi giải thuật cần có một số lượng dữ liệu vào. Đó là các giá trị cần đưa vào khi giải thuật bắt đầu làm việc. Các dữ liệu này cần được lấy từ các tập hợp giá trị cụ thể nào đó. Chẳng hạn, trong giải thuật Euclid trên, m và n là các dữ liệu vào lấy từ tập các số nguyên dương.

ii) Dữ liệu ra: Mỗi giải thuật cần có một hoặc nhiều dữ liệu ra. Đó là các giá trị có quan hệ hoàn toàn xác định với các dữ liệu vào và là kết quả của sự thực hiện giải thuật. Trong giải thuật Euclid có một dữ liệu ra, đó là d, khi thực hiện đến bước 2 và phải dừng lại (trường hợp r = 0), giá trị của d là ước chung lớn nhất của m và n.

iii) Tính xác định: Mỗi bước của giải thuật cần phải được mô tả một các chính xác, chỉ có một cách hiều duy nhất. Đây là một đòi hỏi rất quan trọng. Bởi vì, nếu một bước có thể hiểu theo nhiều cách khác nhau, thì cùng một dữ liệu vào, những người thực hiện giải thuật khác nhau có thể dẫn đến các kết quả khác nhau. Để đảm bảo được tính xác định giải thuật cần phải được mô tả trong các ngôn ngữ lập trình. Trong các ngôn ngữ này, các mệnh đề được tạo thành theo quy tắc cú pháp nghiêm ngặt và chỉ có một ý nghĩa duy nhất.

iv) Tính khả thi: Tất cả các phép toán có mặt trong các bước của giải thuật phải đủ đơn giản. Điều này có nghĩa là, người lập trình có thể thực hiện chỉ bằng giấy trắng và bút trong khoảng thời gian hữu hạn. Chẳng hạn, với giải thuật Euclid, ta chỉ cần thực hiện các phép chia số nguyên, các phép gán và phép so sánh để biết được r = 0 hay r = 0.

v) Tính dừng: Với mọi bộ dữ liệu vào thoả mãn các điều kiện của dữ liệu vào, giải thuật phải dừng lại sau một số hữu hạn các bước thực hiện. Chẳng hạn, giải thuật Euclid thoả mãn điều kiện này. Bởi vì, khi thực hiện bước 1 thì giá trị của r nhỏ hơn n, nếu r ≠ 0 thì giá trị của n ở bước 2 là giá trị của r ở bước trước, ta có n > r = n₁> r = n2 > r2… Dãy số nguyên dương giảm dần cần phải kết thúc ở 0, do đó sau một số bước nào đó giá trị của r phải bằng 0, giải thuật dừng.