Giáo án điện tử Khoa học máy tính 11 cánh diều Chủ đề F(CS) Bài 5: Đánh giá thuật toán
Bài giảng điện tử Tin học 11 Khoa học máy tính cánh diều. Giáo án powerpoint Chủ đề F(CS) Bài 5: Đánh giá thuật toán. Giáo án thiết kế theo phong cách hiện đại, nội dung đầy đủ, đẹp mắt, tạo hứng thú học tập cho học sinh. Thầy, cô giáo có thể tham khảo.
Click vào ảnh dưới đây để xem 1 phần giáo án rõ nét
Các tài liệu bổ trợ khác
Xem toàn bộ: Giáo án điện tử khoa học máy tính 11 cánh diều
CHÀO MỪNG CẢ LỚP ĐẾN VỚI TIẾT HỌC MỚI!
KHỞI ĐỘNG
Theo em, một thuật toán như thế nào thì được xem là chạy nhanh/chạy chậm?
BÀI 5: ĐÁNH GIÁ THUẬT TOÁN
NỘI DUNG BÀI HỌC
Các khái niệm cơ bản
Độ phức tạp thời gian của thuật toán
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
Kí pháp và các bậc độ phức tạp thời gian
Các quy tắc khi ước lượng thời gian thực hiện thuật toán
01
CÁC KHÁI NIỆM CƠ BẢN
Đọ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:
- Thế nào được gọi là một thuật toán “tốt”?
- Tính hiệu quả của thuật toán dựa trên những tiêu chí nào?
- Tại sao không thể đánh giá thuật toán qua chương trình cài đặt thuật toán?
- 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ụ.
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ả.
Tiết kiệm thời gian
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.
Lí do không thể bấm giờ lấy thời gian thực thi chương trình
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.
02
ĐỘ PHỨC TẠP THỜI GIAN CỦA THUẬT TOÁN
Đọc hiểu thông tin mục 2 trang 108 SGK, thảo luận cặp đôi trả lời các câu hỏi sau:
Thế nào là độ 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.
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?
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.
Phép toán sơ cấp là gì? Nêu ví dụ.
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.
03
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
Trên chỉ là 1 phần của giáo án. Giáo án khi tải về có đầy đủ nội dung của bài. Đủ nội dung của học kì I + học kì II
MỘT VÀI THÔNG TIN:
- Word được soạn: Chi tiết, rõ ràng, mạch lạc
- Powerpoint soạn: Hiện đại, đẹp mắt để tạo hứng thú học tập
- Word và powepoint đồng bộ với nhau
Phí giáo án:
- Giáo án word: 300k/học kì - 400k/cả năm
- Giáo án Powerpoint: 400k/học kì - 450k/cả năm
- Trọn bộ word + PPT: 500k/học kì - 600k/cả năm
=> Khi đặt: nhận đủ giáo án cả năm ngay và luôn
CÁCH TẢI:
- Bước 1: Chuyển phí vào STK: 10711017 - Chu Văn Trí- Ngân hàng ACB (QR)
- Bước 2: Nhắn tin tới Zalo Fidutech - nhấn vào đây để thông báo và nhận giáo án
=> Khi đặt, sẽ nhận giáo án ngay và luôn. Tặng kèm phiếu trắc nghiệm + đề kiểm tra ma trận
Xem toàn bộ: Giáo án điện tử khoa học máy tính 11 cánh diều
GIÁO ÁN WORD LỚP 11 CÁNH DIỀU
GIÁO ÁN POWERPOINT LỚP 11 CÁNH DIỀU
GIÁO ÁN CHUYÊN ĐỀ LỚP 11 CÁNH DIỀU
Giáo án chuyên đề Công nghệ cơ khí 11 cánh diều đủ cả năm
Giáo án chuyên đề Tin học 11 Khoa học máy tính cánh diều đủ cả năm
Giáo án chuyên đề Tin học 11 Tin học ứng dụng cánh diều đủ cả năm
Giáo án chuyên đề Âm nhạc 11 cánh diều đủ cả năm
Giáo án chuyên đề Kinh tế pháp luật 11 cánh diều đủ cả năm
GIÁO ÁN DẠY THÊM LỚP 11 CÁNH DIỀU
Giáo án dạy thêm toán 11 cánh diều đủ cả năm
Giáo án dạy thêm ngữ văn 11 cánh diều đủ cả năm
CÁCH ĐẶT MUA:
Liên hệ Zalo: Fidutech - nhấn vào đây