THUẬT TOÁN [ P_1 ]

1.1. KHÁI NIỆM THUẬT TOÁN.

1.1.1. Mở đầu:

Có nhiều lớp bài toán tổng quát xuất hiện trong toán học rời rạc. Chẳng hạn, cho một dãy các số nguyên, tìm s ố lớn nhất; cho một tập hợp, liệt kê các tập con của nó; cho tập hợp các số nguyên, xếp chúng theo thứ tự tăng dần; cho một mạng, tìm đường đingắn nhất giữa hai đỉnh của nó. Khi được giao cho một bài toán như vậy thì việc đầu tiên ph ải làm là xây dựng một mô hình dịch bài toán đó thành ngữ cảnh toán học. Các cấu trúc rời rạc được dùng t rong các mô hình này là tập hợp, dãy, hàm, hoán vị, quan hệ,cùng với các cấu trúc khác như đồ thị, cây, mạng - những khái niệm sẽ được nghiên cứu ở các chương sau.
Lập được một mô hình toán học thích hợp chỉ là một phần của quá trình giải. Để hoàn tất quá trình giải, còn cần phải có một phương pháp dùng mô hình để giải bài toán tổng quát. Nói một cách lý tưởng, cái được đòi hỏi là một thủ tục, đó là dãy các bước dẫn tới đáp số mong muốn. Một dãy các bước như vậy, được gọi là một thuật toán.
Khi thiết kế và cài đặt một phần mềm tin học cho một vấn đề nào đó, ta cần phải đưa ra phương pháp giải quyết mà th ực chất đó là thuật toán giải quyết vấn đề này. Rõ ràng  rằng, nếu không  tìm được  một phương pháp giải quyết thì không thể lập trìnhđược. Chính vì thế, thuật toán là khái niệm nền tảng của hầu hết các lĩnh vực của tin học.

1.1.2. Định nghĩa: 

Thuật toán là một bảng liệt kê các chỉ dẫn (hay quy tắc) cần thực hiện theo từng bước xác định nhằm giải một bài toán đã cho.Thuật ngữ “Algorithm” (thuật toán) là xuấ t phát từ tên nhà toán học Ả Rập Al Khowarizmi. Ban đầu, từ algorism được dùng để chỉ các quy tắc thực hiện các phép tính số học trên các số thập phân. Sau đó, algorism chuyển thành algorithm vào thế kỷ 19. Với sự quan tâm ngày càng tăng đối với các máy tí nh, khái niệm thuật toán đã được cho một ý nghĩa chung hơn, bao hàm cả các thủ tục xác định để giải các bài toán, chứ không phải chỉ là thủ tục để thực hiện các phép tính số học.
Có nhiều cách trình bày thuật toán: dùng ngôn ngữ tự nhiên, ngôn ngữ lưu đồ (sơ đồ khối), ngôn ngữ lập trình. Tuy nhiên, một khi dùng ngôn ng ữ lập trình thì chỉ những lệnh được phép trong ngôn ngữ đó mới có thể dùng được và điều này thường làm cho sự mô tả các thuật toán trở nên rối rắm và khó hiểu. Hơn n ữa, vì nhiều ngôn ngữ lập trình đều được dùng rộng rãi, nên chọn một ngôn ngữ đặc biệt nào đó là điều ng ười ta không muốn. Vì vậy ở đây các thuật toán ngoài vi ệc được tr ình bày bằng ngôn ngữ tự nhiên cùng với những ký hiệu toán học quen thuộc còn dùng một dạng giả mã để mô tả thuật toán. Giả mã tạo ra bước trung gian giữa sự mô tả một thuật toán bằng ngôn ngữ thông thường và sự thực hiện thuật toán đó trong ngôn ngữ lập trình. Các bước của thuật toán được chỉ rõ bằng cách dùng các lệnh giống như trong các ngôn ngữ lập trình.

Thí dụ 1: Mô tả thuật toán tìm phần tử lớn nhất trong một dãy h ữu hạn các số nguyên.
a) Dùng ngôn ngữ tự nhiên đ ể mô tả các bước cần phải thực hiện :

1. Đặt giá trị cực đại tạm thời bằng số nguyên đầu tiên trong dãy. (Cực đại tạm
thời sẽ là số nguy ên lớn nhất đã được kiểm tra ở một giai đoạn nào đó của thủ tục.)
2. So sánh s ố nguyên tiếp sau với giá trị cực đại tạm thời, nếu nó lớn hơn giá trị
c ực đại tạm thời thì đặt cực đại tạm thời bằng số nguyên đó.
3. L ặp lại bước trước nếu còn các số nguy ên trong dãy.
4. Dừng khi không còn số nguy ên nào nữa trong dãy. Cực đại tạm thời ở điểm
này chính là số nguy ên lớn nhất của dãy.

b) Dùng đoạn giả mã:

procedure max (a1, a2, ..., an: integers)
max:= a1
for i:= 2 to n
if max <ai
then max:= ai{max là phần tử lớn nhất}

Thuật toán này trước hết gán số hạng đầu tiên a của dãy cho biến max. Vòng lặp “for” được dùng để kiểm tra lần lượt các số hạng của dãy. Nếu một số hạng lớn hơn giá trị hiện thời của max thì nó được gán làm giá trị mới của max.

1.1.3. Các đặc trưng của thuật toán:

-- Đầu vào (Input): Một thuật toán có các giá trị đầu vào từ một tập đã được chỉ rõ.
-- Đầu ra (Output): Từ mỗi tập các giá trị đầu vào, thuật toán sẽ tạo ra các giá trị đầu ra. Các giá trị đầu ra chính là nghiệm của bài toán.
-- Tính dừng: Sau một số hữu hạn bước thuật toán phải dừng.
-- Tính xác định: Ở mỗi bước, các bước thao tác phải hết sức rõ ràng, không gây nên sự nhập nhằng. Nói rõ hơn, trong cùng một điều kiện hai bộ xử lý cùng thực hiện một bước của thuật toán phải cho những kết quả như nhau.
-- Tính hiệu quả: Trước hết thuật toán cần đúng đắn, nghĩa là sau khi đưa dữ liệu vào
thuật toán hoạt động và đưa ra kết quả như ý muốn.
-- Tính phổ dụng: Thuật toán có thể giải bất kỳ một bài toán nào trong lớp các bài toán. Cụ thể là thuật toán có thể có các đầu vào là các bộ dữ liệu khác nhau trong một miền xác định.