Chủ đề 6. Kĩ thuật lập trình – Bài 23. Kiểm thử và đánh giá chương trình – sách giáo khoa trang 106 lớp 11 Khoa học máy tính – Kết Nối Tri Thức, mời các em tham khảo cùng Bumbii.
Chủ đề 6. Kĩ thuật lập trình – Bài 23. Kiểm thử và đánh giá chương trình
Khởi động
Trong các bài trước em đã học cách thiết kế thuật toán cho một số bài toán như bài toán tìm kiếm, bài toán sắp xếp và thiết lập chương trình thực hiện thuật toán đó. Một bài toán có nhiều thuật toán khác nhau và do đó có thể có nhiều chương trình khác nhau cùng giải quyết một bài toán. 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?
Lời giải:
– Dựa vào hai yếu tố là thời gian thực hiện thuật toán (còn gọi là độ phức tạp thuật toán) và dung lượng bộ nhớ cần thiết để lưu trữ dữ liệu.
– Thuật toán tối ưu là sử dụng ít thời gian, ít bộ nhớ, ít phép toán, giải bài toán trên máy tính thường được tiến hành qua 5 bước xác định bài toán, lựa chọn hoặc thiết kế thuật toán, viết chương trình, hiệu chỉnh và viết tài liệu.
1. Vai trò của kiểm thử chương trình
Hoạt động 1
Ở 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ó).
Lời giải:
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. Nếu phát hiện lỗi không chính xác của dữ liệu đầu ra thì kết luận ngay thuật toán và chương trình không đúng. Nếu với các bộ dữ liệu kiểm thử, dữ liệu đầu ra đều đúng thì điều đó chưa chứng minh được thuật toán hay chương trình đúng. Kết quả đó chỉ làm tăng khả năng đúng của chương trình.
Mục đích của các phương pháp 2 và 3 là tìm ra lỗi và sửa lỗi của chương trình. Như vậy, với việc tìm ra và sửa lỗi chứng tỏ chương trình trở nên tin cậy hơn, tốt 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.
Một thuật toán nếu được thiết kế đúng thì với mọi bộ dữ liệu đầu vào sẽ nhận được bộ dữ liệu đầu ra đúng tương ứng. Các phương pháp kiểm thử không có tính năng chứng minh được tính đúng của một thuật toán.
Câu hỏi
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?
Lời giải:
Dựa trên việc kiểm thử với 10 bộ dữ liệu và tất cả các kết quả đều đúng, em có thể có một sự đánh giá tích cực về độ tin cậy của chương trình, nhưng không thể kết luận chắc chắn rằng chương trình đó đã hoàn toàn đúng.
Lý do là vì 10 bộ dữ liệu kiểm thử không đủ lớn và đa dạng để đảm bảo tính đúng đắn của chương trình trên mọi trường hợp có thể xảy ra trong thực tế. Có thể vẫn tồn tại các trường hợp đặc biệt hoặc dữ liệu đầu vào ngoại lệ mà chương trình chưa xử lý đúng, dẫn đến lỗi ở những bộ dữ liệu khác.
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 đúng, 1 lần sai. Chương trình đó là sai hay đúng?
Lời giải:
Dựa trên kết quả của 10 bộ dữ liệu kiểm thử, với 9 lần đúng và 1 lần sai, không thể kết luận chương trình đó là đúng hoặc sai một cách chắc chắn. Kết quả này chỉ cho thấy chương trình có khả năng hoạt động chính xác trên hầu hết các trường hợp, nhưng vẫn có một trường hợp đặc biệt nào đó mà chương trình không xử lý đúng.
Việc phát hiện được một lỗi trong 1 lần kiểm thử không đồng nghĩa với việc chương trình đó là sai. Có thể có nhiều nguyên nhân dẫn đến kết quả sai trong lần kiểm thử đó, chẳng hạn như dữ liệu đầu vào đặc biệt, điều kiện biên, hay một vấn đề trong việc cấu hình môi trường kiểm thử.
Vì vậy, để đưa ra đánh giá chính xác về tính đúng của chương trình, cần phải tiếp tục kiểm thử với nhiều bộ dữ liệu kiểm thử khác nhau, đánh giá kết quả và phân tích sâu hơn về nguyên nhân của lỗi nếu có. Sau đó, cần tiến hành sửa chữa lỗi và thực hiện kiểm thử lại để đảm bảo tính đúng đắn của chương trình trước khi có thể kết luận chương trình là đúng hoặc sai.
2. Kiểm tra tính đúng của chương trình
Hoạt động 2
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.
Lời giải:
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â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 sau có đúng không?
Lời giải:
Chương trình này làm việc đúng và sẽ cho kết quả đúng nếu người dùng nhập một số tự nhiên n. Chương trình sẽ tính tổng từ 1 đến n bằng cách sử dụng vòng lặp for và sau đó in kết quả ra màn hình.
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 sau đúng hay sai.
Lời giải:
Chương trình đúng. Sử dụng một vòng lặp để kiểm tra các số từ 2 đến n-1 xem chúng có phải là ước số của n hay không. Nếu có, nó tăng biến count lên 1. Sau khi kiểm tra tất cả các số từ 2 đến n-1, chương trình trả về giá trị của count, tức là số lượng ước số thực sự của n.
3. Đánh giá hiệu quả chương trình
Hoạt động 3
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.
Lời giải:
1. Độ phức tạp thời gian (time complexity) được xác định là thời gian thực hiện chương trình thuật toán. Thời gian này phụ thuộc vào khối lượng của dữ liệu cần phải lưu trữ trong quá trình thực hiện chương trình thuật toán, đặc biệt liên quan tới các bước giải quyết một vấn đề cụ thể đưa ra trong chương trình/thuật toán.
2. Độ phức tạp không gian (space complexity) đượ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.
3. Một chương trình thuật toán là hiệu quả (efficient) nếu độ phức tạp của thuật toán này là thấp, nghĩa là tốn ít thời gian và tốn ít bộ nhớ cần thiết để thực hiện chương trình thuật toán. 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.
Câu hỏi
Hai tiêu chỉ đánh giá độ phức tạp tính toán quan trọng nhất là gì?
Lời giải:
1. Độ phức tạp thời gian (time complexity) được xác định là thời gian thực hiện chương trình thuật toán. Thời gian này phụ thuộc vào khối lượng của dữ liệu cần phải lưu trữ trong quá trình thực hiện chương trình thuật toán, đặc biệt liên quan tới các bước giải quyết một vấn đề cụ thể đưa ra trong chương trình/thuật toán.
2. Độ phức tạp không gian (space complexity) đượ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.
Luyện tập
Câu 1. Hãy 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.
Lời giải:
Dưới đây là một số bộ dữ liệu kiểm thử đề tìm lỗi cho chương trình tính n!:
- Số nguyên dương: n = 5 Kết quả mong đợi: 5! = 120
- Số nguyên âm: n = -3 Kết quả mong đợi: Lỗi – Số nguyên dương được yêu cầu
- Số 0: n = 0 Kết quả mong đợi: Lỗi – Số nguyên dương được yêu cầu
- Số nguyên lớn: n = 10 Kết quả mong đợi: 10! = 3628800
- Số chẵn: n = 6 Kết quả mong đợi: 6! = 720
- Số lẻ: n = 7 Kết quả mong đợi: 7! = 5040
- Số nguyên tối đa: n = 12 Kết quả mong đợi: 12! = 479001600
- Số nguyên tối thiểu: n = 1 Kết quả mong đợi: 1! = 1
- Số nguyên dương lớn nhất: n = 999 Kết quả mong đợi: Kết quả chưa đúng do số quá lớn vượt quá giới hạn của kiểu dữ liệu int
- Số nhập không phải số nguyên: n = “abc” Kết quả mong đợi: Lỗi – Số nguyên dương được yêu cầu
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. 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.
Lời giải:
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 có thể là:
– Bộ dữ liệu 1: A = [2, 4, 6, 8, 10] # Có 5 phần tử Kết quả mong đợi: Tổng các số chẵn là 30
– Bộ dữ liệu 2: A = [1, 3, 5, 7, 9] # Có 5 phần tử Kết quả mong đợi: Tổng các số chẵn là 0
Trong trường hợp này, cả hai bộ dữ liệu đều có cùng kích thước là 5 phần tử, nhưng thời gian chạy của thuật toán sẽ khác nhau vì số lượng số chẵn trong dãy số khác nhau. Bộ dữ liệu 1 chứa toàn số chẵn nên thời gian chạy của thuật toán sẽ lớn hơn bộ dữ liệu 2 chỉ chứa các số lẻ.
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 này.
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ả tìm kiếm ở câu a.
Lời giải:
a) Sử dụng time.time() để lấy thời gian hiện tại.
import time
A = [3, 1, 0, 10, 13, 16, 9, 7, 5, 11]
C = 9
start_time = time.time()
found = False
for i in range(len(A)):
if A[i] == C:
found = True
break
end_time = time.time()
elapsed_time = end_time - start_time
if found:
print(f"Phần tử {C} được tìm thấy trong dãy A.")
else:
print(f"Phần tử {C} không có trong dãy A.")
print(f"Thời gian thực hiện: {elapsed_time} giây")Kết quả chương trình:
Phần tử 9 được tìm thấy trong dãy A.
Thời gian thực hiện: 4.0531158447265625e-06 giâyb) Giả sử dãy A đã được sắp xếp theo thứ tự tăng dần, có thể sử dụng thuật toán tìm kiếm nhị phân để tìm phần tử C = 9.
import time
A = [0, 1, 3, 5, 7, 9, 10, 11, 13, 16]
C = 9
start_time = time.time()
found = False
left = 0
right = len(A) - 1
while left <= right:
mid = (left + right) // 2
if A[mid] == C:
found = True
break
elif A[mid] < C:
left = mid + 1
else:
right = mid - 1
end_time = time.time()
elapsed_time = end_time - start_time
if found:
print(f"Phần tử {C} được tìm thấy trong dãy A.")
else:
print(f"Phần tử {C} không có trong dãy A.")
print(f"Thời gian thực hiện: {elapsed_time} giây")Kết quả chương trình:
Phần tử 9 được tìm thấy trong dãy A.
Thời gian thực hiện: 3.0994415283203125e-06 giâyCâ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, 11]
- Sắp xếp chèn (Insertion Sort):
import time
def insertion_sort(arr):
n = len(arr)
for i in range(1, n):
key = arr[i]
j = i - 1
while j >= 0 and key < arr[j]:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
A = [3, 1, 0, 10, 13, 16, 9, 7, 5, 11]
start_time = time.time()
insertion_sort(A)
end_time = time.time()
elapsed_time = end_time - start_time
print("Dãy sau khi sắp xếp chèn:", A)
print(f"Thời gian thực hiện sắp xếp chèn: {elapsed_time} giây")Kết quả chương trình:
Dãy sau khi sắp xếp chèn: [0, 1, 3, 5, 7, 9, 10, 11, 13, 16]
Thời gian thực hiện sắp xếp chèn: 1.1205673217773438e-05 giây2. Sắp xếp chọn (Selection Sort):
import time
def selection_sort(arr):
n = len(arr)
for i in range(n):
min_idx = i
for j in range(i + 1, n):
if arr[j] < arr[min_idx]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i]
A = [3, 1, 0, 10, 13, 16, 9, 7, 5, 11]
start_time = time.time()
selection_sort(A)
end_time = time.time()
elapsed_time = end_time - start_time
print("Dãy sau khi sắp xếp chọn:", A)
print(f"Thời gian thực hiện sắp xếp chọn: {elapsed_time} giây")Kết quả chương trình:
Dãy sau khi sắp xếp chọn: [0, 1, 3, 5, 7, 9, 10, 11, 13, 16]
Thời gian thực hiện sắp xếp chọn: 9.059906005859375e-06 giây3. Sắp xếp nổi bọt (Bubble Sort):
import time
def bubble_sort(arr):
n = len(arr)
for i in range(n):
swapped = False
for j in range(0, n - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
swapped = True
if not swapped:
break
A = [3, 1, 0, 10, 13, 16, 9, 7, 5, 11]
start_time = time.time()
bubble_sort(A)
end_time = time.time()
elapsed_time = end_time - start_time
print("Dãy sau khi sắp xếp nổi bọt:", A)
print(f"Thời gian thực hiện sắp xếp nổi bọt: {elapsed_time} giây")Kết quả chương trình:
Dãy sau khi sắp xếp nổi bọt: [0, 1, 3, 5, 7, 9, 10, 11, 13, 16]
Thời gian thực hiện sắp xếp nổi bọt: 1.6927719116210938e-05 giâyXem các bài giải khác: Giải bài tập SGK lớp 11 định hướng Khoa học máy tính – NXB Kết nối tri thức với cuộc sống
Thông tin liên hệ & mạng xã hội:
Website: https://bumbii.com/
Facebook: https://www.facebook.com/bumbiiapp
Pinterest: https://www.pinterest.com/bumbiitech
