TAILIEUCHUNG - 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 . Giởi thiệu kiếm chúng thuật toán . 53 . Thuật toán hổi . Tính đúng của thuật toán hổi quy .56 . Tính đúng của thuật toán không hổi . Bài . 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ế .

• Toán học
• giáo trình đại học
• giáo trình về thuật toán
• cơ sở dữ liệu
• phương pháp giải mã thuật toán
• phân tích thuật toán
• Chương trình giáo dục đại học
• Giáo trình giáo dục đại học
• Giáo dục đại học
• Tiểu luận giáo dục học
• Thuyết trình giáo dục đại học
• Giáo dục đại học Việt Nam
• Giáo dục đại học thế giới
• Suy nghĩ về giáo trình Đại học
• Xây dựng giáo trình Đại học
• Việc xây dựng giáo trình Đại học
• Chất lượng giáo trình Đại học
• Nâng cao chất lượng giáo trình Đại học
• Giáo dục đại học ngoài công lập
• Giảng viên đại học ngoài công lập
• Sinh viên đại học ngoài công lập
• Đánh giá chất lượng giáo dục đại học
• Chất lượng giáo dục đại học
• Giáo trình Quản lý giáo dục đại học quân sự
• Quản lý giáo dục đại học quân sự
• Kế hoạch quản lý giáo dục đại học quân sự
• Mục tiêu quản lý giáo dục đại học quân sự
• Quá trình quản lý giáo dục đại học quân sự
• Phương pháp quản lý giáo dục đại học quân sự
• Đại học ngoài công lập
• Quản lý giáo dục đại học ngoài công lập
• Giáo dục đại học ngoài công lập Việt Nam
• Đại học công lập
• Giáo dục đại học công lập
• Hệ thống giáo dục đại học Việt Nam
• Chất lượng sinh viên
• Cải cách giáo dục
• Giáo dục Hoa Kỳ
• Giáo dục đại học Hoa Kỳ
• Đặc điểm giáo dục đại học Hoa Kỳ
• Tài chính giáo dục
• Tài chính giáo dục đại học
• Tài chính giáo dục đại học Việt Nam
• Hệ mục tiêu trong chương trình giáo dục đại học
• Mục tiêu chương trình giáo dục đại học Việt Nam
• Mục tiêu chương trình đào tạo bậc đại học Hoa kỳ
• Hệ mục tiêu chung cho chương trình giáo dục đại học
• Thông tư số 07 2015 TT BGDĐT
• Trình độ đào tạo giáo dục đại học
• Quy trình xây dựng trình độ đại học
• Quy trình xây dựng trình độ thạc sĩ
• Quy trình xây dựng trình độ tiến sĩ
• Chuẩn đầu ra giáo dục đại học
• Thiết kế chương trình giáo dục đại học
• Mục tiêu giáo dục đại học
• Điều tra nhu cầu đào tạo
• Quy trình phát triển giáo dục đại học
• Giáo dục đại học Việt Nam và thế giới
• Đặc trưng giáo dục đại học
• Văn minh nông nghiệp
• Quản lý nhà trường đại học
• Quản lý giáo dục đại học
• Nghiên cứu khoa học trong giáo dục đại học
• Nghiên cứu khoa học
• Quản lý nguồn nhân lực giáo dục
• Quản lý nguồn nhân lực giáo dục đại học quân sự
• Quản lý cơ sở vật chất kỹ thuật giáo dục
• Quản lý chất lượng giáo dục đại học quân sự
• Giáo dục học đại cương
• Giáo trình giáo dục học đại cương 1
• Giáo dục học đại cương 1 phần 1
• Giáo dục học
• Giáo dục học là một khoa học
• Tâm lý giáo dục
• Đánh giá chất lượng giáo dục
• Chất lượng giáo dục
• Giáo dục ngoài công lập
• Giáo dục học đại cương 1 phần 2
• Giáo dục và sự phát triển nhân cách
• Giáo dục phổ thông Việt Nam
• Giáo dục phổ thông Phần Lan
• Giáo dục phổ thông
• Giáo dục Singapore
• Cấu trúc giáo dục Singapore
• Hệ thống giáo dục