I. Lý thuyết trọng tâm

1. Vai trò của kiểm thử chương trình

Khi viết xong một chương trình, làm sao biết nó có đúng hay không? Có ba phương pháp kiểm thử phổ biến:

Phương pháp 1 – Dùng bộ dữ liệu kiểm thử (test): Chuẩn bị nhiều bộ dữ liệu đầu vào, chạy chương trình rồi kiểm tra xem đầu ra có khớp với kết quả mong đợi không. Nếu phát hiện sai ở bất kỳ bộ nào → kết luận ngay chương trình có lỗi. Tuy nhiên, nếu tất cả các bộ test đều cho kết quả đúng, điều đó chưa chứng minh được chương trình đúng hoàn toàn – nó chỉ tăng độ tin cậy rằng chương trình có khả năng đúng. Thử được càng nhiều bộ test thì độ tin cậy càng cao.

Phương pháp 2 – Chạy từng bước (debug): Thiết lập điểm dừng hoặc cho chương trình chạy theo từng lệnh để theo dõi giá trị các biến, từ đó phát hiện và sửa lỗi (bug).

Phương pháp 3 – In dữ liệu trung gian: Thêm lệnh print() tại các vị trí quan trọng trong chương trình để hiển thị giá trị biến, giúp xác định chỗ phát sinh lỗi.

Phương pháp 2 và 3 giúp tìm và sửa lỗi, làm chương trình tin cậy hơn. Nhưng việc tìm ra lỗi và sửa được lỗi cũng không đồng nghĩa với việc chứng minh chương trình đúng với mọi trường hợp.

Kết luận quan trọng: Kiểm thử 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 chỉ được coi là đúng khi với mọi bộ dữ liệu đầu vào hợp lệ, nó đều cho ra kết quả đúng.

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

Vậy làm thế nào để thực sự chứng minh một thuật toán là đúng? Có ba cách tiếp cận từ đơn giản đến chặt chẽ:

Cách 1 – Kiểm thử bằng dữ liệu mẫu: Thử nhiều bộ dữ liệu, nếu kết quả đều đúng thì tăng niềm tin rằng thuật toán đúng. Đây là cách đơn giản nhất nhưng không phải là chứng minh.

Cách 2 – Lập luận logic từ ý tưởng thuật toán: Dựa trên ý tưởng cốt lõi của thuật toán để suy luận rằng nó cho kết quả đúng. Đây là cách lập luận đơn giản, thường được sử dụng.

Ví dụ với thuật toán sắp xếp chèn: Vòng lặp for i chạy từ 1 đến n − 1. Tại mỗi bước, phần tử A[i] được chèn vào đúng vị trí trong dãy con đã sắp xếp A[0], ..., A[i−1]. Do đó sau mỗi bước lặp, dãy con A[0], ..., A[i] luôn được sắp xếp đúng. Đến bước cuối (i = n − 1), toàn bộ dãy A đã được sắp xếp → thuật toán đúng.

Cách 3 – Chứng minh bằng toán học (bất biến vòng lặp): Trong khoa học máy tính, tính đúng của thuật toán được chứng minh chặt chẽ bằng logic toán học, thường sử dụng phương pháp quy nạp toán học kết hợp với khái niệm bất biến vòng lặp (loop invariant).

Bất biến vòng lặp là một mệnh đề luôn đúng trước và sau mỗi bước lặp. Nếu chứng minh được mệnh đề này đúng cho mọi bước lặp, thì khi vòng lặp kết thúc, ta kết luận thuật toán cho kết quả đúng.

Ví dụ: Với thuật toán sắp xếp chèn, bất biến vòng lặp là: “Sau bước lặp thứ i, dãy con A[0], A[1], …, A[i] đã được sắp xếp tăng dần.” Nếu chứng minh được mệnh đề này bằng quy nạp, áp dụng với i = n − 1 sẽ kết luận toàn bộ dãy đã sắp xếp đúng.

Kết luận: 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. Kiểm thử bằng dữ liệu mẫu chỉ tăng độ tin cậy, không thay thế được việc chứng minh.

3. Đánh giá hiệu quả chương trình

Một bài toán có thể có nhiều thuật toán khác nhau cùng giải quyết. Vậy làm sao đánh giá thuật toán nào tốt hơn? Câu trả lời nằm ở khái niệm độ phức tạp tính toán (computational complexity) – lượng tài nguyên cần thiết để thực hiện chương trình.

3.1. Hai tiêu chí chính

Độ phức tạp thời gian (time complexity): Đo lường thời gian thực hiện chương trình. Thời gian này phụ thuộc vào kích thước dữ liệu đầu vào và số lần thực hiện các phép toán/câu lệnh trong thuật toán. Đây là tiêu chí quan trọng nhất trong phạm vi kiến thức phổ thông.

Độ phức tạp không gian (space complexity): Đo lường lượng bộ nhớ mà chương trình sử dụng trong quá trình thực hiện.

Một chương trình được gọi là hiệu quả nếu tốn ít thời gian và ít bộ nhớ để hoàn thành công việc.

3.2. Các tiêu chí khác

Ngoài hai tiêu chí trên, khi đánh giá chương trình người ta còn xét đến: tính dễ hiểu, rõ ràng, ngắn gọn, dễ bảo trì, dễ cài đặt, dễ sử dụng lại. Với các bài toán đòi hỏi khối lượng tính toán lớn (kỹ thuật, nghiên cứu khoa học), độ phức tạp thời gian thấp là ưu tiên hàng đầu. Với các phần mềm chạy liên tục (dịch vụ trực tuyến), tính ổn định và dễ bảo trì lại quan trọng hơn.

3.3. Đo thời gian chạy bằng Python

Python cung cấp hàm perf_counter() trong module time để đo thời gian thực thi. Cách dùng: ghi nhận thời điểm trước và sau khi chạy đoạn code cần đo, rồi tính hiệu số.

from time import perf_counter

def InsertionSort(A):
    n = len(A)
    for i in range(1, n):
        value = A[i]
        j = i - 1
        while j >= 0 and A[j] > value:
            A[j + 1] = A[j]
            j = j - 1
        A[j + 1] = value

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

t1 = perf_counter()       # Ghi nhận thời điểm bắt đầu
InsertionSort(A)           # Chạy thuật toán
t2 = perf_counter()       # Ghi nhận thời điểm kết thúc

print("Thời gian chạy:", t2 - t1, "giây")

Giải thích: Hàm perf_counter() trả về thời gian hiện tại tính bằng giây (độ chính xác cao). Biến t1 lưu thời điểm trước khi sắp xếp, t2 lưu thời điểm sau. Hiệu t2 - t1 chính là thời gian thực thi của hàm InsertionSort(). Với dãy nhỏ, thời gian này rất bé (gần 0 giây); với dãy lớn hàng nghìn, hàng triệu phần tử, sự khác biệt giữa các thuật toán sẽ rõ rệt hơn.

II. Phương pháp giải các dạng bài tập

Dạng 1: Xây dựng bộ dữ liệu kiểm thử để tìm lỗi

Phương pháp: Để tìm lỗi hiệu quả, cần xây dựng các bộ test đa dạng bao gồm: trường hợp bình thường, trường hợp biên (giá trị nhỏ nhất, lớn nhất), và trường hợp đặc biệt (giá trị 0, số âm, dãy rỗng,…). Nếu phát hiện kết quả sai ở bộ test nào, từ đó phân tích ngược lại code để xác định lỗi.

Bài 1 (Luyện tập SGK). 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.

n = int(input("Nhập số n: "))
if n > 0:
    giaithua = 1
    for i in range(1, n + 1):
        giaithua = giaithua * i
    print(n, "giai thừa bằng:", giaithua)

Lời giải:

Xây dựng các bộ test:

Phân tích lỗi: Chương trình dùng điều kiện if n > 0, nên khi n = 0 chương trình không thực hiện gì – trong khi theo toán học, 0! = 1. Đây là lỗi logic: điều kiện đúng phải là if n >= 0. Ngoài ra, chương trình không xử lí trường hợp n âm – nên bổ sung thông báo nhập sai.

Chương trình sửa lỗi:

n = int(input("Nhập số n: "))
if n < 0:
    print("Lỗi: n phải là số nguyên không âm")
else:
    giaithua = 1
    for i in range(1, n + 1):
        giaithua = giaithua * i
    print(n, "giai thừa bằng:", giaithua)

Dạng 2: Phân tích thời gian chạy của thuật toán

Phương pháp: Thời gian chạy phụ thuộc vào số lần thực hiện các phép toán bên trong vòng lặp. Với cùng một thuật toán và cùng kích thước dữ liệu, dữ liệu đầu vào khác nhau có thể dẫn đến số phép toán khác nhau (trường hợp tốt nhất, xấu nhất).

Bài 2 (Luyện tập SGK). Xét hàm tính tổng các số chẵn của một dãy số:

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 nhưng có thời gian chạy khác nhau.

Lời giải:

Hai bộ dữ liệu cùng kích thước 6 phần tử:

• Bộ 1: A = [2, 4, 6, 8, 10, 12] – toàn số chẵn.
• Bộ 2: A = [1, 3, 5, 7, 9, 11] – toàn số lẻ.

Phân tích: Cả hai bộ đều chạy vòng for đúng 6 lần. Tuy nhiên:

• Với bộ 1, điều kiện A[i] % 2 == 0 luôn đúng → phép cộng S = S + A[i] thực hiện 6 lần.
• Với bộ 2, điều kiện A[i] % 2 == 0 luôn sai → phép cộng không thực hiện lần nào.

Vì vậy bộ 1 thực hiện nhiều phép toán hơn bộ 2, dẫn đến thời gian chạy dài hơn (dù sự khác biệt rất nhỏ với dãy ngắn, nhưng sẽ rõ rệt hơn với dãy lớn).

Dạng 3: So sánh thời gian tìm kiếm tuần tự và nhị phân

Phương pháp: Dùng perf_counter() để đo thời gian thực thi của mỗi thuật toán trên cùng dữ liệu, rồi so sánh.

Bài 3 (Vận dụng SGK). Cho dãy A = [3, 1, 0, 10, 13, 16, 9, 7, 5, 11].

a) Viết chương trình tìm kiếm tuần tự phần tử C = 9. Tính thời gian thực hiện.

b) Giả sử dãy đã sắp xếp 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 phần tử C = 9. Tính thời gian và so sánh với câu a.

Lời giải:

from time import perf_counter

# --- Câu a: Tìm kiếm tuần tự ---
def LinearSearch(A, K):
    for i in range(len(A)):
        if A[i] == K:
            return i
    return -1

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

t1 = perf_counter()
kq1 = LinearSearch(A1, C)
t2 = perf_counter()

print("=== Tìm kiếm tuần tự ===")
if kq1 == -1:
    print("Không tìm thấy")
else:
    print(f"Tìm thấy {C} tại chỉ số {kq1}")
print(f"Thời gian: {t2 - t1} giây")

# --- Câu b: Tìm kiếm nhị phân ---
def BinarySearch(A, K):
    left = 0
    right = len(A) - 1
    while left <= right:
        mid = (left + right) // 2
        if A[mid] == K:
            return mid
        elif A[mid] < K:
            left = mid + 1
        else:
            right = mid - 1
    return -1

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

t3 = perf_counter()
kq2 = BinarySearch(A2, C)
t4 = perf_counter()

print("\n=== Tìm kiếm nhị phân ===")
if kq2 == -1:
    print("Không tìm thấy")
else:
    print(f"Tìm thấy {C} tại chỉ số {kq2}")
print(f"Thời gian: {t4 - t3} giây")

Giải thích:

• Tìm kiếm tuần tự trên dãy chưa sắp xếp: phần tử 9 nằm tại chỉ số 6, phải duyệt qua 7 phần tử mới tìm thấy.
• Tìm kiếm nhị phân trên dãy đã sắp xếp: phần tử 9 nằm tại chỉ số 5, chỉ cần vài bước chia đôi.

Với dãy 10 phần tử, thời gian cả hai đều rất nhỏ nên khó thấy khác biệt. Nhưng nếu dãy có hàng triệu phần tử, tìm kiếm nhị phân sẽ nhanh hơn rất nhiều (tối đa khoảng 20 bước so với hàng triệu bước của tuần tự).

Dạng 4: Đo và so sánh thời gian các thuật toán sắp xếp

Bài 4 (Vận dụng SGK). Viết ba chương trình sắp xếp chèn, sắp xếp chọn, sắp xếp nổi bọt. Cho biết thời gian thực hiện với dãy A = [3, 1, 0, 10, 13, 16, 9, 7, 5, 11].

Lời giải:

from time import perf_counter

# --- Ba thuật toán sắp xếp ---
def InsertionSort(A):
    n = len(A)
    for i in range(1, n):
        value = A[i]
        j = i - 1
        while j >= 0 and A[j] > value:
            A[j + 1] = A[j]
            j = j - 1
        A[j + 1] = value

def SelectionSort(A):
    n = len(A)
    for i in range(n - 1):
        iMin = i
        for j in range(i + 1, n):
            if A[j] < A[iMin]:
                iMin = j
        A[i], A[iMin] = A[iMin], A[i]

def BubbleSort(A):
    n = len(A)
    for i in range(n - 1):
        for j in range(n - 1 - i):
            if A[j] > A[j + 1]:
                A[j], A[j + 1] = A[j + 1], A[j]

# --- Đo thời gian ---
day_goc = [3, 1, 0, 10, 13, 16, 9, 7, 5, 11]

# Sắp xếp chèn
A1 = day_goc.copy()
t1 = perf_counter()
InsertionSort(A1)
t2 = perf_counter()
print(f"Sắp xếp chèn:    {t2 - t1:.10f} giây | Kết quả: {A1}")

# Sắp xếp chọn
A2 = day_goc.copy()
t3 = perf_counter()
SelectionSort(A2)
t4 = perf_counter()
print(f"Sắp xếp chọn:    {t4 - t3:.10f} giây | Kết quả: {A2}")

# Sắp xếp nổi bọt
A3 = day_goc.copy()
t5 = perf_counter()
BubbleSort(A3)
t6 = perf_counter()
print(f"Sắp xếp nổi bọt: {t6 - t5:.10f} giây | Kết quả: {A3}")

Giải thích: Dùng day_goc.copy() để tạo bản sao cho mỗi thuật toán (vì sắp xếp tại chỗ sẽ thay đổi dãy). Định dạng :.10f in thời gian với 10 chữ số thập phân để thấy rõ sự khác biệt dù rất nhỏ. Với dãy 10 phần tử, cả ba thuật toán đều chạy gần như tức thì. Sự khác biệt rõ rệt hơn khi thử với dãy lớn hàng nghìn phần tử.

III. Sơ đồ tư duy

                              ┌─ PP1: Bộ dữ liệu test → tăng độ tin cậy
  ┌─ Kiểm thử chương trình ──┼─ PP2: Chạy từng bước (debug) → tìm lỗi
  │                           ├─ PP3: In dữ liệu trung gian → tìm lỗi
  │                           └─ ⚠ Chưa chứng minh được tính đúng
  │
  │                           ┌─ Cách 1: Test nhiều bộ dữ liệu (chưa đủ)
  ├─ Kiểm tra tính đúng ─────┼─ Cách 2: Lập luận logic từ ý tưởng thuật toán
  │                           └─ Cách 3: Chứng minh toán học
  │                                      (bất biến vòng lặp + quy nạp)
  │
  │                           ┌─ Độ phức tạp thời gian (quan trọng nhất)
  │                           │    → số phép toán/câu lệnh thực hiện
  └─ Đánh giá hiệu quả ──────┼─ Độ phức tạp không gian
                              │    → lượng bộ nhớ sử dụng
                              ├─ Tiêu chí khác: dễ hiểu, dễ bảo trì,...
                              └─ Đo thời gian: perf_counter()

Thầy Phạm Thành Danh

(Người kiểm duyệt, ra đề)

Chức vụ: Trưởng ban biên soạn môn Tin Học THPT

Trình độ: Cử nhân Sư phạm Tin học, Chứng chỉ hạng II, Chứng chỉ Tin học, Ngoại ngữ B1

Kinh nghiệm: 8+ năm kinh nghiệm tại Trường THPT Thuận Hóa