Soạn mới giáo án Khoa học máy tính 11 kết nối tri thức bài 23: Kiểm thử và đánh giá chương trình

HOẠT ĐỘNG CỦA GV VÀ HS

SẢN PHẨM DỰ KIẾN

Bước 1: GV chuyển giao nhiệm vụ:

- GV đặt vấn đề theo Hoạt động 1 trang 106 SGK: Ở lớp 10, em đã học một số phương pháp 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ó).

- Trên cơ sở kiến thức vừa nêu, GV yêu cầu HS nêu ý nghĩa của kiểm thử chương trình.

- Dựa vào ví dụ vừa nêu ở Hoạt động 1, GV yêu cầu HS trả lời câu hỏi củng cố trang 107 SGK:

+ Câu 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?

+ Câu 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, 1 lần sai. Chương trình đó là sai hay đúng?

Bước 2: HS thực hiện nhiệm vụ học tập:

- HS thảo luận nhóm, đọc SGK và trả lời câu hỏi.

Bước 3: Báo cáo kết quả hoạt động, thảo luận:

- Đại diện nhóm HS trình bày.

*Câu hỏi củng cố trang 107 SGK:

+ Câu 1: Chưa thể kết luận chương trình đó đúng hay sai.

+ Câu 2: Có thể kết luận ngay chương trình đó là sai.

- Các nhóm khác nhận xét, bổ sung cho nhóm bạn.

Bước 4: Đánh giá kết quả thực hiện:

- GV nhận xét, đánh giá kết quả thảo luận của HS.

1. Vai trò của kiểm thử chương trì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.

- Một thuật toán đúng chỉ có thể được chứng minh là đúng bằng các công cụ toán học (và khoa học máy tính), còn kiểm thử bằng các bộ test sẽ không được coi là phương pháp chứng minh tính đúng của thuật toán, mà chỉ là biện pháp làm tăng độ tin cậy của chương trình.

HOẠT ĐỘNG CỦA GV VÀ HS

SẢN PHẨM DỰ KIẾN

Bước 1: GV chuyển giao nhiệm vụ:

- GV đặt vấn đề theo Hoạt động 2 trang 107 SGK: 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.

- GV giới thiệu với HS 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.

- GV chia lớp thành 6 nhóm và giao nhiệm vụ cho các nhóm:

+ Nhóm 1,4: Tìm hiểu và thực hiện Trao đổi 1. Thực hiện kiểm thử chương trình thông qua các bộ test, ghi kết quả xem đúng hay sai, yêu cầu kiểm thử càng nhiều càng tốt.

+ Nhóm 2,5: Tìm hiểu và thực hiện Trao đổi 2. Chứng minh thuật toán trên là đúng.

+ Nhóm 3,6: Tìm hiểu và thực hiện Trao đổi 3. Chứng minh tính đúng của thuật toán bằng lí luận toán học.

- Sau thời gian thảo luận, GV yêu cầu các nhóm báo cáo kết quả thảo luận và nêu ý kiến xem cách nào là phương pháp đúng nhất để chứng minh tính đúng của thuật toán.

- Dựa vào nội dung vừa nêu, GV yêu cầu HS trả lời câu hỏi củng cố trang 108 SGK:

+ 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.

1 n = int(input("Nhập số tự nhiên n: "))

2 S = 0

3 for i in range(n+1):

4    S = S + i

5 print(S)

Chương trình trên có đúng không?

+ Câu 2: Chương trình sau giải bài toán đếm số các ước số thực sự của số tự nhiên n.

1 def dem(n):

2     count = 0

3     k = 2

4     while k < n:

5         if n%k ==0:

6             count = count + 1

7         k = k + 1

8      return count

Chương trình trên là đúng hay sai?

Bước 2: HS thực hiện nhiệm vụ học tập:

- HS thảo luận nhóm, đọc SGK và trả lời câu hỏi.

Bước 3: Báo cáo kết quả hoạt động, thảo luận:

- Đại diện nhóm HS trình bày.

*Câu hỏi củng cố trang 108 SGK:

+ Câu 1: Chương trình trên đúng.

+ Câu 2: Chương trình sai vì chưa tính số 1.

- Các nhóm khác nhận xét, bổ sung cho nhóm bạn.

Bước 4: Đánh giá kết quả thực hiện:

- GV nhận xét, đánh giá kết quả thảo luận của HS.

2. Kiểm tra tính đúng của chương trình

- 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ư sau:

1 def InsertionSort(A,n):

2   for i in range(1,n):

3      value = A[i]

4      k = i – 1

5      #di chuyển các phần tử A[k] > value qua phải

6      while k >= 0 and A[k] > value

7        A[k+1] = A[k]

8        k = k – 1

9      A[k+1] = value

- 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.

HOẠT ĐỘNG CỦA GV VÀ HS

SẢN PHẨM DỰ KIẾN

Bước 1: GV chuyển giao nhiệm vụ :

- GV đặt về đề dựa vào nội dung Hoạt động 3 trang 108 SGK: 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.

- GV yêu cầu các nhóm thảo luận, nghiên cứu SGK để tìm hiểu về đánh giá hiệu quả chương trình và trả lời câu hỏi:

+ Hiệu quả hay tính tối ưu của chương trình được xem xét trên cơ sở nào?

- GV yêu cầu các nhóm thực hiện đoạn chương trình tính thời gian chạy cụ thể của chương trình mô tả thuật toán chèn theo SGK.

- GV chú ý: Thời gian chạy và không gian tính toán của thuật toán được kí hiệu là T(n) và S(n), trong đó n là kích thước đầu vào của bài toán. Nếu đầu vào là 1 dãy thì n là độ dài dãy đã cho.

- Trên cơ sở kiến thức vừa nêu, GV yêu cầu HS rút ra những tiêu chí đánh giá tính hiệu quả của chương trình.

- Dựa vào nội dung vừa nêu, GV yêu cầu HS trả lời câu hỏi củng cố trang 110 SGK:

+ Hai tiêu chí đánh giá độ phức tạp tính toán quan trọng nhất là gì?

Bước 2: HS thực hiện nhiệm vụ học tập:

- HS thảo luận nhóm, đọc SGK và trả lời câu hỏi.

Bước 3: Báo cáo kết quả hoạt động, thảo luận:

- Đại diện nhóm HS trình bày.

*Câu hỏi củng cố trang 110 SGK:

+ Hai tiêu chí đánh giá chính độ phức tạp thuật toán là thời gian T(n) và không gian bộ nhớ S(n).

- Các nhóm khác nhận xét, bổ sung cho nhóm bạn.

Bước 4: Đánh giá kết quả thực hiện:

- GV nhận xét, đánh giá kết quả thảo luận của HS.

- GV tổng kết kiến thức và yêu cầu HS ghi chép vào vở.

3. Đánh giá hiệu quả chương trì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. Hai loại độ phức tạp tính toán phổ biến nhất đó là:

+ Độ 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ức tạp không gian được xác định là tài nguyên của máy tính trong đó có phần bộ nhớ được sử dụng để thực hiện chương trình.

- Ngoài ra để đánh giá hiệu quả chương trình đôi khi người ta còn quan tâm tới các tiêu chí như tính dễ hiểu, rõ ràng, ngắn gọn, dễ bảo trì, dễ cài đặt,…của chương trình.

- Độ 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.