BÀI 23. KIỂM THỬ VÀ ĐÁNH GIÁ CHƯƠNG TRÌNH
Trang bìa
Trang bìa
Ảnh
TIN HỌC 11
BÀI 23. KIỂM THỬ VÀ ĐÁNH GIÁ CHƯƠNG TRÌNH
Ảnh
Mục tiêu bài học
Mục tiêu
Ảnh
Mục tiêu:
Biết được vai trò của kiểm thử làm tăng độ tin cậy của chương trình nhưng chưa chứng minh được tính đúng của chương trình. Biết được các tiêu chí đánh giá hiệu quả và tính đúng của chương trình.
Khởi động
Khởi động
Ảnh
- Khởi động:
Hãy thảo luận và trả lời các câu hỏi sau: - Làm thế nào để biết trong các thuật toán giải cùng một bài toán thì thuật toán nào là tốt nhất? - Có những tiêu chí nào để đánh giá tính "tối ưu" của một thuật toán?
Hình thành kiến thức
1. Vai trò của kiểm thử chương trình
Ảnh
1. Vai trò của kiểm thử chương trình
Em hãy thảo luận với các bạn về các phương pháp kiểm thử sau, nêu ý nghĩa của chúng trong việc đánh giá độ tin cậy và chứng minh tính đúng của chương trình: 1.Tạo các bộ dữ liệu kiểm thử (test) để kiểm tra dữ liệu đầu ra có chính xác hay không. 2.Thiết lập điểm dừng hoặc cho chương trình chạy theo từng lệnh để kiểm tra và tìm ra lỗi (bug) của chương trình. 3.Thực hiện in dữ liệu trung gian trong quá trình kiểm thử để tìm ra lỗi của chương trình (nếu có).
- HĐ1: Tìm hiểu ý nghĩa của kiểm thử chương trình
- Tìm hiểu
Ảnh
- Tìm hiểu:
Phương pháp 1: Sử dụng bộ dữ liệu kiểm thử để kiểm tra tính đúng của chương trình. Nếu phát hiện lỗi thì kết luận chương trình không đúng, nhưng nếu không có lỗi thì chưa chứng minh được tính đúng của chương trình. Mục đích của phương pháp 2 và 3 là tìm và sửa lỗi để tăng tính tin cậy của chương trình, nhưng không chứng minh được tính đúng của thuật toán và chương trình. Một thuật toán được thiết kế đúng sẽ cho ra kết quả đúng với mọi bộ dữ liệu đầu vào tương ứng. Phương pháp kiểm thử không có khả năng chứng minh tính đúng của một thuật toán.
- Ghi nhớ
- Ghi nhớ:
Ảnh
Kiểm thử sẽ giúp tăng độ tin cậy của chương trình nhưng chưa chứng minh được tính đúng của thuật toán và chương trình.
- Câu hỏi củng cố
Ảnh
- Câu hỏi củng cố:
1. Giả sử em thiết lập chương trình giải bài toán nào đó. Em đã kiếm thử với 10 bộ dữ liệu và tất cả các kết quả đều đúng. Khi đó có thể kết luận chương trình đó đúng hay chưa? 2. Giả sử một chương trình kiểm thử với 10 bộ dữ liệu cho kết quả 9 lần đúng, 1 lần sai. Chương trình đó là sai hay đúng?
2. Kiểm tra tính đúng của chương trình
2. Kiểm tra tính đúng của chương trình
- HĐ2: Tìm hiểu cách kiểm tra tính đúng của chương trình
Ảnh
Quan sát chương trình mô tả thuật toán sắp xếp chèn. Hãy thảo luận và đưa ra các lập luận để kiểm tra tính đúng của thuật toán sắp xếp chèn.
- Tìm hiểu
- Tìm hiểu:
Chương trình thực hiện thuật toán sắp xếp chèn để sắp xếp dãy A cho trước theo thứ tự tăng dần:
Ảnh
Ảnh
+ tiếp (- Tìm hiểu)
Ảnh
Phương pháp 1 sử dụng các bộ dữ liệu kiểm thử để kiểm tra tính đúng của chương trình. Tuy nhiên, việc kiểm tra với các bộ dữ liệu kiểm thử không chứng minh được tính đúng của thuật toán hay chương trình, chỉ làm tăng khả năng đúng của chương trình. Phương pháp 2 và 3 nhằm tìm và sửa lỗi của chương trình để chương trình trở nên tin cậy hơn. Tuy nhiên, điều đó không chứng minh được tính đúng của thuật toán và chương trình.
- Nhận xét
Ảnh
Trong trao đổi 1, việc sử dụng các bộ dữ liệu kiểm thử chưa chứng minh được tính đúng của thuật toán và chương trình. Tuy nhiên, việc thử nhiều bộ dữ liệu kiểm thử sẽ tăng độ tin cậy của chương trình. Trao đổi 2 là một luận điệu logic vì nó dựa trên ý tưởng chính của thuật toán sắp xếp chèn. Đây là cách lập luận đơn giản thường được sử dụng để chứng minh tính đúng của thuật toán. Trong trao đổi 3, việc chứng minh tính đúng của chương trình thường được thực hiện bằng lập luận toán học, sử dụng phương pháp quy nạp toán học. Đây là cách tốt nhất để chứng minh tính đúng của một thuật toán.
- Nhận xét:
- Ghi nhớ
- Ghi nhớ:
Ảnh
Tính đúng của thuật toán cần được chứng minh bằng lập luận toán học. Sử dụng các bộ dữ liệu kiểm thử có thể làm tăng độ tin cậy của chương trình nhưng chưa chứng minh được tính đúng của thuật toán.
- Câu hỏi củng cố
- Câu hỏi củng cố:
Câu 1: Chương trình sau giải bài toán: Yêu cầu nhập số tự nhiên n và tính tổng 1 + 2+… +n. Chương trình trên có đúng không?
Ảnh
Ảnh
+ tiếp (- Câu hỏi củng cố)
Câu 2: Chương trinh sau giải bài toán đếm số các ước số thực sự của số tự nhiên n. Chương trình trên đúng hay sai.
Ảnh
Ảnh
3. Đánh giá hiệu quả chương trình
Ảnh
3. Đánh giá hiệu quả chương trình
- HĐ3: Những TC đánh giá tính hiệu quả của chương trình
Thảo luận về các tiêu chí đánh giá tính hiệu quả của thuật toán hay chương trình giải một bài toán. 1. Tiêu chí quan trọng nhất là thời gian chạy chương trình phải nhanh, không cần quan tâm đến không gian bộ nhớ sử dụng của chương trình. 2. Tiêu chí tiết kiệm bộ nhớ là quan trọng nhất, sau đó mới đến thời gian chạy chương trình. 3. Các tiêu chí 1 và 2 không quan trọng mà quan trọng là chương trình được viết một cách đơn giản, rõ ràng, dễ hiểu và áp dụng.
- Tìm hiểu
Ảnh
- Tìm hiểu:
Độ phức tạp tính toán là lượng tài nguyên cần thiết để thực hiện chương trình, được sử dụng để đánh giá hiệu quả hoặc tính tối ưu của chương trình. Độ phức tạp thời gian được xác định là thời gian thực hiện chương trình/ thuật toán, phụ thuộc vào khối lượng dữ liệu cần xử lí và các bước giải quyết vấn đề. Độ phức tạp không gian là lượng bộ nhớ máy tính cần sử dụng để thực hiện chương trình/ thuật toán.
- Ghi nhớ
- Ghi nhớ:
Ảnh
Tính hiệu quả của chương trình/ thuật toán được xem xét trên cơ sở đánh giá độ phức tạp tính toán. Độ phức tạp tính toán quan trọng nhất là độ phức tạp thời gian có liên quan trực tiếp tới các câu lệnh được thực hiện trong chương trình/ thuật toán.
- Câu hỏi củng cố
Ảnh
- Câu hỏi củng cố:
Ảnh
Hai tiêu chỉ đánh giá độ phức tạp tính toán quan trọng nhất là gì?
Luyện tập
- Câu 1 (- Luyện tập)
- Luyện tập
Câu 1. Xây dựng các bộ dữ liệu kiểm thử đề tìm lỗi cho chương trình tính n! với n là một số nguyên dương nhập từ bàn phím.
Ảnh
Ảnh
- Câu 2 (- Luyện tập )
Câu 2: Xét hàm mô tả thuật toán tính tổng các số chẵn của một dãy số cho trước.
Ảnh
Ảnh
Tìm hai bộ dữ liệu đầu vào có cùng kích thước của thuật toán trên nhưng có thời gian chạy khác nhau.
Vận dụng
- Câu 1
Ảnh
- Vận dụng:
Câu 1: Cho dãy các số A = (3, 1, 0, 10, 13, 16, 9, 7, 5, 11]. a) Viết chương trình mô tả thuật toán tìm kiếm phần tử C = 9 của dãy trên. Tính thời gian chính xác thực hiện công việc tìm kiếm. b) Giả sử dây A ở trên đã được sắp xếp theo thứ tự tăng dần: A= [0,1,3,5,7,9,10,11,13, 16]. Viết chương trình tìm kiếm nhị phân để tìm kiếm phân tử C = 9, đo thời gian thực hiện thuật toán. So sánh với kết quả 1ìm kiếm ở câu a.
- Câu 2 (- Vận dụng)
Ảnh
Câu 2: Viết ba chương trình mô phỏng các thuật toán sắp xếp chèn, sắp xếp chọn và sắp xếp nổi bọt mà em đã biết. Cho biết thời gian thực tế thực hiện các chương trình trên với bộ dữ liệu đầu vào là dãy A = {3, 1, 0, 10, 13, 16, 9,7, 5, T1].
Dặn dò
Dặn dò
Ảnh
Dặn dò:
Ôn lại kiến thức vừa học. Làm bài tập trong SBT. Chuẩn bị bài sau: "Bài 24. Đánh giá độ phức tạp thời gian thuật toán".
Cảm ơn
Ảnh