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.
Tuy nhiên, một điều cần cũng rất quan trọng là học sinh cần chú trọng đến một khái niệm "Độ phức tạp của một thuật toán" và đánh giá độ phức tạp của một thuật toán…Để làm được điều này, học sinh có thể từng bước hình thành, rèn luyện 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.
Chúng ta có thể đi vào chi tiết một vài ví dụ đơn giản trong SGK Tin học lớp 11.
Ví dụ 1: Lập trình giải bài toán cổ "vừa gà vừa chó"
Cách 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.
Cách 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ố, chúng 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".
Cách 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.
Cách 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, chúng ta có thể chỉ ra được tính tối ưu của cách 2 so với cách 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: Cho một dãy số a có n phần tử a1, a2, ...an. Hãy xây dựng thuật toán để tìm con số lớn nhất trong dãy a.
Khi giải quyết bài toán này, chúng ta nhận thấy:
- Nếu dãy chỉ có 1 phần tử thì phần tử đó là số lớn nhất.
- Giả sử dãy có n phần tử và ta đã xác định được phần tử lớn nhất là amax . Nếu bổ sung thêm phần tử thứ an+1 vào dãy mà an+1 > amax thì an+1 chính là phần tử lớn nhất của dãy có n+1 phần tử. Trường hợp ngược lại, nghĩa là an+1 < amax thì amax vẫn là phần tử lớn nhất của dãy có n+1 phần tử.
Ta có thuật toán như sau:
Bước 1: Ghi nhớ amax = a1.
Bước 2: i = 2.
Bước 3: Nếu (i £ n) thì thực hiện các bước sau, ngược lại sang bước 5.
Bước 3.1: Nếu (ai > amax ) thì
Bước 3.1.1: Ghi nhớ amax = ai .
Bước 3.2: Tăng i lên 1.
Bước 4: Trở lại bước 3.
Bước 5: Phần tử lớn nhất dãy a chính là amax .Kết thúc.
Trong thuật toán trên, để đơn giản, ta chỉ xem chi phí là số lần so sánh ở bước 3.1 và số lần "ghi nhớ" trong bước 3.1.1. Trường hợp tốt nhất của thuật toán này xảy ra khi con số lớn nhất nằm đầu dãy (amax= a1); trường hợp xấu nhất xảy ra khi con số lớn nhất nằm ở cuối dãy (amax=an) và dãy được sắp xếp theo thứ tự tăng dần.
Dựa theo sơ đồ khối của thuật toán, ta nhận thấy rằng, trong mọi trường hợp của bài toán, phép "ghi nhớ" ở bước 3.1 luôn được thực hiện và số lần thực hiện là n-1 (ứng với việc xét từ phần tử a2 đến an). Ta gọi đây là chi phí cố định hoặc bất biến của thuật toán.
- Trường hợp tốt nhất : do amax = a1 suy ra, với mọi i >= 2, ai< amax. Do đó, điều kiện ai>amax ở bước 3.1 luôn không thỏa nên bước 3.1.1 không bao giờ được thực hiện. Như vậy, chi phí chung cho trường hợp này chính là chi phí cố định của bài toán.
T = f(n) = n-1
- Trường hợp xấu nhất : với mọi i>1, ai-1< ai (do định nghĩa dãy được sắp xếp tăng dần) nên điều kiện ai>amax ở bước 3.1 luôn thỏa, bước 3.1.1 luôn được thực hiện. Như vậy, ngoài chi phí chung là n-1 phép so sánh, ta cần phải dùng thêm n-1 phép "ghi nhớ" ở bước 3.1.1. Như vậy, tổng chi phí của trường hợp này là
T = f(n) = 2(n-1)=2n-2
Tóm lại, một điều quan trọng cần phải biết là máy tính phải cần bao lâu để giải xong một bài toán. Thí dụ, nếu một thuật toán đòi hỏi 10 giờ, thì chúng ta có thể chấp nhận chi phí thời gian máy tính đòi hỏi để giải bài toán đó. Nhưng nếu một thuật toán đòi hỏi 10 tỉ năm để giải một bài toán, thì thực hiện thuật toán đó sẽ là một điều phi lý. Một trong những hiện tượng lý thú nhất của công nghệ hiện đại là sự tăng ghê gớm của tốc độ và lượng bộ nhớ trong máy tính. Một nhân tố quan trọng khác làm giảm thời gian cần thiết để giải một bài toán là sự xử lý song song - đây là kỹ thuật thực hiện đồng thời các dãy phép tính. Do sự tăng tốc độ tính toán và dung lượng bộ nhớ của máy tính, cũng như nhờ việc dùng các thuật toán lợi dụng được ưu thế của kỹ thuật xử lý song song, các bài toán vài năm trước đây được xem là không thể giải được, thì bây giờ có thể giải bình thường.
Không có nhận xét nào:
Đăng nhận xét