Câu hỏi mở đầu trang 106

Đề bài: Một bài toán có thể 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:

• Làm thế nào để biết thuật toán nào tốt nhất? Cần kiểm thử chương trình để kiểm tra tính đúng đắn, sau đó đánh giá hiệu quả dựa trên thời gian chạy và bộ nhớ sử dụng.
• Các tiêu chí đánh giá tính tối ưu:
  • Độ phức tạp thời gian (thời gian chạy).
  • Độ phức tạp không gian (bộ nhớ sử dụng).
  • Tính đúng đắn của thuật toán.
  • Tính dễ hiểu, dễ cài đặt, dễ bảo trì.

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

Hoạt động 1 trang 106

Đề bài: Ở 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:

→ Kết luận chung: Cả 3 phương pháp đều không chứng minh được tính đúng của thuật toán, chỉ giúp tăng độ tin cậy của chương trình.

Câu hỏi củng cố mục 1 trang 107

Đề bà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?

Lời giải:

Chưa thể kết luận chương trình đúng.

Giải thích: Kiểm thử với 10 bộ dữ liệu chỉ chứng tỏ chương trình chạy đúng với 10 bộ đó, có thể vẫn còn bộ dữ liệu khác làm chương trình chạy sai. Kiểm thử chỉ tăng độ tin cậy, không chứng minh được tính đúng của thuật toán.

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:

Chương trình đó chắc chắn sai.

Giải thích: Chỉ cần một bộ dữ liệu cho kết quả sai là đủ kết luận chương trình có lỗi, dù các bộ khác đều đúng.

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

Hoạt động 2 trang 107

Đề bài: 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:

Có 3 cách kiểm tra tính đúng, theo mức độ chặt chẽ tăng dần:

Trao đổi 1 – Dùng bộ dữ liệu kiểm thử:

• Nhập các bộ dữ liệu đầu vào bất kì, chạy chương trình rồi kiểm tra kết quả đầu ra.
• Nếu tất cả các bộ đều cho kết quả đúng → tăng độ tin cậy, chưa chứng minh được tính đúng của thuật toán.

Trao đổi 2 – Lập luận logic theo ý tưởng thuật toán:

• Dòng lệnh 2 là vòng lặp gồm n – 1 bước, với i chạy từ 1 đến n – 1.
• Mỗi bước i, các dòng lệnh 3 – 9 chèn A[i] vào đúng vị trí trong dãy con A[0], A[1], …, A[i-1] đã sắp xếp.
• Do đó sau bước cuối cùng, dãy A được sắp xếp theo thứ tự tăng dần.
• Đây là cách lập luận đơn giản, thường dùng để chứng minh tính đúng.

Trao đổi 3 – Chứng minh bằng lập luận toán học (bất biến vòng lặp):

• Chứng minh mệnh đề: “Sau mỗi bước lặp i, dãy con A[0], A[1], …, A[i] đã được sắp xếp đúng theo thứ tự tăng dần” bằng phương pháp quy nạp toán học.
• Áp dụng với i = n – 1 → kết luận thuật toán đúng.
• Đây là cách tốt nhất để chứng minh chặt chẽ tính đúng của thuật toán.

Câu hỏi củng cố mục 2 trang 108

Đề bà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?

n = int(input("Nhập số tự nhiên n: "))
S = 0
for i in range(n+1):
    S = S + i
print(S)

Lời giải:

Chương trình đúng.

Giải thích:

• range(n+1) sinh ra dãy 0, 1, 2, …, n.
• Vòng lặp cộng dồn tất cả các số i vào S, tức là: S = 0 + 1 + 2 + … + n.
• Kết quả in ra chính là 1 + 2 + … + n (vì cộng thêm 0 không ảnh hưởng đến tổng).

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 là đú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

Lời giải:

Chương trình đúng với định nghĩa: ước số thực sự của n là các số chia hết cho n, khác 1 và khác chính n.

Giải thích:

• Biến k chạy từ 2 đến n – 1 (nhờ điều kiện k < n), tức là bỏ qua giá trị 1 và n.
• Nếu k là ước của n (tức n % k == 0) thì tăng biến đếm.
• Cuối cùng trả về số các ước thực sự tìm được.

Ví dụ: với n = 12, chương trình đếm được các ước 2, 3, 4, 6 → trả về 4.

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

Hoạt động 3 trang 108

Đề bài: 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ớ.
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.
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 đơn giản, rõ ràng, dễ hiểu và áp dụng.

Lời giải:

Cả 3 tiêu chí đều có ý nghĩa, không có tiêu chí nào tuyệt đối quan trọng nhất. Việc chọn tiêu chí ưu tiên tùy thuộc vào bài toán cụ thể:

• Với bài toán kỹ thuật, khoa học (xử lý dữ liệu lớn): ưu tiên thời gian chạy nhanh.
• Với chương trình chạy liên tục (dịch vụ trực tuyến): ưu tiên độ tin cậy, dễ cài đặt, dễ bảo trì.
• Với chương trình chạy trên thiết bị bộ nhớ hạn chế: ưu tiên tiết kiệm bộ nhớ.

→ Trong phạm vi phổ thông, ta chủ yếu quan tâm đến độ phức tạp thời gian của chương trình.

Câu hỏi củng cố mục 3 trang 110

Đề bà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:

Hai tiêu chí đó là:

1. Độ phức tạp thời gian (time complexity): là thời gian cần thiết để thực hiện chương trình/thuật toán.
2. Độ phức tạp không gian (space complexity): là dung lượng bộ nhớ cần dùng để thực hiện chương trình/thuật toán.

Luyện tập

Luyện tập trang 110

Đề bài:

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.

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 thua bang:", giaithua)

Lời giải:

Bảng các bộ dữ liệu kiểm thử:

→ Hai bộ dữ liệu tìm ra lỗi: n = 0 (do điều kiện if n > 0 bỏ qua) và n âm (không có xử lý).

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.

def tongchan(A):
    S = 0
    for i in range(len(A)):
        if A[i] % 2 == 0:
            S = S + A[i]
    return S

Lời giải:

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

• Bộ 1: A = [1, 3, 5, 7, 9] → toàn số lẻ, không có phép cộng nào được thực hiện.
• Bộ 2: A = [2, 4, 6, 8, 10] → toàn số chẵn, thực hiện 5 phép cộng.

→ Cùng kích thước nhưng bộ 2 chạy chậm hơn bộ 1 vì phải thực hiện nhiều phép cộng hơn.

Vận dụng

Vận dụng trang 110

Đề bài:

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.

Lời giải:

Dãy chưa sắp xếp → dùng tìm kiếm tuần tự.

from time import perf_counter

def LinearSearch(A, K):
    for i in range(len(A)):
        if A[i] == K:
            return i
    return -1

A = [3, 1, 0, 10, 13, 16, 9, 7, 5, 11]
t1 = perf_counter()
kq = LinearSearch(A, 9)
t2 = perf_counter()
print("Chỉ số tìm được:", kq)
print("Thời gian:", t2 - t1, "giây")

Giải thích:

• Hàm LinearSearch duyệt lần lượt từng phần tử, khi gặp giá trị bằng K thì trả về chỉ số.
• Dùng perf_counter() đo thời điểm trước và sau khi tìm kiếm, hiệu số là thời gian chạy.
• Với dãy trên, phần tử 9 nằm ở chỉ số 6.

b) Giả sử dãy A đã đượ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 phần tử C = 9 theo thuật toán tìm kiếm nhị phân. Tính 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:

from time import perf_counter

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

A = [0, 1, 3, 5, 7, 9, 10, 11, 13, 16]
t1 = perf_counter()
kq = BinarySearch(A, 9)
t2 = perf_counter()
print("Chỉ số tìm được:", kq)
print("Thời gian:", t2 - t1, "giây")

Giải thích:

• Trong dãy đã sắp xếp, phần tử 9 nằm ở chỉ số 5.
• Tìm kiếm nhị phân chỉ cần vài bước (khoảng 2–3 bước) để tìm ra kết quả.

So sánh câu a và câu b:

→ Tìm kiếm nhị phân nhanh hơn tìm kiếm tuần tự khi dãy đã sắp xếp (dù trên dãy nhỏ, sự chênh lệch không nhiề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 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].

Lời giải:

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

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]

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

# Sắp xếp chèn
A1 = A.copy()
t1 = perf_counter()
InsertionSort(A1)
t2 = perf_counter()
print("Sắp xếp chèn:", A1, "- Thời gian:", t2 - t1)

# Sắp xếp chọn
A2 = A.copy()
t1 = perf_counter()
SelectionSort(A2)
t2 = perf_counter()
print("Sắp xếp chọn:", A2, "- Thời gian:", t2 - t1)

# Sắp xếp nổi bọt
A3 = A.copy()
t1 = perf_counter()
BubbleSort(A3)
t2 = perf_counter()
print("Sắp xếp nổi bọt:", A3, "- Thời gian:", t2 - t1)

Giải thích:

• Dùng A.copy() để mỗi thuật toán sắp xếp trên bản sao độc lập của dãy A, tránh ảnh hưởng lẫn nhau.
• Đo thời gian chạy bằng perf_counter() tại thời điểm trước và sau khi gọi hàm.
• Dãy kết quả sau sắp xếp: [0, 1, 3, 5, 7, 9, 10, 11, 13, 16].

Nhận xét: Với dãy nhỏ 10 phần tử, thời gian chạy của 3 thuật toán chênh lệch không đáng kể (khoảng phần triệu giây). Sự khác biệt sẽ thể hiện rõ hơn với dãy lớn.

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