Soạn mới giáo án Khoa học máy tính 11 cánh diều Chủ đề F(CS) Bài 5: Đánh giá thuật toán

HOẠT ĐỘNG CỦA GV - HS

DỰ KIẾN SẢN PHẨM

Bước 1: GV chuyển giao nhiệm vụ học tập

- GV yêu cầu đọc hiểu thông tin mục 1 trang 107 SGK, thảo luận cặp đôi trả lời các câu hỏi sau:

1. Thế nào được gọi là một thuật toán “tốt”?

2. Tính hiệu quả của thuật toán dựa trên những tiêu chí nào?

3. (Câu hỏi 1 - Tự kiểm tra tr.112) Tại sao không thể đánh giá thuật toán qua chương trình cài đặt thuật toán?

4. Dựa vào kiến thức đã học ở bài 2, hãy cho biết vì sao thời gian thực hiện các phép toán là tuyến tính? Cho ví dụ.

- GV lưu ý HS: Trong hai tiêu chí đánh giá tính hiệu quả của thuật toán thì tiết kiệm thời gian được quan tâm hàng đầu và bài học này chỉ tập trung vào ước lượng độ phức tạp thời gian thuật toán.

Bước 2: HS thực hiện nhiệm vụ học tập

- HS đọc và tìm hiểu thông tin mục 1 SGK trang 101 - 102, thực hiện các nhiệm vụ được giao.

- GV hướng dẫn, theo dõi, hỗ trợ HS khi cần.

Bước 3: Báo cáo kết quả hoạt động và thảo luận

- GV mời đại diện một số nhóm trình bày kết quả thảo luận.

- GV mời HS nhóm khác nhận xét, bổ sung.

Bước 4: Đánh giá kết quả, thực hiện nhiệm vụ học tập

- GV nhận xét kết quả thảo luận của HS, thái độ làm việc của HS trong nhóm.

- GV kết luận và yêu cầu HS ghi chép đầy đủ vào vở.

1. Các khái niệm cơ bản

- Trong tin học, các thuật toán được đánh giá và so sánh dựa trên tính hiệu quả.

- Hiệu quả thuật toán được đánh giá theo cả hai tiêu chí: tiết kiệm thời gian và tiết kiệm không gian nhớ.

Ước lượng thời gian thực thi chương trình hiệu quả của thuật toán

- Các ngôn ngữ lập trình có lệnh cho phép bấm giờ tính thời gian chạy thực thi chương trình.

Ví dụ: Python có lệnh time()...

- Cách tính giờ chạy thực thi chương trình cụ thể không áp dụng được khi muốn so sánh hiệu quả để lựa chọn thuật toán vì các vấn đề sau đây:

+ Phải lập trình và chạy thử chương trình của tất cả các thuật toán cần so sánh.

+ Thời gian đo được phụ thuộc vào nhiều yếu tố không liên quan tới thuật toán: phần cứng máy tính, ngôn ngữ lập trình, chương trình dịch, kĩ năng lập trình của người viết.

+ Không khả thi nếu muốn chọn cách tính thời gian thực thi trung bình.

Kích thước đầu vào

- Thời gian thực thi thuật toán phụ thuộc kích thước đầu vào, được đại diện bằng một số tự nhiên n.

Ví dụ:

+ Dữ liệu đầu vào là dãy gồm 10 số → thời gian chạy mất 1s.

+ Dữ liệu đầu vào là dãy gồm 1000 số → thời gian chạy mất 10s.

HOẠT ĐỘNG CỦA GV - HS

DỰ KIẾN SẢN PHẨM

Bước 1: GV chuyển giao nhiệm vụ học tập

- GV yêu cầu HS đọc hiểu mục 2 tr.108 SGK, thảo luận cặp đôi trả lời các câu hỏi:

1. Thế nào là độ phức tạp thời gian của thuật toán?

2. Vì sao khó đếm chính xác con số ước lượng thời gian thực hiện các chương trình thuật toán để xử lí một lượng dữ liệu đầu vào có độ lớn n?

3. Phép toán sơ cấp là gì? Cho ví dụ.

Bước 2: HS thực hiện nhiệm vụ học tập

- HS đọc hiểu thông tin mục 2 SGK trang 108 và thực hiện nhiệm vụ.

- GV theo dõi, hỗ trợ HS trong quá trình học tập.

Bước 3: Báo cáo kết quả hoạt động và thảo luận

- HS giơ tay trả lời câu hỏi.

- Câu hỏi thảo luận 2: Khó đếm chính xác con số ước lượng vì:

+ Bộ xử lí thực hiện các phép toán bit, khó có thể xác định tương ứng số các phép toán bit với mỗi phép toán mà chúng ta vẫn biết như các phép toán số học (cộng, trừ, nhân, chia), các phép so sánh…

+ Ngay cả khi tính đếm số phép toán theo nghĩa thông thường với con người thì thế nào là một phép toán cũng không dễ thống nhất. Ví dụ: Phép khai căn, phép lũy thừa… là một hay nhiều phép toán số học.

- Các HS còn lại nhận xét, bổ sung (nếu có).

Bước 4: Đánh giá kết quả, thực hiện nhiệm vụ học tập

- GV nhận xét kết quả trả lời của HS.

- GV tổng quát kiến thức và yêu cầu HS ghi chép đầy đủ vào vở.

2. Độ phức tạp thời gian của thuật toán

- Độ phức tạp thời gian của thuật toán là kết quả ước lượng thời gian thực hiện các chương trình cài đặt thuật toán để xử lí một lượng dữ liệu đầu vào có độ lớn n.

Phép toán sơ cấp

- Phép toán sơ cấp là phép toán có thời gian thực hiện không lớn hơn một hằng số nào đó, không phụ thuộc n (n là kích thước dữ liệu đầu vào).

Ví dụ: Những trường hợp được coi là phép toán sơ cấp:

+ Phép toán số học, phép so sánh… với các toán hạng là giá trị cụ thể.

+ Các hàm toán học với đầu vào là giá trị cụ thể không phụ thuộc n.

Chú ý: Phép lặp, phép lựa chọn không phải là phép toán sơ cấp.

HOẠT ĐỘNG CỦA GV - HS

DỰ KIẾN SẢN PHẨM

Bước 1: GV chuyển giao nhiệm vụ học tập

- GV yêu cầu HS dựa vào kiến thức đã học ở Bài 1 và Bài 2, nhắc lại khả năng truy cập ngẫu nhiên, thời gian thực hiện là hằng số, thời gian thực hiện là tuyến tính.

- GV yêu cầu HS đọc hiểu thông tin mục 3 tr.108 - 109 thảo luận cặp đôi trả lời câu hỏi Hoạt động:

Cho bài toán tính tổng dãy số: S = 1 + 2 + … + n. Hãy cho biết cách giải nào tốt hơn trong hai cách giải sau đây:

Cách 1: Tính cộng dồn dần từng số.

Cách 2: Vì dãy số là cấp số cộng nên có thể dùng công thức tính tổng cấp số cộng S = .

- Trên cơ sở đó, GV yêu cầu HS trình bày về độ phức tạp thời gian hằng số, độ phức tạp thời gian tuyến tính.

Bước 2: HS thực hiện nhiệm vụ học tập

- HS đọc và tìm hiểu SGK trang 108 - 109, thực hiện các nhiệm vụ được giao.

- GV hướng dẫn, theo dõi, hỗ trợ HS khi cần.

Bước 3: Báo cáo kết quả hoạt động và thảo luận

- GV mời đại diện một số nhóm trình bày kết quả thảo luận.

- GV mời HS nhóm khác nhận xét, bổ sung.

Bước 4: Đánh giá kết quả, thực hiện nhiệm vụ học tập

- GV nhận xét kết quả thảo luận của HS, thái độ làm việc của HS trong nhóm.

- GV kết luận và yêu cầu HS ghi chép đầy đủ vào vở.

3. Ví dụ về độ phức tạp thời gian hằng số và độ phức tạp thời gian tuyến tính

Độ phức tạp thời gian hằng số

- Thuật toán có độ phức tạp thời gian hằng số khi mà số phép toán cần thực hiện không phụ thuộc kích thước n của dữ liệu đầu vào.

Ví dụ: Cách giải thứ hai của bài toán trong Hoạt động:

    s1 = n + 1

    s2 = n*s1

    s3 = s2/2

→ T(n) = 3.

Độ phức tạp thời gian tuyến tính

- Thuật toán có độ phức tạp thời gian tuyến tính nếu số phép toán cần thực hiện là hàm tuyến tính của n (n là kích thước dữ liệu đầu vào).

Ví dụ: Cách giải thứ nhất của bài toán trong Hoạt động:

while i <= n:

  tong = tong + i

  i = i + 1

→ T(n) = n – 1.

HOẠT ĐỘNG CỦA GV - HS

DỰ KIẾN SẢN PHẨM

Bước 1: GV chuyển giao nhiệm vụ học tập

Nhiệm vụ 1. Cách ước lượng làm già thêm

- GV đặt vấn đề: Xét thuật toán tìm số lớn nhất trong dãy số:

+ Đầu tiên, tạm gán max = a₀; đọc giá trị tiếp theo, so sánh với max và gán lại nếu cần.

+ Khi phần tử đầu dãy a₀  có giá trị lớn nhất thì số lần phải gán lại giá trị max = a_i bằng 0 → Số phép toán ít nhất ⇨ Trường hợp thuật lợi nhất.

+ Khi dãy số ban đầu là dãy tăng chặt, mọi số đều khác nhau, thì số lần gán max = a_i bằng n → Số phép toán nhiều nhất ⇨ Trường hợp bất lợi nhất.

+ Trường hợp ngẫu nhiên → Số phép toán cần thực hiện ở mức trung bình.

⇨ Tuy nhiên, không dễ tìm được ước lượng trung bình này, nên người ta chọn cách dễ làm hơn đó là ước lượng làm già thêm.

- GV yêu cầu HS đọc hiểu phần Cách ước lượng làm già thêm tr.109 để trả lời câu hỏi: Thế nào là cách ước lượng làm già thêm?

- GV bổ sung: Cách ước lượng đặc trưng này phân biệt O lớn với các kí hiệu khác cũng dùng trong thuật toán: o, Ω, ω, θ. Từ nội dung này, GV dẫn dắt sang nhiệm vụ tiếp theo.

Nhiệm vụ 2. Kí pháp O lớn

- Kí pháp O lớn là khái niệm khó, bản chất là dùng để biểu diễn các vô cùng lớn trong toán cao cấp, nên GV giới thiệu có thể diễn đạt đơn giản hơn để không phải dẫn dắt đến khái niệm vô cùng lớn: Kí hiệu O lớn dùng để đánh giá và phân loại độ phức tạp thời gian của thuật toán khi kích thước đầu vào của bài toán tăng lên vô cùng.

- GV yêu cầu HS đọc SGK tr.110 trả lời câu hỏi: Cho biết O lớn được sử dụng như thế nào trong thuật toán.

Bước 2: HS thực hiện nhiệm vụ học tập

- HS đọc và tìm hiểu SGK trang 109 - 110, thực hiện nhiệm vụ được giao.

- GV hướng dẫn, theo dõi, hỗ trợ HS khi cần.

Bước 3: Báo cáo kết quả hoạt động và thảo luận

- HS giơ tay trả lời câu hỏi.

- GV mời HS nhóm khác nhận xét, bổ sung.

Bước 4: Đánh giá kết quả, thực hiện nhiệm vụ học tập

- GV nhận xét câu trả lời của HS.

- GV kết luận và yêu cầu HS ghi chép đầy đủ vào vở.

4. Kí pháp và các bậc độ phức tạp thời gian

Cách ước lượng làm già thêm

- Số phép toán cần thiết để thực hiện thuật toán không chỉ phụ thuộc kích thước n của dữ liệu đầu vào mà còn phụ thuộc vào việc may mắn gặp trường hợp dễ, ít việc phải làm hay không may gặp trường hợp khó, nhiều việc phải làm hơn.

- Ước lượng làm già thêm là cách ước lượng đảm bảo rằng trong thực tế sẽ không có trường hợp nào vượt quá ước lượng đã đưa ra.

Kí pháp O lớn

- Nếu phép toán sơ cấp cần thực hiện không vượt quá một hằng số C, không phụ thuộc n → Độ phức tạp thời gian là hằng số T(n) = O(1).

- Nếu phép toán sơ cấp cần thực hiện không vượt quá một hàm số tuyến tính của n, T(n) ≤ C₁n + C₂ (C₁, C₂ là hằng số) → Độ phức tạp thời gian là tuyến tính T(n) = O(n).

- Một số công thức liên quan:

Công thức 1: Áp dụng cho hai cấu trúc điều khiển được thực hiện tuần tự.

Nếu f₁(n) = O(g₁(n)) và f₂(n) = O(g₂(n))

thì f₁(n) + f₂(n) = O(max(g₁(n), g₂(n)).

Công thức 2: Áp dụng cho hai cấu trúc điều khiển lồng nhau.

Nếu f₁(n) = O(g₁(n)) và f₂(n) = O(g₂(n))

thì f₁(n) × f₂(n) = O(g₁(n)× g₂(n)).

HOẠT ĐỘNG CỦA GV - HS

DỰ KIẾN SẢN PHẨM

Bước 1: GV chuyển giao nhiệm vụ học tập

- GV yêu cầu HS đọc mục 5 tr.110 - 111 SGK: Trình bày các quy tắc khi ước lượng thời gian thực hiện thuật toán.

Bước 2: HS thực hiện nhiệm vụ học tập

- HS đọc và tìm hiểu SGK trang 110 - 111, thực hiện các nhiệm vụ được giao.

- GV hướng dẫn, theo dõi, hỗ trợ HS khi cần.

Bước 3: Báo cáo kết quả hoạt động và thảo luận

- HS giơ tay trả lời câu hỏi.

- GV mời HS nhóm khác nhận xét, bổ sung.

Bước 4: Đánh giá kết quả, thực hiện nhiệm vụ học tập

- GV nhận xét câu trả lời của HS.

- GV kết luận và yêu cầu HS ghi chép đầy đủ vào vở.

3. Các quy tắc khi ước lượng thời gian thực hiện thuật toán

Quy tắc chung

- Khi tính đếm số phép toán cần thực hiện, các quy tắc ước lượng cho phép bỏ bớt những phần có bậc lớn thấp hơn, chỉ giữ lại những phần có bậc lớn cao nhất và các hằng số nhân C đều coi là 1.

- Mô tả thuật toán chỉ sử dụng ba cấu trúc: cấu trúc tuần tự, cấu trúc rẽ nhánh, cấu trúc lặp.

- Lồng bên trong các cấu trúc rẽ nhánh và cấu trúc lặp lại là các dãy phép toán tuần tự khác → Cần ước lượng số phép toán từ bên trong trở ra ngoài.

Lời gọi hàm

- Hàm bên trong chương trình thực chất là một chương trình con, thực hiện một thuật toán cụ thể.

- Ước lượng độ phức tạp thời gian của một lời gọi hàm được chia làm hai trường hợp:

+ Lời gọi các hàm toán học sơ cấp, các hàm thư viện… với đầu vào là các giá trị cụ thể không phụ thuộc n → T(n) = O(1).

+ Lời gọi hàm trong các trường hợp còn lại sẽ được ước lượng độ phức tạp như với một thuật toán.

Cấu trúc tuần tự và quy tắc lấy max

- Cấu trúc tuần tự là một dãy gồm C phép toán; C là số xác định, không phụ thuộc n.

+ Nếu tất cả C phép toán là sơ cấp → độ phức tạp thời gian là T(n) = O(1).

+ Trái lại, thời gian thực hiện bằng ước lượng lớn nhất trong số các ước lượng của phép toán có trong dãy.

Cấu trúc rẽ nhánh và quy tắc lấy max

- Khi thực thi một cấu trúc rẽ nhánh sẽ phải kiểm tra điều kiện và thực hiện một trong số các nhánh.

- Việc kiểm tra điều kiện là tính giá trị biểu thức logic gồm biểu thức số học và một phép so sánh → T(n) = O(1).

- Độ phức tạp thời gian của cấu trúc rẽ nhánh là độ phức tạp lớn nhất trong các độ phức tạp thời gian của các nhánh.

Ví dụ:

Cấu trúc vòng lặp và quy tắc nhân

- Khi thực hiện một cấu trúc vòng lặp sẽ phải kiểm tra điều kiện và thực hiện hiện thân vòng lặp.

- Thân vòng lặp là một cấu trúc tuần tự các phép toán.

- Thời gian thực hiện cấu trúc vòng lặp được tính bằng số lần lặp nhân với tổng thời gian kiểm tra điều kiện lặp và thời gian thực hiện thân vòng lặp.

Ví dụ: