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

PHẦN I. HỆ THỐNG CÂU HỎI, BÀI TẬP TRONG SGK

KHỞI ĐỘNG

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? 

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ó)

Câu hỏi 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 hỏi 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 ĐẮN 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.

Câu hỏi 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?

Câu hỏi 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. Chương trình trên đúng hay sai?

3. ĐÁNH GIÁ HIỆU QUẢ 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ì?

LUYỆN TẬP

Luyện tập 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.

Luyện tập 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.

VẬN DỤNG

Vận dụng 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 ở CH a.

Vận dụng 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].

PHẦN II. 5 PHÚT TRẢ LỜI CÂU HỎI, BÀI TẬP SGK

KHỞI ĐỘNG

Đáp án KD:

Dựa vào hai yếu tố là thời gian thực hiện 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.

1.VAI TRÒ CỦA KIỂM THỬ CHƯƠNG TRÌNH

Đáp án HD1: 

1. Giúp đánh giá tính chính xác của dữ liệu đầu ra của chương trình. 

2. Giúp kiểm tra từng bước thực thi của chương trình. 

3. Giúp theo dõi dữ liệu giữa các bước trong quá trình kiểm thử. 

Đáp án CH1: 

Không thể 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ế. 

Đáp án CH2: 

Không thể kết luận đúng hoặc sai. 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.

2. KIỂM TRA TÍNH ĐÚNG ĐẮN CỦA CHƯƠNG TRÌNH

Đáp án HD2: 

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ử thì độ tin cậy của chương trình càng cao.

Đáp án CH1: 

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

Đáp án CH2: 

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

3. ĐÁNH GIÁ HIỆU QUẢ CHƯƠNG TRÌNH

Đáp án CH: 

Hai tiêu chí là thời gian thực hiện và không gian bộ nhớ sử dụng. 

LUYỆN TẬP

Đáp án LT1: 

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

Đáp án LT2: 

• 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

VẬN DỤNG

Đáp án VD1:

1. Gán i = 0.

2. So sánh giá trị của A[i] và x:

   • Nếu A[i] == x thì dừng và trả về giá trị của i (vị trí của x trong mảng A).

   • Nếu A[i] != x thì sang bước 3.

3. Gán i = i + 1:

   • Nếu i == n (tức hết mảng) thì 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.

Đáp án VD2:

• Thuật toán 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 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ố 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 chèn

insertion_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

• Thuật toán 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ố 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 chọn

selection_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

• Thuật toán 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