Các bài khác
- Khoa học máy tính 11 cánh diều: Tải giáo án Chủ đề A Bài 1 Bên trong máy tính
- Khoa học máy tính 11 cánh diều: Tải giáo án Chủ đề A Bài 2 Khám phá thế giới thiết bị số thông minh
- Khoa học máy tính 11 cánh diều: Tải giáo án Chủ đề A Bài 3 Khái quát về hệ điều hành
- Khoa học máy tính 11 cánh diều: Tải giáo án Chủ đề A Bài 4 Thực hành với các thiết bị số
- Khoa học máy tính 11 cánh diều: Tải giáo án Chủ đề A Bài 5 Phần mềm ứng dụng và dịch vụ phần mềm
- Khoa học máy tính 11 cánh diều: Tải giáo án Chủ đề C Bài 1 Lưu trữ trực tuyến
- Khoa học máy tính 11 cánh diều: Tải giáo án Chủ đề C Bài 2 Thực hành một số tính năng hữu ích của máy tìm kiếm
- Khoa học máy tính 11 cánh diều: Tải giáo án Chủ đề C Bài 3 Thực hành một số tính năng nâng cao của mạng xã hội
- Khoa học máy tính 11 cánh diều: Tải giáo án Chủ đề C Bài 4 Thực hành một số tính năng hữu ích của dịch vụ thư điện tử
- Khoa học máy tính 11 cánh diều: Tải giáo án Chủ đề D Bài Phòng tránh lừa đảo và ứng xử văn hoá trên mạng
- Khoa học máy tính 11 cánh diều: Tải giáo án Chủ đề F Bài 1 Bài toán quản lí và cơ sở dữ liệu
- Khoa học máy tính 11 cánh diều: Tải giáo án Chủ đề F Bài 2 Bảng và khoá chính trong cơ sở dữ liệu quan hệ
- Khoa học máy tính 11 cánh diều: Tải giáo án Chủ đề F Bài 3 Quan hệ giữa các bảng và khoá ngoài trong cơ sở dữ liệu quan hệ
- Khoa học máy tính 11 cánh diều: Tải giáo án Chủ đề F Bài 4 Các biểu mẫu cho xem và cập nhật dữ liệu
- Khoa học máy tính 11 cánh diều: Tải giáo án Chủ đề F Bài 5 Truy vấn trong cơ sở dữ liệu quan hệ
- Khoa học máy tính 11 cánh diều: Tải giáo án Chủ đề F Bài 6 Truy vấn trong cơ sở dữ liệu quan hệ (tiếp theo)
- Khoa học máy tính 11 cánh diều: Tải giáo án Chủ đề F Bài 7 Các loại kiến trúc của hệ cơ sở dữ liệu
- Khoa học máy tính 11 cánh diều: Tải giáo án Chủ đề F Bài 8 Bảo vệ an toàn của hệ cơ sở dữ liệu và bảo mật thông tin trong cơ sở dữ liệu
- Khoa học máy tính 11 cánh diều: Tải giáo án Chủ đề G Bài Nghề quản trị cơ sở dữ liệu
- Khoa học máy tính 11 cánh diều: Tải giáo án Chủ đề F(CS) Bài 1 Kiểu mảng và cấu trúc mảng
- Khoa học máy tính 11 cánh diều: Tải giáo án Chủ đề F(CS) Bài 2 Mảng hai chiều
- Khoa học máy tính 11 cánh diều: Tải giáo án Chủ đề F(CS) Bài 3 Thực hành về tệp, mảng và danh sách
- Khoa học máy tính 11 cánh diều: Tải giáo án Chủ đề F(CS) Bài 4 Làm mịn dần từng bước từ thuật toán đến chương trình máy tính
- Khoa học máy tính 11 cánh diều: Tải giáo án Chủ đề F(CS) Bài 5 Đánh giá thuật toán
- Khoa học máy tính 11 cánh diều: Tải giáo án Chủ đề F(CS) Bài 6 Kiểm thử và sửa lỗi chương trình
Khoa học máy tính 11 cánh diều: Tải giáo án Chủ đề F(CS) Bài 5 Đánh giá thuật toán
Mẫu giáo án chủ đề F(CS) Bài 5 Đánh giá thuật toán - khoa học máy tính 11 cánh diều. Giáo án được biên soạn chi chủ đề. Có thể tải về tham khảo. Cách tải nhanh chóng, dễ dàng. Ngoài ra, hệ thống có đủ các chủ đề khác trong chương trình khoa học máy tính 11 cánh diều
Nội dung giáo án
Ngày soạn:…/…/…
Ngày dạy:…/…/…
BÀI 5. ĐÁNH GIÁ THUẬT TOÁN
- MỤC TIÊU
- Về kiến thức
Sau bài học này, HS sẽ:
- Trình bày được sơ lược khái niệm độ phức tạp thời gian của thuật toán. Nêu được ví dụ minh họa.
- Biết được kí pháp O lớn và các bậc độ phức tạp thời gian.
- Năng lực
Năng lực chung:
- Năng lực tự chủ: Biết lựa chọn các nguồn tài liệu học tập phù hợp.
- Năng lực giải quyết vấn đề và sáng tạo: Xác định và tìm hiểu được các thông tin liên quan đến vấn đề, đề xuất giải pháp giải quyết vấn đề trong bài học.
- Năng lực giao tiếp và hợp tác: Thực hiện tốt nhiệm vụ trong hoạt động nhóm.
Năng lực tin học:
- Hình thành, phát triển năng lực tin học giải quyết vấn đề với sự hỗ trợ của công nghệ thông tin và truyền thông.
- Ứng dụng công nghệ thông tin và truyền thông trong học và tự học.
- Khả năng tư duy logic và mô hình hóa.
- Phẩm chất
- Hình thành ý thức trách nhiệm, tính cẩn thận, chăm chỉ trong học tập và công việc.
- Có ý thức vận dụng kiến thức, kĩ năng đã học ở nhà trường vào thực tiễn.
- THIẾT BỊ DẠY HỌC VÀ HỌC LIỆU
- Đối với giáo viên
- SGK, SGV, Giáo án;
- Máy tính và máy chiếu;
- Tài liệu hướng dẫn sử dụng máy tính (tivi, điện thoại,...) (nếu có).
- Đối với học sinh: SGK, SBT, vở ghi.
III. TIẾN TRÌNH DẠY HỌC
- HOẠT ĐỘNG KHỞI ĐỘNG
- Mục tiêu: Tạo tâm thế vui vẻ, hứng khởi cho HS trước khi vào bài học mới; kích thích sự tò mò cho người học.
- Nội dung: GV cho HS liên hệ thực tế, dùng những hiểu biết của bản thân để trả lời câu hỏi.
- Sản phẩm học tập: Câu trả lời của HS theo ý kiến cá nhân.
- Tổ chức thực hiện:
Bước 1: GV chuyển giao nhiệm vụ học tập
- GV đặt câu hỏi: Theo em, một thuật toán như thế nào thì được xem là chạy nhanh/chạy chậm?
Bước 2: HS thực hiện nhiệm vụ học tập
- HS lắng nghe, suy nghĩ và đưa ra câu trả lời dựa trên những hiểu biết của bản thân
Bước 3: Báo cáo kết quả hoạt động và thảo luận
- GV mời 2 - 3 HS trả lời câu hỏi.
- GV ghi nhận tất cả các câu trả lời của HS.
Bước 4: Đánh giá kết quả, thực hiện nhiệm vụ học tập
- GV nhận xét, đánh giá, dẫn dắt vào nội dung bài mới: Thời gian chạy chương trình phụ thuộc vào yếu tố nào? Chúng ta hãy cùng vào - Bài 5. Đánh giá thuật toán.
- HOẠT ĐỘNG HÌNH THÀNH KIẾN THỨC
Hoạt động 1: Các khái niệm cơ bản
- Mục tiêu: Biết được các khái niệm cơ bản.
- Nội dung: GV giao nhiệm vụ, HS đọc hiểu thông tin mục 1 SGK trang 107; thực hiện các nhiệm vụ GV giao.
- Sản phẩm học tập: Các khái niệm cơ bản.
- Tổ chức hoạt động:
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 2: Độ phức tạp thời gian của thuật toán
- Mục tiêu: Trình bày được sơ lược khái niệm độ phức tạp thời gian của thuật toán. Nêu được ví dụ minh họa.
- Nội dung: GV giao nhiệm vụ, HS đọc hiểu thông tin mục 2 SGK trang 108; thực hiện các nhiệm vụ GV giao.
- Sản phẩm học tập: Độ phức tạp thời gian của thuật toán.
- Tổ chức hoạt động:
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 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
- Mục tiêu: Nêu được ví dụ minh họa về độ phức tạp thời gian của thuật toán.
- Nội dung: GV giao nhiệm vụ, HS đọc hiểu thông tin mục 3 SGK trang 108 – 109; thực hiện các nhiệm vụ GV giao.
- Sản phẩm học tập: 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.
- Tổ chức hoạt động:
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 4: Kí pháp và các bậc độ phức tạp thời gian
- Mục tiêu: Biết được kí pháp O lớn và các bậc độ phức tạp thời gian.
- Nội dung: GV giao nhiệm vụ, HS đọc hiểu thông tin mục 4 SGK trang 109 – 110; thực hiện các nhiệm vụ GV giao.
- Sản phẩm học tập: Kí pháp O lớn và các bậc độ phức tạp thời gian.
- Tổ chức hoạt động:
Thông tin tải tải liệu
Nhận xét
Đánh giá trung bình
Chi tiết
Kho tài liệu Tin học 11 cánh diều
Giáo án lớp 11 cánh diều chương trình mới bản chuẩn
1. Giáo án ban tự nhiên
- Giáo án toán 11 cánh diều chuẩn nhất
- Giáo án vật lí 11 cánh diều chuẩn nhất
- Giáo án sinh học 11 cánh diều chuẩn nhất
- Giáo án hoá học 11 cánh diều chuẩn nhất
- Giáo án tiếng anh 11 cánh diều chuẩn nhất
2. Giáo án ban xã hội
- Giáo án ngữ văn 11 cánh diều chuẩn nhất
- Giáo án lịch sử 11 cánh diều chuẩn nhất
- Giáo án Địa lí 11 cánh diều chuẩn nhất
- Giáo án kinh tế pháp luật 11 cánh diều chuẩn nhất
3. Giáo án các môn khác
Giáo án tin học cánh diều bản chuẩn, đầy đủ
Tin học cánh diều THPT
- Giáo án Tin học 10 Cánh diều chuẩn nhất
- Giáo án Tin học 11 Cánh diều chuẩn nhất
- Giáo án Tin học 12 Cánh diều chuẩn nhất
Tin học cánh diều THCS
- Giáo án Tin học 6 Cánh diều chuẩn nhất
- Giáo án Tin học 7 Cánh diều chuẩn nhất
- Giáo án Tin học 8 Cánh diều chuẩn nhất
- Giáo án Tin học 9 Cánh diều chuẩn nhất