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

1. VAI TRÒ 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.

- 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.

2. KIỂM TRA TÍNH ĐÚNG CỦA CHƯƠNG TRÌNH

- Chương trình thực hiện thuật toán sắp xếp chèn để sắp xếp dãy A cho trước theo thứ tự tăng dần như sau:

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

- 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.

3. ĐÁNH GIÁ HIỆU QUẢ CHƯƠNG TRÌ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. 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 người ta 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.

- Độ 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.