Đang chuẩn bị liên kết để tải về tài liệu:
Giáo trình - Một số vấn đề về thuật toán - chương 2

Chương 2: Tính đúng đắn của thuật toán Giới thiệu kiểm chứng thuật toán Giả sử chúng ta đã thiết kế được một thuật toán và đưa nó vào chương trình để thể hiện nó. Ta có thể tin được rằng tuật toán có đưa ra lời giải đúng hay không? | ChươNq2 TÍNH ĐÚNG ĐẮN củ A THUẬT TOÁN 2.1. Giởi thiệu kiếm chúng thuật toán . 53 2.2. Thuật toán hổi quy.55 2.3. Tính đúng của thuật toán hổi quy .56 2.4. Tính đúng của thuật toán không hổi quỵ.60 2.5. Bài tập.66 2.1. GIỚI THIỆU KIÊM CHÚNG THUẬT TOÁN Giả sử chúng ta đã thiết kê được một thuật toán và đưa nó vào chương trình để thể hiện nó. Ta có thể tin được rằng thuật toán có đưa ra lời giải đúng hay không Không tính sai sót về mặt cú pháp khi thuật toán đã thể hiện được những kết quả khác nhau khi ta cho những mẫu đầu vào để thử. Tuy vậy với các mẫu đã cho chương trình cho kết quả đúng đi chăng nữa thì thuật toan cụng còn tiềm tàng những lời giải sai. Như vậỳ ta phải chứng minh đửợc kết qua cua thuẩt toán cho đầu ra luôn luôn đúng. Những phương pháp lụận đã được xây dựng để chứng minh tính đúng đắn của thuật toán khi có đầu vào đúng và kết quả đầu ra phải là đúng. Thường có hai phương pháp lôgíc để kiểm tra thuật toán hoặc chương trình đúng hay không đó là kiểm thử testing và chứng minh tính đúng đắn Correctness proof . Kiểm thử thuật toán là thử thuật toán vởìnhững mẩu đầu vào. Chứng minh tính đúng đắn là chứng minh theo toán học. Việc kiểm thử thuật toán tiềm ẩn những lỗi không ngờ tới. Chỉ dùng kiểm thử nhiều khi rất nguy hiểm cho việc triển khai nhiều thuật toán với nhau. 54 Chương 2. Tính đủng đắn của thuật toán Khi đó những lỏi trong các thuật toán khác nhau sẽ kết hợp làm cho ta khá bốỉ rối không biết chính xác chương trình hoạt động thế nào Chứng minh tính đúng đắn của thuật toán cũng nhiều khi còn có lỗi vì vậy ta phải kết hợp cầ hai. Một thuật toán thế nào là đúng đán Ta có thể định nghĩa như sau Một thuật toán được gọi là đúng tỉđn nếu với mọi đầu vào chấp nhận được nó cho đầu ra đúng. Việc chứng minh tính đúng đắn của thuật toán bao gồm hai phần 1. Ta phải chỉ ra ràng thuật toán kết thúc thì nhận được kết quả đúng. Phần này người ta thường gọi là xác minh tính đúng đắn bộ phận của thuật toán. 2. Chứng tỏ thuật toán luôn ỉuón kết thúc. Để định rõ thế .