CHƯƠNG 6: KĨ THUẬT LẬP TRÌNH

BÀI 22: KIỂM THỬ VÀ ĐÁNH GIÁ CHƯƠNG TRÌNH

( 11 câu)

1. NHẬN BIẾT (5 câ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?

Trả lờ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.

Câu 2: 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:

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

Câu 3: Nêu ý nghĩa của việc 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 trong việc đánh giá độ tin cậy và chứng minh tính đúng của chương trình

Trả lời:

Tạo các bộ dữ liệu kiểm thử để kiểm tra dữ liệu đầu ra: Phương pháp này giúp đánh giá tính chính xác của dữ liệu đầu ra của chương trình. Bằng cách tạo ra các bộ dữ liệu kiểm thử đa dạng và phong phú, ta có thể đảm bảo rằng 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. Nếu chương trình không đáp ứng được kết quả mong đợi trên các bộ dữ liệu kiểm thử, ta có thể suy ra rằng chương trình chưa hoạt động chính xác hoặc có thể chứa các lỗi còn chưa được phát hiện.

Câu 4: Nêu ý nghĩa của việc 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. trong việc đánh giá độ tin cậy và chứng minh tính đúng của chương trình

Trả lời:

Thiết lập điểm dừng hoặc kiểm tra từng lệnh của chương trình: Phương pháp này giúp 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. Bằng cách dừng chương trình ở các điểm kiểm tra hoặc theo dõi từng lệnh, ta có thể 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.

Câu 5: Nêu ý nghĩa của việc 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ó). trong việc đánh giá độ tin cậy và chứng minh tính đúng của chương trình

Trả lời:

Thực hiện in dữ liệu trung gian trong quá trình kiểm thử: Phương pháp này giúp theo dõi dữ liệu giữa các bước trong quá trình kiểm thử. Bằng cách in ra dữ liệu trung gian, ta có 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ó. Điều này giúp đảm bảo tính đúng đắn của kết quả của chương trình trong quá trình kiểm thử.

2. THÔNG HIỂU ( 2 câu)

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:

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?

Trả lờ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

3. VẬN DỤNG (3 câu)

Câu 1: Quan sát chương trình mô tả thuật toán sắp xếp chèn. Hãy đư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.

def InsertionSort(A,n):

for i in range(1,n):

value = A[i]

k = i-1

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

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

A[k+1] = A[k]

k = k 1

A[k+1] = value

Trả lời:

- 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, nếu thử được cảng nhiều bộ dữ liệu kiểm thử thi độ tin cậy của chương trình cảng cao.
- Trao đổi 2 là một suy luận logic vì nó bắt nguồn từ ý tưởng chính của thuật toán sắp xếp chèn. Đây là một 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.
- 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 2: 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?

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

S =

for i in range(n+1):

S = S + i

print(S)

Trả lời:

Chương trình trên đú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.

def dem(n):

count = 0

k = 2

while k<n:

if n%k == 0:

count = count + 1

k = k + 1

          return count

Trả lời:

Chương trình trên đúng.

4. VẬN DỤNG CAO ( 1 câu)

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ả 1ìm kiếm ở câu a.

Trả lời:

a) import time

A = [3, 1, 0, 10, 13, 16, 9, 7, 5, 11]

C = 9

start_time = time.time()

found = False

for num in A:

    if num == C:

        found = True

        break

end_time = time.time()

execution_time = end_time - start_time

if found:

    print("Phần tử", C, "được tìm thấy trong dãy.")

else:

    print("Phần tử", C, "không có trong dãy.")

print("Thời gian thực hiện tìm kiếm:", execution_time, "giây.")

b) import time

A = [4, 3, 5, 7, 8, 10, 11, 13, 16]

C = 9

start_time = time.time()

low = 0

high = len(A) - 1

found = False

while low <= high:

    mid = (low + high) // 2

    if A[mid] == C:

        found = True

        break

    elif A[mid] < C:

        low = mid + 1

    else:

        high = mid - 1

end_time = time.time()

execution_time = end_time - start_time

if found:

    print("Phần tử", C, "được tìm thấy trong dãy.")

else:

    print("Phần tử", C, "không có trong dãy.")

print("Thời gian thực hiện tìm kiếm nhị phân:", execution_time, "giây.")