Hướng dẫn giải nhanh Tin học 11 định hướng Khoa học máy tính KNTT bài 23: Kiểm thử và đánh giá chương trình
Baivan.net sẽ đưa ra lời giải nhanh, ngắn gọn chuẩn xác môn tin học 11 định hướng Khoa học máy tính bộ sách kết nối tri thức và cuộc sống bài 23: Kiểm thử và đánh giá chương trình. Học sinh kéo xuống để tham khảo. Hi vọng đây sẽ là tài liệu hữu ích giúp các em đạt hiệu quả cao trong học tập
MỞ ĐẦU
Câu 1: 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?
Trả lời:
Dựa vào: thời gian thực hiện thuật toán (độ phức tạp thuật toán) và dung lượng bộ nhớ cần thiết để lưu trữ dữ liệ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
1. VAI TRÒ CỦA KIỂM THỬ CHƯƠNG TRÌNH
Hoạt động 1. Tìm hiểu ý nghĩa của kiểm thử chương trình
Câu 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:
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.
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.
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ả lời:
Giúp đánh giá tính chính xác của dữ liệu đầu ra của chương trình, đảm bảo chương trình hoạt động đúng trên nhiều trường hợp khác nhau, từ đó đánh giá được độ tin cậy của chương trình.
Kiểm tra từng bước thực thi của chương trình, từ đó giúp tìm ra các lỗi hoặc bug của chương trình, kiểm tra giá trị của các biến, xác nhận tính đúng đắn của các phép tính, kiểm tra điều kiện của các câu lệnh rẽ nhánh, v.v. Nếu phát hiện lỗi trong quá trình này, ta có thể xác định nguyên nhân và sửa chữa chúng.
Theo dõi dữ liệu giữa các bước trong quá trình kiểm thử, xác nhận tính đúng đắn của các giá trị được sử dụng trong chương trình, theo dõi dòng dữ liệu từ đầu vào đến đầu ra của chương trình, từ đó giúp phát hiện và sửa chữa lỗi nếu có.
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?
Trả lời:
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.
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?
Trả lời:
Không thể kết luận chương trình đó là đúng hoặc sai, 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 có một trường hợp đặc biệt 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 chương trình đó sai.
Để đưa ra đánh giá chính xác, cần 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 ĐẮN CỦA CHƯƠNG TRÌNH
Hoạt động 2. Tìm hiểu cách kiểm tra tính đúng của chương trình
Câu 1: 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.
Trả lời:
Trao đổi 1: chưa chứng minh được tính đúng của thuật toán và chương trình. Tuy nhiên, thử càng nhiều bộ dữ liệu kiểm thử, độ tin cậy của chương trình càng cao.
Trao đổi 2: là một suy luận lôgic vì nó bắt nguồn từ ý tưởng chính của thuật toán sắp xếp chèn.
Trao đổi 3: cho biết việc chứng minh tính đúng của chương trình thường 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.
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 trên có đúng không?
Trả lời:
Đúng.
Câu 3: 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. Chương trình trên đúng hay sai?
Trả lời:
Đúng.
3. ĐÁNH GIÁ HIỆU QUẢ CHƯƠNG TRÌNH
Câu 1: Hai tiêu chỉ đánh giá độ phức tạp tính toán quan trọng nhất là gì?
Trả lời:
Thời gian thực hiện và không gian bộ nhớ sử dụng.
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.
Trả lời:
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: Số quá lớn vượt quá giới hạn của kiểu dữ liệu int
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.
def tongchan(A):
s=0
for i in range(len(A)):
if A[i]%2==0:
s=s+A[i]
return s
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.
Trả lời:
Bộ 1: A = [2, 4, 6, 8, 10] # Có 5 phần tử Kết quả mong đợi: Tổng 30
Bộ 2: A = [1, 3, 5, 7, 9] # Có 5 phần tử Kết quả mong đợi: Tổng 0
Bộ dữ liệu 1 thời gian chạy của thuật toán sẽ lớn hơn bộ dữ liệu 2
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= [4,3,5,7,8, 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.
Trả lời:
Gán i = 0.
So sánh của A[i] và x:
Nếu A[i] = x, dừng và trả về giá trị của i (vị trí của x trong mảng A).
Nếu A[i] != x, sang bước 3.
Gán i = i + 1:
Nếu i = n (tức hết mảng), dừng lại và trả kết quả là -1 (không tìm thấy x).
Nếu i < n thì quay lại bước 2.
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].
Trả lời:
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 arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
# Dãy số nguyên đầu vào
A = [3, 1, 0, 10, 13, 16, 9, 7, 5, 1]
# In dãy số trước khi sắp xếp
print("Dãy số trước khi sắp xếp:", A)
# Đo thời gian thực hiện thuật toán
start_time = time.time()
# Gọi hàm sắp xếp chèn
insertion_sort(A)
# Kết thúc đo thời gian
end_time = time.time()
# In dãy số nguyên sau khi sắp xếp
print("Dãy số nguyên sau khi sắp xếp:", A)
# In thời gian thực hiện thuật toán
print("Thời gian thực hiện thuật toán: {:.6f} giây".format(end_time - start_time))
Thời gian thực hiện là 0 giây
Sắp xếp chọn:
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]
# Dãy số nguyên đầu vào
A = [3, 1, 0, 10, 13, 16, 9, 7, 5, 1]
# In dãy số trước khi sắp xếp
print("Dãy số nguyên trước khi sắp xếp:", A)
# Đo thời gian thực hiện thuật toán
start_time = time.time()
# Gọi hàm sắp xếp chọn
selection_sort(A)
# Kết thúc đo thời gian
end_time = time.time()
# In dãy số nguyên sau khi sắp xếp
print("Dãy số nguyên sau khi sắp xếp:", A)
# In thời gian thực hiện thuật toán
print("Thời gian thực hiện thuật toán: {:.6f} giây".format(end_time - start_time))
Thời gian thực hiện là: 0 giây
Sắp xếp nổi bọt:
import time
def bubble_sort(arr):
n = len(arr)
for i in range(n - 1):
for j in range(n - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
# Dãy số nguyên đầu vào
A = [3, 1, 0, 10, 13, 16, 9, 7, 5, 1]
# In dãy số nguyên trước khi sắp xếp
print("Dãy số nguyên trước khi sắp xếp:", A)
# Bắt đầu đo thời gian thực hiện thuật toán
start_time = time.time()
# Gọi hàm sắp xếp nổi bọt
bubble_sort(A)
# Kết thúc đo thời gian thực hiện thuật toán
end_time = time.time()
# In dãy số nguyên sau khi sắp xếp
print("Dãy số nguyên sau khi sắp xếp:", A)
# In thời gian thực hiện thuật toán
print("Thời gian thực hiện thuật toán: {:.6f} giây".format(end_time - start_time))
Thời gian thực hiện là: 0 giây