Chủ đề 6. Kĩ thuật lập trình – Bài 23: Kiểm thử và đánh giá chương trình – sách bài tập trang 73 lớp 11 Khoa học máy tính – Kết Nối Tri Thức, mời các em tham khảo cùng Bumbii.
Chủ đề 6. Kĩ thuật lập trình – Bài 23: Kiểm thử và đánh giá chương trình
Câu 23.1
Mệnh đề sau có đúng không?
Muốn chứng minh một chương trình chạy đúng chỉ cần thực hiện thật nhiều việc kiểm thử (test). Nếu kiểm tra trên tất cả các bộ dữ liệu kiểm thử đều đúng thì chương trình đúng.
Trả lời:
Mệnh đề sau không đúng. Việc kiểm thử không thể kiểm tra tất cả các trường hợp có thể xảy ra, và một lỗi nhỏ có thể dẫn đến sự cố lớn trong một số trường hợp đặc biệt.
Câu 23.2
Giả sử một chương trình đã được kiểm tra chạy chính xác với hơn 1000 lần test. Mệnh đề nào sau đây là đúng?
A. Chương trình đó hoàn toàn chính xác.
B. Chương trình đó chắc là sai ít đúng nhiều.
C. Chương trình đó có độ tin cậy cao.
D. Chưa thể nói gì được về chương trình đó.
Trả lời:
Đáp án C. Một chương trình đã được kiểm tra chạy chính xác với hơn 1000 lần test thì chương trình đó có độ tin cậy cao.
Câu 23.3
Để chứng minh một thuật toán là đúng cần phải làm gì? Chọn phương án đúng nhất trong các phương án sau:
A. Cần tiến hành kiểm thử chương trình cài đặt thuật toán, kiểm thử càng nhiều càng tốt.
B. Cần cài đặt thuật toán trên càng nhiều ngôn ngữ lập trình càng tốt.
C. Cần chạy thử chương trình cài đặt thuật toán xem thời gian chạy có nhanh hay không.
D. Cần chứng minh bằng toán học chặt chẽ tính đúng của thuật toán.
Trả lời:
Đáp án D. Chứng minh bằng toán học đảm bảo tính đúng của thuật toán trên mọi trường hợp, trong khi kiểm thử chỉ kiểm tra trên một số trường hợp cụ thể.
Câu 23.4
Cùng một chương trình, với hai bộ dữ liệu đầu vào khác nhau (cùng kích thước) thì thời gian chạy chương trình với hai bộ dữ liệu này sẽ giống nhau hay khác nhau?
Trả lời:
Thời gian chạy của cùng một chương trình với hai bộ dữ liệu đầu vào khác nhau có thể giống nhau hoặc khác nhau, tùy thuộc vào thuật toán và cách chương trình được cài đặt.
Câu 23.5
Với thuật toán sắp xếp chèn (trong sách giáo khoa), cùng kích thước n, thì bộ dữ liệu kiểm thử nào cho thời gian chạy.
a) Nhanh nhất?
b) Chậm nhất?
Trả lời:
a) Bộ dữ liệu là dãy đã sắp xếp đúng.
b) Bộ dữ liệu là dãy đã sắp xếp nhưng theo thứ tự ngược lại.
Câu 23.6
Trong các bài toán sau, kích thước đầu vào của bài toán là gì, được tính như thế nào?
a) Bài toán sắp xếp dãy số A theo thứ tự tăng dần.
b) Bài toán tính tổng 1+ 2 + … + n với n là số tự nhiên cho trước.
c) Bài toán tính gcd(a,b)—ước chung lớn nhất của hai số tự nhiên cho trước a, b.
Trả lời:
a) Chiều dài dãy A
b) Số n.
c) Số maximum trong 2 số a, b.
Câu 23.7
Viết chương trình thực hiện các việc sau:
– Nhập dãy số A từ bàn phím.
– Thực hiện các thuật toán sắp xếp chèn, sắp xếp chọn, sắp xếp nổi bọt trên dãy A.
– Tính thời gian chạy của từng thuật toán trên đối với dãy A, kết quả đưa ra màn hình.
Trả lời:
from time import perf_counter
A = [int(x) for x in input("Nhập dãy số nguyên: ").split()]
B, C, D = A.copy(), A.copy(), A.copy()
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]
t1 = perf_counter()
InsertionSort(B)
t2 = perf_counter()
print("Sắp xếp chèn:", t2 - t1)
t1 = perf_counter()
SelectionSort(C)
t2 = perf_counter()
print("Sắp xếp chọn:", t2 - t1)
t1 = perf_counter()
BubbleSort(D)
t2 = perf_counter()
print("Sắp xếp nổi bọt:", t2 - t1)Câu 23.8
Hàm sau tạo một dãy số nguyên có n phần tử và các giá trị nằm ngẫu nhiên nằm ngẫu nhiên trong phạm vi [a, b]
Em hãy viết chương trình tạo dãy A như trên với độ dài n và thực hiện các thuật toán sắp xếp chèn, sắp xếp chọn, sắp xếp nổi bọt trên dãy A. Sau đó tính thời gian chạy của các thuật toán này. Ghi lại bảng kết quả với các giá trị của n = 100, 1000, 10 000, 100 000.
Trả lời:
from time import perf_counter
from random import randint
def sinh_day(n, a, b):
A = [randint(a, b) for i in range(n)]
return A
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]
# Chương trình chính
n = 1000
A = sinh_day(n, 1, n // 2)
B, C, D = A.copy(), A.copy(), A.copy()
t1 = perf_counter()
InsertionSort(B)
t2 = perf_counter()
print("Sắp xếp chèn:", t2 - t1)
t1 = perf_counter()
SelectionSort(C)
t2 = perf_counter()
print("Sắp xếp chọn:", t2 - t1)
t1 = perf_counter()
BubbleSort(D)
t2 = perf_counter()
print("Sắp xếp nổi bọt:", t2 - t1)Nhận xét kết quả: Thời gian chạy ba thuật toán trên gần như tương đương nhau.
Câu 23.9*
Viết chương trình tạo dãy A có n phần tử với giá trị ngẫu nhiên. Sau đó tính thời gian chạy của lệnh sắp xếp A.sort( ) của Python và so sánh thời gian này với các thời gian chạy của các thuật toán em đã biết (xem Câu 23.8). Em có nhận xét gì về kết quả thu được?
Trả lời:
Nhận xét: Thời gian chạy sắp xếp theo phương thức sort() nhanh hơn hẳn ba thuật toán sắp xếp đã biết.
Ví dụ: với n = 10000, kết quả tính toán có thể như sau (tính theo giây).
1 Sắp xếp chèn: 10.774742899043896
2 Sắp xếp chọn: 10.29863730003126
3 Sắp xếp nổi bọt: 20.886252700118348
4 Sắp xếp Python: 0.0912119900311940908Xem các bài giải khác: Giải Sách Bài Tập Lớp 11 Khoa Học Máy Tính Kết Nối Tri Thức Với Cuộc Sống
Thông tin liên hệ & mạng xã hội:
Website: https://bumbii.com/
Facebook: https://www.facebook.com/bumbiiapp
Pinterest: https://www.pinterest.com/bumbiitech
