CHÀO MỪNG CẢ LỚP
ĐẾN VỚI BÀI HỌC HÔM NAY!

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?

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

NỘI DUNG BÀI HỌC
1

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

2

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

3

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

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

Nêu ý nghĩa của kiểm thử chương trình?

Kiểm thử sẽ 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.

Lưu ý

Một thuật toán đúng chỉ có thể được chứng minh là đúng
bằng các công cụ toán học (và khoa học máy tính), còn
kiểm thử bằng các bộ test sẽ không được coi là phương
pháp chứng minh tính đúng của thuật toán, mà chỉ là
biện pháp làm tăng độ tin cậy của chương trình.

Câu hỏi củng cố kiến thức (SGK - tr.107)
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ữ

Chưa thể

liệu và tất cả các kết quả đều đúng. Khi đó có

kết luận

thể kết luận chương trình đó đúng hay chưa?
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, 1 lần sai.
Chương trình đó là sai hay đúng?

Có thể kết
luận ngay
chương trình
đó là sai.

02
KIỂM TRA TÍNH ĐÚNG
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.

1 def InsertionSort(A,n):
2
for i in range(1,n):
3
value = A[i]
4
k = i – 1
5
#di chuyể
n các phầ
n tử A[k] > value qua
phải
6
while k >= 0 and A[k] > value:
7
A[k+1] = A[k]
8
k = k – 1
9
A[k+1] = value

Chia lớp thành 6 nhóm, thực hiện các nhiệm vụ sau:
 Nhóm 1, 4: Tìm hiểu và thực hiện Trao đổi 1. Thực hiện kiểm
thử chương trình thông qua các bộ test, ghi kết quả xem đúng
hay sai, yêu cầu kiểm thử càng nhiều càng tốt.
 Nhóm 2, 5: Tìm hiểu và thực hiện Trao đổi 2. Chứng minh
thuật toán trên là đúng.
 Nhóm 3, 6: Tìm hiểu và thực hiện Trao đổi 3. Chứng minh
tính đúng của thuật toán bằng lí luận toán học.

GHI NHỚ
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.
Sử dụng các bộ dữ liệu kiểm thử có
thể làm 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.

Câu hỏi củng cố kiến thức (SGK - tr.108)
Câu 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.
1
n = int(input("Nhập số tự nhiên n:
"))
2 S = 0
3 for i in range(n+1):
Chương trình
4
S = S + i
5 print(S)

Chương trình trên có đúng không?

đúng

Câu hỏi củng cố kiến thức (SGK - tr.108)
Câu 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.
1
2
3
4
5
6
7
8

def dem(n):
count = 0
k = 2
while k < n:
if n%k ==0:
count = count + 1
k = k + 1
return count

Chương trình trên đúng hay sai?

Chương trình sai
vì chưa tính số 1

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

Hoạt động 3:

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.

Hiệu quả hay tính tối ưu của chương trình
được xem xét trên cơ sở nào?

Tính hiệu quả của chương trình/
thuật toán được xem xét trên cơ sở
đánh giá độ phức tạp tính toán.

Hai loại độ phức tạp tính toán phổ biến nhất đó là:
Độ phức tạp thời gian: được xác
định là thời gian thực hiện chương
trình/thuật toán.
Độ phức tạp không gian: được
xác định là tài nguyên của máy tính
trong đó có phần bộ nhớ được sử
dụng để thực hiện chương trình.

Ngoài ra để đánh giá hiệu quả chương trình,
đôi khi còn cần quan tâm tới các tiêu chí như
tính dễ hiểu, rõ ràng, ngắn gọn, dễ bảo trì,
dễ cài đặt,…của chương trình.

Chú ý

Thời gian chạy và không gian tính toán của thuật
toán được kí hiệu là T(n) và S(n), trong đó n là kích
thước đầu vào của bài toán. Nếu đầu vào là 1 dãy
thì n là độ dài dãy đã cho.

GHI NHỚ
Tính hiệu quả của chương trình/ thuật toán được xem xét trên
cơ sở đánh giá độ phức tạp tính toán. Độ phức tạp tính toán
quan trọng nhất là độ phức tạp thời gian có liên quan trực tiếp
tới các câu lệnh được thực hiện trong chương trình/thuật toán.

Câu hỏi củng cố kiến thức (SGK - tr.110)
Hai tiêu chí đánh giá độ phức tạp tính toán quan trọng
nhất là gì?

Thời gian

Không gian

T(n)

bộ nhớ (Sn)

ĐƯỜNG LÊN ĐỈNH
OLYMPIA

1

Hiệu quả hay tính tối ưu của chương trình được xem
xét trên cơ sở đánh giá nào?
A. Đánh giá độ phức tạp tính toán
B. Đánh giá độ phức tạp thời gian
C. Đánh giá độ phức tạp không gian
D. Đánh giá độ phức tạp vị trí chương trình
ĐÁP ÁN

A
Answer

2

Chương trình chạy phát sinh lỗi ngoại lệ NameError, nên xử lí
như thế nào?
A. Kiểm tra lại chỉ số trong mảng
B. Kiểm tra kiểu dữ liệu nhập vào
C. Kiểm tra lại tên các biến và hàm
D. Viết lại chương trình
ĐÁP ÁN

C
Answer

3

Tính đúng của thuật toán cần được chứng minh bằng
A. Lập luận khoa học
B. Lập luận toán học
C. Lập luận tin học
D. Lập luận vật lí
ĐÁP ÁN

B
Answer

4

Để đánh giá hiệu quả chương trình, độ phức tạp tính
toán nào quan trọng nhất?
A. Chương trình dễ cài đặt
B. Chương trình dễ bảo trì
C. Độ phức tạp không gian
D. Độ phức tạp thời gian
ĐÁP ÁN

D
Answer

5

Độ phức tạp tính toán phổ biến gồm mấy loại?
A. 2

B. 3

C. 4

D. 5

ĐÁP ÁN

A
Answer

LUYỆN TẬP
Bài 1 (SGK - tr.110) 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.
1

n = int(input("Nhập sốn: "))

2

if n > 0:

chỉ là một số
tự nhiên bất kì

3

giaithua=1

4

for i in range(1,n+1):

5

Bộ kiểm thử

giaithua = giaithua*i

6
bằng:",giaithua)

print(n,"giai

thừa

Bài 2 (SGK-tr110) 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.
1

def tongchan(A):

Bộ n số chẵn

2

S = 0

3

for i in range(len(A)):

4

if A[i] % 2 == 0:

5
6

Bộ n số lẻ

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
Bài 1 (SGK-tr.110) Cho dãy các số A = [3, 1, 0, 10, 13, 16, 9, 7, 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 = [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.

Chương trình có thể như sau:

Chương trình có thể như sau:

Bài 2 (SGK - tr.110). 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].

Chương trình gộp tính
thời gian thực tế cho ba
thuật toán sắp xếp chèn,
sắp xếp chọn, sắp xếp nổi
bọt như sau:

Chương trình gộp tính
thời gian thực tế cho ba
thuật toán sắp xếp chèn,
sắp xếp chọn, sắp xếp nổi
bọt như sau:

HƯỚNG DẪN VỀ NHÀ
Ôn tập kiến thức đã học trong
bài

01

Hoàn thành bài tập trong SBT

02

Chuẩn bị bài sau - Bài 24

03

CẢM ƠN SỰ CHÚ Ý
LẮNG NGHE CỦA CÁC EM!