[Lý thuyết] Kiểm thử và đánh giá chương trình SVIP

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

Phương pháp 1: Tạo các bộ dữ liệu kiểm thử để xem dữ liệu đầu ra có đúng hay không.

• Ý tưởng: Sử dụng các bộ dữ liệu kiểm thử để kiểm tra tính đúng của chương trình.
• Nhận định: Kết quả chỉ làm tăng khả năng đúng của chương trình.

Phương pháp 2: Thiết lập điểm dừng hoặc chạy chương trình theo từng lệnh, in dữ liệu trung gian trong quá trình kiểm thử.

• Ý tưởng: Kiểm tra quá trình thực hiện chương trình thông qua từng câu lệnh hoặc dữ liệu trung gian.
• Nhận định: Chương trình tin cậy hơn nhưng chưa chắc đã đúng đắn.

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

Xem xét ba cách lập luận để kiểm tra tính đúng của thuật toán sắp xếp chèn.

Lập luận 1: Sử dụng các bộ dữ liệu kiểm thử.

• Ý tưởng: Kiểm tra kết quả đầu ra bằng cách cài đặt và nhập bộ dữ liệu.
• Nhận định: Chưa chứng minh được tính đúng của thuật toán nhưng tăng độ tin cậy của chương trình.

Lập luận 2: Kiểm tra tính logic của các lệnh.

• Ý tưởng: Suy diễn đến bước cuối cùng (hoặc là kết quả giả định đúng đắn) của chương trình/thuật toán thông qua phân tích và xem xét tính logic từ ý tưởng giải quyết vấn đề.
• Nhận định: Suy luận logic từ ý tưởng thuật toán là cách đơn giản để chứng minh tính đúng của thuật toán.

Lập luận 3: Chứng minh bằng logic toán học.

• Ý tưởng: Sử dụng logic toán học, chứng minh mệnh đề bằng bất biến vòng lặp.
• Nhận định: Chứng minh tính đúng của chương trình bằng lập luận toán học (PPQN) là cách tốt nhất.

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

Hiệu quả hay tính tối ưu của chương trình thường được xem xét trên cơ sở đánh giá độ 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.

Hai loại độ phức tạp tính toán phổ biến nhất đó là:

• Độ 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. Thời gian phụ thuộc vào khối lượng của dữ liệu cần phải lưu trữ trong quá trình thực hiện chương trình thuật toán, các bước giải quyết một vấn đề cụ thể đưa ra trong chương trình/thuật toán.

• Độ phức tạp không gian (space complexity) đượ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.

Một chương trình thuật toán là hiệu quả (efficient) nếu độ phức tạp của thuật toán này là thấp.

Tổng kết kiến thức

1. Kiểm thử chỉ có thể làm tăng độ tin cậy của chương trình.

2. Tính đúng của thuật toán cần chứng minh bằng lập luận toán học.

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

4. Độ phức tạp thời gian quan trọng nhất vì liên quan trực tiếp tới các câu lệnh.