Bài giảng Phân tích thiết kế và đánh giá thuật toán

1. Thuật toán (giải thuật) - Algorithm 1.1. Định nghĩa thuật toán

Có rất nhiều các định nghĩa cũng như cách phát biểu khác nhau về định nghĩa của thuật toán. Theo như cuốn sách giáo khoa nổi tiếng viết về thuật toán là “Introduction to Algorithms" (Second Edition của Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest và Chifford Stein) thì thuật toán được định nghĩa như sau: “một thuật toán là một thủ tục tính toán xác định (well-defined) nhận các giá trị hoặc một tập các giá trị gọi iput và sinh ra ra một vài giá trị hoặc một tập giá trị được gọi là output”.

Nói một cách khác các thuật toán giống như là các cách thức, qui trình để hoàn thành một công việc cụ thể xác định (wel-defined) nào đó. Vì thế một đoạn mã chương trình tỉnh các phần tử của dãy số Fibonaci là một cài đặt của một thuật toán cụ thể. Thậm chí một hàm đơn giản để cộng hai số cũng à một thuật toán hoàn chỉnh, mặc dù đó là một thuật toán đơn glän

1.2. Đặc trưng của thuật toán

Tinh đúng đắn: Thuật toán cần phải đảm bảo cho một kết quả đúng sau khi thực hiện đối với các bộ dữ liệu đầu vào. Đây có thể nói là đặc trưng quan trọng nhất đối với một thuật toán. | Tinh dừng thuật toán cần phải đảm bảo sẽ dừng sau một số hữu hạn bước.

Tính xác định: Các bước của thuật toán phải được phát biểu rõ ràng, cụ thể, tránh gây nhập nhằng hoặc nhầm lẫn đối với người đọc và hiểu, cài đặt thuật toán.

Tinh hiệu quả: thuật toán được xem là hiệu quả nếu như nó có khả năng giải quyết hiệu quả bài toán đặt ra trong thời gian hoặc các điều kiện cho phép trên thực tế đáp ứng được yêu cầu của người dùng.

Tinh phổ quát: thuật toán được gọi là có tính phổ quát (phổ biến) nếu nó có thể giải quyết được một lớp các bài toán tương tự.

Ngoài ra mỗi thuật toán theo định nghĩa đều nhận các giá trị đầu vào được gọi chung là các giá trị dữ liệu Input. Kết quả của thuật toán (thường là một kết quả cụ thể nào đó tùy theo các bài toán và thuật toán cụ thể) được gọi là Output.

2. Biểu diễn thuật toán

Thường có hai cách biểu diễn một thuật toán, cách thứ nhất là mô tả các bước thực hiện của thuật toán, cách thứ hai là sử dụng sơ đồ giải thuật.

2.1. Mô tả các bước thực hiện

Để biểu diễn thuật toán người ta mô tả chính xác các bước thực hiện của thuật toán ngôn ngữ dùng để mô tả trật toàn có thể là ngôn ngữ tự nhiên hoặc một ngôn ngữ hi ghép giữa ngôn ngữ tự nhiên với một ngôn ngữ lập trình nào đó gọi là các đoạn giả mã lệnh