Rèn luyện khả năng đánh giá độ phức tạp của thuật toán
Mục đích đưa dạy học lập trình vào chương trình PTTH trước hết nằm trang bị cho học sinh (HS) một số kiến thức, kỹ năng cơ
bản về lập trình, biết vận dụng chúng để giải một số bài tập cơ bản, đồng thời bước đầu chuẩn bị hành trang cho HS có thể đi tiếp
vào lĩnh vực này ở các giai đoạn tiếp theo. Đặc biệt qua dạy học lập trình cần rèn luyện cho HS một loại hình tư duy quan trọng -
đó là tư duy thuật toán.
Để hình thành và phát triển loại hình tư duy này cần trú trọng rèn luyện cho HS các khả năng sau:
1. Thực hiện những thao tác theo một trình tự nhất định phù hợp với một thuật toán cho trước
2. Phân tích một hoạt động thành những thao tác thành phần được thực hiện theo một trình tự nhất định.
3. Mô tả chính xác quá trình tiến hành một hoạt động.
4. Khái quát hoá một hoạt động trên những đối tượng riêng lẻ thành một hoạt động trên một lớp đối tượng.
5. So sánh những thuật toán khác nhau cùng thực hiện một công việc và phát hiện thuật toán tối ưu.
Việc rèn luyện, phát triển tư duy thuật toán cho HS được hiểu theo hướng là rèn luyện cho HS 5 khả năng trên.
Trong dạy học tin học cho đối tượng đại trà thì việc thực hiện mục tiêu thứ 5 thường khặp khó khăn, lý do có thể kể đến là:
- HS không được học khái niệm "Độ phức tạp của một thuật toán" một cách tường minh.
- Việc đánh giá độ phức tạp của một thuật toán vốn là một bài toán khó.vv
Tuy nhiên giáo viên (GV) có thể từng bước hình thành, rèn luyện cho HS khả năng đánh giá độ phức tạp của thuật toán ở mức độ
đơn giản dưới các góc độ sau:
- Độ phức tạp về thời gian tính của thuật toán
- Độ phức tạp về dung lượng nhớ dùng cho thuật toán.
Xin minh hoạ bằng các ví dụ cụ thể trong SGK Tin học lớp 10.
Ví dụ 1: Lập trình giải bài toán cổ "vừa gà vừa chó"
Phương án 1:
Gọi số gà là i (khi đó số chó là 36-i)
Từ giả thiết suy ra i là một số nguyên và có thể nhận giá trị từ 0 đến 36.
Ta có thuật toán :
For i:= 0 To 36 Do
If 2*i + (36-i)*4 =100 Then
Thông báo kết quả.
Với mỗi bước lặp về hình thức máy phải thực hiện 5 phép toán, nếu gọi thời gian để thực hiện một lượt 5 phép toán đó là t thì thời
gian thực hiện thuật toán là 36t.
Phương án 2:

end
else If a[k]>x then cuoi:=k-1
else dau:=k+1
Vậy sau mỗi bước lặp hoặc ta tìm được số x hoặc chỉ còn phải so sánh x với một nửa các phần tử của dãy.
Bằng các ví dụ cụ thể với số phần tử n càng lớn, HS càng chỉ ra được tính tối ưu của phương án 2 so với phương án 1 (độ phức
tạp của phương án 2 là O(log2n) trong khi đó độ phức tạp của thuật toán trong phương án 1 là O(n)).
Ví dụ 3: Tính giá trị của đa thức P(x)=anxn+an-1xn-1+....+a1x +ao tại x=xo.
Phương án 1: Tính giá trị từng hạng tử của đa thức rồi cộng lại
s:=a[o];
For i:=1 to n do
begin
For j:=1 to i do a[i]:=a[i]*xo;
s:=s+a[i];
end;
ở bước tính giá trị hạng tử thứ i cần phải thực hiện i phép nhân vậy số phép nhân cần phải thực hiện là 1+2+...+n =n(n+1)/2; sau
đó ta cần thực hiện n phép cộng để cộng từng hạng tử vào tổng S. Vậy tổng các phép toán cần thực hiện là n+n(n+1)/2 =
n(n+3)/2.
Phương án 2: Tính dồn theo bậc
tg:=1;s:=a[o];
For i:=1 to n do
begin
tg:=tg*xo;
s:=s+a[i]*tg
end;
Vậy với mỗi bước lặp số phép toán phải thực hiện gồm 2 phép nhân và 1 phép cộng. Do vậy tổng số phép toán phải thực hiện là
3n.
Phương án 3: Ta có đa thức P(x) có thể biểu diễn dưới dạng:
P(x)=(....(anx+an-1)x+an-2ư)x+.....x)+ao.
Nên ta có thể tính giá trị của P(x) tại x=xo như sau:
s:=a[n];