tailieunhanh - Luận văn Thạc sĩ Khoa học: Một số phương pháp chứng minh tính đúng của thuật toán và ứng dụng

Để đánh giá một thuật toán là tốt có rất nhiều tiêu chí trong đó không thể bỏ qua tính đúng của thuật toán. Và đây cũng là nội dung chính của luận văn này theo đề tài nghiên cứu: “Một số phương pháp chứng minh tính đúng của thuật toán và ứng dụng”. Luận văn nhằm tìm hiểu, nghiên cứu, tổng hợp phương pháp chứng minh tính đúng của thuật toán. | Để kiểm tra tính đúng đắn của thuật toán chúng ta có thể cài đặt thuật toán đó và cho thực hiện trên máy với một số bộ dữ liệu mẫu rồi lấy kết quả thu được so sánh với kết quả đã biết. Có thể phải có rất nhiều bộ dữ liệu vào với kích cỡ khác nhau mới kiểm tra được hết các trường hợp của bài toán đặt ra nhưng cũng có khả năng người lập trình không phát hiện ra hết các trường hợp. Thực ra thì cách làm này không chắc chắn bởi vì có thể thuật toán đúng với tất cả các bộ dữ liệu chúng ta đã thử nhưng lại sai với một bộ dữ liệu nào đó. Do đó với chiến lược này là tương đối dễ thực hiện nhưng lại không thể phát hiện hết các lỗi tiểm ẩn. Vả lại cách làm này chỉ phát hiện ra thuật toán sai chứ chưa chứng minh được là nó đúng. Tính đúng đắn của thuật toán cần phải được chứng minh bằng toán học. Tuy nhiên kiểm thử vẫn được sử dụng phổ biến cho các chương trình trong thực tế, vì các chương trình lớn khó có thể chứng minh hoàn toàn bằng toán học. Hiện nay, trong công nghệ phần mềm công đoạn kiểm thử là bắt buộc.