Tin học 11 Kết nối tri thức bài 23 Khởi động
Câu hỏi: 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? Bài làm
- 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.
- 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.
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
Ở 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ó). Bài làm
1. 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.
2. 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.
3. 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ử.
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? Bài làm
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 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? Bài làm
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 để đả
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
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. Bài làm
- Trong trao đổi 1, việc sử dựng các bộ dữ liệu kiểm thử chưa chứng minh được tinh
đú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 trinh 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. Đâ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 tinh đúng của một thuật toá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? Bài làm
Chương trình trên đúng.
Câu hỏi 2. Chương trinh 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. Bài làm
Chương trình trên đúng.
3. Đánh giá hiệu quả chương trình
Hoạt động 3: Những tiêu chí đánh giá tính hiệu quả của chương trình
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ớ sử dụng của chương trì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 chương trình.
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 một
cách đơn giản, rõ ràng, dễ hiểu và áp dụng. Bài làm
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 có thể khác nhau tùy vào mục đích và yêu cầu của dự án hoặc ứng dụng cụ thể.
Dưới đây là một số thảo luận về các tiêu chí được đưa ra trong câu hỏi:
1. Tiêu chí thời gian chạy (runtime): Thời gian chạy của chương trình là một yếu tố
quan trọng trong đánh giá tính hiệu quả của thuật toán hay chương trình. Nếu
chương trình chạy nhanh, đáp ứng được yêu cầu về thời gian đối với ứng dụng cụ
thể, thì đây là một tiêu chí quan trọng để đánh giá tính hiệu quả của chương trình.
2. Tiêu chí tiết kiệm bộ nhớ: Việc sử dụng bộ nhớ của chương trình cũng là một yếu
tố quan trọng trong đánh giá tính hiệu quả của chương trình, đặc biệt là đối với các
ứng dụng có yêu cầu về tài nguyên hạn chế. Nếu chương trình sử dụng ít bộ nhớ và
đáp ứng được yêu cầu về tài nguyên, thì tiêu chí này cũng được coi là quan trọng.
3. Tiêu chí đơn giản, rõ ràng, dễ hiểu: Độ đơn giản, rõ ràng và dễ hiểu của chương
trình cũng là một yếu tố quan trọng trong đánh giá tính hiệu quả của chương trình,
đặc biệt là trong việc duy trì và phát triển sau này. Nếu chương trình được viết một
cách đơn giản, rõ ràng và dễ hiểu, thì nó sẽ dễ dàng trong việc duy trì, nâng cấp, và
áp dụng cho các tình huống khác nhau.
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ì? Bài làm
Hai tiêu chí đánh giá độ phức tạp tính toán quan trọng nhất là thời gian thực hiện và
không gian bộ nhớ sử dụng. Dựa trên dựa 2 tiêu chí này mà người lập trình và nhà
phát triển có thể tối ưu hóa chương trình để đạt được hiệu suất tốt nhất trong việc xử lý dữ liệu. Luyện tập
Câu hỏ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. Bài làm
Dưới đây là một số bộ dữ liệu kiểm thử đề tìm lỗi cho chương trình tính n!:
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
Những bộ dữ liệu này giúp kiểm thử chương trình với các trường hợp đặc biệt và
tiềm ẩn lỗi, như số âm, số 0, số nguyên tối đa, số nhập không phải số nguyên, giúp
đảm bảo tính đúng đắn và hoạt động ổn định của chương trình tính n!.
Câu hỏi 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. Bài là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 có thể là:
- 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
Trong trường hợp này, cả hai bộ dữ liệu đều có cùng kích thước là 5 phần tử, nhưng
thời gian chạy của thuật toán sẽ khác nhau vì số lượng số chẵn trong dãy số khác
nhau. Bộ dữ liệu 1 chứa toàn số chẵn nên thời gian chạy của thuật toán sẽ lớn hơn
bộ dữ liệu 2 chỉ chứa các số lẻ. Vận dụng
Câu hỏ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.
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. Bài làm Gợi ý: Gán i = 0.
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.
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.
Câu hỏi 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] Bài làm
*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
Document Outline

• Khởi động
• 1. Vai trò của kiểm thử chương trình
• 2. Kiểm tra tính đứng đắn của chương trình
• 3. Đánh giá hiệu quả chương trình
• Luyện tập
• Vận dụng