Hotline: 024.62511017

024.62511081

  Trang chủ   Sản phẩm   Phần mềm Dành cho nhà trường   Phần mềm Hỗ trợ học tập   Kho phần mềm   Liên hệ   Đăng nhập | Đăng ký

Tìm kiếm

School@net
 
Xem bài viết theo các chủ đề hiện có
  • Hoạt động của công ty (726 bài viết)
  • Hỗ trợ khách hàng (498 bài viết)
  • Thông tin tuyển dụng (57 bài viết)
  • Thông tin khuyến mại (80 bài viết)
  • Sản phẩm mới (216 bài viết)
  • Dành cho Giáo viên (549 bài viết)
  • Lập trình Scratch (3 bài viết)
  • Mô hình & Giải pháp (156 bài viết)
  • IQB và mô hình Ngân hàng đề kiểm tra (127 bài viết)
  • TKB và bài toán xếp Thời khóa biểu (242 bài viết)
  • Học tiếng Việt (183 bài viết)
  • Download - Archive- Update (289 bài viết)
  • Các Website hữu ích (70 bài viết)
  • Cùng học (92 bài viết)
  • Learning Math: Tin học hỗ trợ học Toán trong nhà trường (78 bài viết)
  • School@net 15 năm (154 bài viết)
  • Mỗi ngày một phần mềm (7 bài viết)
  • Dành cho cha mẹ học sinh (124 bài viết)
  • Khám phá phần mềm (122 bài viết)
  • GeoMath: Giải pháp hỗ trợ học dạy môn Toán trong trường phổ thông (36 bài viết)
  • Phần mềm cho em (13 bài viết)
  • ĐỐ VUI - THƯ GIÃN (363 bài viết)
  • Các vấn đề giáo dục (1210 bài viết)
  • Bài học trực tuyến (1037 bài viết)
  • Hoàng Sa - Trường Sa (17 bài viết)
  • Vui học đường (275 bài viết)
  • Tin học và Toán học (220 bài viết)
  • Truyện cổ tích - Truyện thiếu nhi (180 bài viết)
  • Việt Nam - 4000 năm lịch sử (97 bài viết)
  • Xem toàn bộ bài viết (8222 bài viết)
  •  
    Đăng nhập/Đăng ký
    Bí danh
    Mật khẩu
    Mã kiểm traMã kiểm tra
    Lặp lại mã kiểm tra
    Ghi nhớ
     
    Quên mật khẩu | Đăng ký mới
     
    Thành viên có mặt
    Khách: 2
    Thành viên: 0
    Tổng cộng: 2
     
    Số người truy cập
    Hiện đã có 79336825 lượt người đến thăm trang Web của chúng tôi.

    Rèn luyện khả năng đánh giá độ phức tạp của thuật toán

    Ngày gửi bài: 04/01/2006
    Số lượt đọc: 4676

    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:

    Gọi số chó là i (số gà là 36-i). Vậy i là một số nguyên có thể nhận giá trị từ 0 đến 25 (vì tổng số chân chỉ có 100 nên số chó tối đa là 25), ta có thuật toán

    For i:= 0 to 25 do

    If 4*i + (36-i)*2 = 100 then

    Thông báo kết quả.

    Vậy thời gian để thực hiện thuật toán 2 là 25t. So với thuật toán ban đầu thì lượng thời gian rút ngắn được là 11t.

    Ví dụ 2: Viết chương trình nhập vào 20 số thực, sau đó sắp lại dãy theo chiều tăng dần và cho biết một số thực x có thuộc mảng không?

    Khi giải quyết công đoạn sắp xếp lại dãy số, HS thường sử dụng thuật toán sắp xếp tuần tự hoặc sắp xếp "nổi bọt", 2 thuật toán này đều tối đa là thực hiện n(n-1)/2 lần so sánh (độ phức tạp tối đa của 2 thuật toán đều là O(n2)). Nên chúng tôi hướng HS so sánh độ phức tạp của thuật toán ở công đoạn tìm số thực x có mặt trong dãy.

    Phương án 1: Ta lần lượt so sánh số x với từng số trong dãy

    i:=1; ok:=true
    While (i<=20) and ok do
    If x=a[i] then
    begin
    Thông báo đã tìm thấy ở vị trí i;
    ok:=False;
    end
    else i:=i+1;

    Vậy tối đa thuật toán thực hiện 20 lần phép toán so sánh.

    Phương án 2: Lần lượt so sánh x với số nằm ở vị trí giữa của dãy

    dau:=1; cuoi:=20;ok:=true;
    While (dau<= cuoi) and ok do
    Begin
    k:=Trunc((daưcuoi)/2);
    If a[k]=x then
    Begin
    Thông báo tìm thấy ở vị trí i;
    ok:=False;
    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];
    For i:=1 to n do s:=s*xo+a[n-i]

    Với mỗi bước của vòng lặp ta cần thực hiện một phép toán nhân và một phép toán cộng, một phép tính trừ. Vậy tổng số phép toán phải thực hiện là 3n.

    Phương án 4:Tương tự phương án 3 nhưng ta dùng vòng For dạng lùi.

    s:=a[n];
    For i:=n-1 downto 0 do s:=s*x0+a[i]

    Mỗi bước của vòng lặp số phép toán được thực hiện là một phép toán nhân và một phép cộng. Tổng cộng số phép toán sẽ thực hiện là 2n.

    So sánh với 3 phương án trên thì phương án 4 tối ưu hơn cả vì số phép toán phải thực hiện là ít nhất.

    Vậy qua các ví dụ cụ thể, đơn giản GV đã từng bước hình thành và rèn luyện cho HS đánh giá độ phức tạp của thuật toán và từ đó lựa chọn thuật toán tối ưu. Đây là những kinh nghiệm của chúng tôi đã áp dụng thành công cho đối tượng đại trà. Rất mong nhận được sự đóng góp ý kiến của các bạn.

    School@net



     Bản để in  Lưu dạng file  Gửi tin qua email


    Những bài viết khác:



    Lên đầu trang

     
    CÔNG TY CÔNG NGHỆ TIN HỌC NHÀ TRƯỜNG
     
    Phòng 804 - Nhà 17T1 - Khu Trung Hoà Nhân Chính - Quận Cầu Giấy - Hà Nội
    Phone: 024.62511017 - 024.62511081
    Email: kinhdoanh@schoolnet.vn


    Bản quyền thông tin trên trang điện tử này thuộc về công ty School@net
    Ghi rõ nguồn www.vnschool.net khi bạn phát hành lại thông tin từ website này
    Site xây dựng trên cơ sở hệ thống NukeViet - phát triển từ PHP-Nuke, lưu hành theo giấy phép của GNU/GPL.