Tin học 11 Kết nối tri thức Bài 23: Kiểm thử và đánh giá chương trình

- Mục đích của phương pháp 2 và 3 là tìm và sửa lỗi để tăng tính tin cậy của chương trình, nhưng không chứng minh được tính đúng của thuật toán và chương trình.

- Một thuật toán được thiết kế đúng sẽ cho ra kết quả đúng với mọi bộ dữ liệu đầu vào tương ứng. Phương pháp kiểm thử không có khả năng chứng minh tính đúng của một thuật toán.

- Phương pháp 1 sử dụng các bộ dữ liệu kiểm thử để kiểm tra tính đúng của chương trình. Tuy nhiên, việc kiểm tra với các bộ dữ liệu kiểm thử không chứng minh được tính đúng của thuật toán hay chương trình, chỉ làm tăng khả năng đúng của chương trình.

- Phương pháp 2 và 3 nhằm tìm và sửa lỗi của chương trình để chương trình trở nên tin cậy hơn. Tuy nhiên, điều đó không chứng minh được tính đúng của thuật toán và chương trình.

- Việc chứng minh tính đúng của thuật toán đều phải dựa trên logic toán học. Bắt biến vòng lặp là một phương pháp thường được sử dụng. Ví dụ với thuật toán sắp xếp chèn, bằng bất biến vòng lặp, ta có thể chứng minh tính đúng của thuật toán.

Nhận xét:

- Trong trao đổi 1, việc sử dụng các bộ dữ liệu kiểm thử chưa chứng minh được tính đúng của thuật toán và chương trình. Tuy nhiên, việc thử nhiều bộ dữ liệu kiểm thử sẽ tăng độ tin cậy của chương trình.

- Trao đổi 2 là một luận điệu logic vì nó dựa trên ý tưởng chính của thuật toán sắp xếp chèn. Đây là 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.

- Trong trao đổi 3, việc chứng minh tính đúng của chương trình thường được thực hiện 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 tính đúng của một thuật toán.

- Độ phức tạp tính toán (computational complexity) là lượng tài nguyên (amounts of resources) cần thiết để thực hiện chương trình, được sử dụng để đánh giá hiệu quả hoặc tính tối ưu của chương trình.

- Độ phức tạp thời gian (time complexity) được xác định là thời gian thực hiện chương trình/thuật toán, phụ thuộc vào khối lượng dữ liệu cần xử lý và các bước giải quyết vấn đề.

- Độ phức tạp không gian (space complexity) là lượng bộ nhớ máy tính cần sử dụng để thực hiện chương trình/thuật toán.

- Một chương trình/thuật toán được coi là hiệu quả nếu độ phức tạp của nó thấp, tức là tốn ít thời gian và bộ nhớ cần thiết để thực hiện.

- 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 cũng được quan tâm trong đánh giá hiệu quả chương trình.

- Độ phức tạp thời gian của chương trình/thuật toán phụ thuộc vào số lần thực hiện các phép toán/câu lệnh trong chương trình/thuật toán. Đối với các bài toán kĩ thuật, thiết kế, nghiên cứu khoa học đòi hỏi khối lượng tính toán lớn, việc thiết kế chương trình/thuật toán có độ phức tạp thời gian thấp là mối quan tâm hàng đầu.

- Đối với các bài toán chạy liên tục như các dịch vụ trực tuyến thì tính dễ cài đặt, dễ duy trì và độ tin cậy của phần mềm cũng cỏ vai trò quan trọng.

- Trong phạm vi kiến thức phổ thông, ta chỉ quan tâm đến độ phức tạp thời gian của chương trình/thuật toán. Việc xác định độ phức tạp thời gian dựa trên ước lượng thời gian thực hiện các bước (câu lệnh) trong chương trình/thuật toán sẽ được trình bày trong các bài học sau.

Cho dãy các số B = [5, 2, 1, 9, 13, 12, 6, 8, 7, 15]. Hãy viết chương trình mô tả thuật toán tìm kiếm phần tử A = 5 của dãy trên?

Hướng dẫn giải:

import time

def linear_search(arr, x):

"""

Tìm kiếm tuyến tính trong dãy arr để tìm giá trị x.

Trả về vị trí của x trong dãy nếu x được tìm thấy, -1 nếu không tìm thấy.

"""

n = len(arr)

for i in range(n):

if arr[i] == x:

return i

return -1

# Dãy số B

B = [5, 2, 1, 9, 13, 12, 6, 8, 7, 15]

# Phần tử cần tìm kiếm

A = 5

if result != -1:

print(f"Phần tử {A} được tìm thấy tại vị trí {result} trong dãy B.")

else:

print(f"Phần tử {A} không có trong dãy B.")

Qua bài học này, các em sẽ có thể:

- Biết được ý nghĩa của bài toán tìm kiếm trên thực tế.

- Biết và thực hiện được chương trình tìm kiếm tuần tự và tìm kiếm nhị phân.

3.1. Trắc nghiệm Bài 23 SGK Tin học 11 Kết nối tri thức  

Như vậy là các em đã xem qua bài giảng Bài 23 Chủ đề 6 Tin học lớp 11 Kết nối tri thức. Để củng cố kiến thức bài học mời các em tham gia bài tập trắc nghiệm Trắc nghiệm Tin học 11 Kết nối tri thức Bài 23.

Câu 4-10: Mời các em đăng nhập xem tiếp nội dung và thi thử Online để củng cố kiến thức về bài học này nhé!

Các em có thể xem thêm phần hướng dẫn Giải bài tập Tin học 11 Kết nối tri thức Bài 23 để giúp các em nắm vững bài học và các phương pháp giải bài tập.

Khởi động trang 106 SGK Tin học 11 Kết nối tri thức - KNTT

Hoạt động 1 trang 106 SGK Tin học 11 Kết nối tri thức - KNTT

Câu hỏi 1 trang 107 SGK Tin học 11 Kết nối tri thức - KNTT

Câu hỏi 2 trang 107 SGK Tin học 11 Kết nối tri thức - KNTT

Hoạt động 2 trang 107 SGK Tin học 11 Kết nối tri thức - KNTT

Câu hỏi 1 trang 108 SGK Tin học 11 Kết nối tri thức - KNTT

Câu hỏi 2 trang 108 SGK Tin học 11 Kết nối tri thức - KNTT

Hoạt động 3 trang 108 SGK Tin học 11 Kết nối tri thức - KNTT

Câu hỏi trang 110 SGK Tin học 11 Kết nối tri thức - KNTT

Luyện tập 1 trang 110 SGK Tin học 11 Kết nối tri thức - KNTT

Luyện tập 2 trang 110 SGK Tin học 11 Kết nối tri thức - KNTT

Vận dụng 1 trang 110 SGK Tin học 11 Kết nối tri thức - KNTT

Vận dụng 2 trang 110 SGK Tin học 11 Kết nối tri thức - KNTT

Trong quá trình học tập nếu có thắc mắc hay cần trợ giúp gì thì các em hãy comment ở mục Hỏi đáp, Cộng đồng Tin học của HOC247 sẽ hỗ trợ cho các em một cách nhanh chóng!

Chúc các em học tập tốt và luôn đạt thành tích cao trong học tập!