CHƯƠNG 1. CÔNG CỤ ĐỂ PHÂN TÍCH VÀ THIẾT KẾ THUẬT TOÁN
1.1. THUẬT TOÁN VÀ CÁC TÍNH CHẤT CỦA NÓ
Sử dụng thuật toán không phải chỉ bắt đầu từ khi xuất hiện máy tính. Loài người đã sử dụng những thuật toán từ rất lâu để giải một cách hệ thống các bài toán. Một cách hình thức, một thuật toán có thể được mô tả như một dãy hữu hạn những quy tắc để giải một bài toán. Còn định nghĩa chính xác và đầy đủ của thuật toán phải dùng khái niệm máy Turing. Định nghĩa sau đây đủ cho mục đích của tài liệu này.
Định nghĩa 1.1. Thuật toán là một thủ tục đầy đủ và từng bước cho việc giải một bài toán cụ thể. Mỗi bước phải thể hiện rõ ràng theo thuật ngữ một số hữu hạn quy tắc và đảm bảo kết thúc trong một số hữu hạn lẫn áp dụng của những quy tắc này. Một quy tắc đặc thù là sự thực hiện một hoặc nhiều phép toán.
Để mô tả thuật toán người ta có rất nhiều cách thể hiện nhằm mục đích dễ hiểu cho người đọc và dễ dàng thực hiện chúng trong thực tế, đặc biệt là trong máy tính. Có ba cách cơ bản mô tả thuật toán:
1. Mô tả bằng lời, liệt kê theo từng bước và các phép thực hiện của thuật toán. Cách này thường dài và cồng kềnh khi nhiều người cùng quan tâm tới thuật toán, mặt khác vì không có chuẩn mực nên rất dễ dẫn đến hiểu sai. Nhưng cách này thích hợp cho việc mô tả và nghiên cứu một thuật toán.
2. Mô tả thuật toán bằng sơ đồ khối. Hiện tại có một số loại sơ đồ khối mô tả thuật toán rất thuận lợi, trực quan và rất gọn. Nhưng với những thuật toán lớn, phức tạp thì nó không đáp ứng được những yêu cầu của người phân tích hệ thống.
3. Mô tả thuật toán bằng giả mã. Đây là cách tối ưu cho người nghiên cứu thuật toán và thiết kế thuật toán. Bằng cách này ngôn ngữ mô tả tự nhiên như ở cách 1, mặt khác rất gần với các ngôn ngữ lập trình bậc cao để thể hiện thuật toán. Với cấu trúc của giả mã ta cũng dễ phân tích, chứng minh tính đúng đắn, tìm được độ phức tạp và thiết kế được thuật toán.
Trong tài liệu này ta dùng bộ giả mã được mô tả dưới đây.
1.1.1. Giả mã mô tả thuật toán
Bộ giả mã là một tập hợp những từ khóa và một số những cú pháp gần với ngôn ngữ tự nhiên để mô tả thuật toán. Với bộ giả mã trong tài liệu này, ta chọn những từ khóa gần giống với ngôn ngữ lập trình Pascal.
Những thuật toán được thực hiện như một chương trình con, nó được thể hiện bằng một trong hai hình thức: Những hàm function và thủ tục procedure. Trong trường hợp hàm số, giá trị trả về sau khi thực hiện hàm được thực hiện bằng lệnh return. Thông tin được chuyển cho dạng như sau : hàm và thủ tục bằng đối thông số tương ứng. Một thủ tục thường có
