Giáo án Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Giáo án Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Xem thử

Chỉ từ 200k mua trọn bộ Kế hoạch bài dạy (KHBD) hay Giáo án Tin học 11 Kết nối tri thức bản word chuẩn kiến thức, trình bày đẹp mắt, dễ dàng chỉnh sửa:

• B1: gửi phí vào tk: 1133836868 - CT TNHH DAU TU VA DV GD VIETJACK - Ngân hàng MB (QR)
• B2: Nhắn tin tới Zalo VietJack Official - nhấn vào đây để thông báo và nhận giáo án

I. MỤC TIÊU:

1. Kiến thức:

Học xong bài này, HS đạt các yêu cầu sau:

- Biết cách phân tích độ phức tạp thời gian thuật toán.

- Nhận biết được phép toán tích cực trong chương trình.

- Biết và thực hiện được tính toán độ phức tạp thời gian của một số thuật toán đã biết.

- Tính và ước lượng được thời gian thuật toán và chương trình.

- Tính được độ phức tạp thời gian thuật toán.

2. Năng lực

Năng lực chung:

- Tự chủ và tự học: biết lắng nghe, tự giác học tập và hoàn thành nhiệm vụ; tích cực tham gia các hoạt động học tập trong lớp.

- Giao tiếp và hợp tác: có thói quen trao đổi, giúp đỡ nhau trong học tập; biết cùng nhau hoàn thành nhiệm vụ học tập theo sự hướng dẫn của GV.

- Giải quyết vấn đề và sáng tạo: ứng dụng các kiến thức đã học vào thực tế, phát triển khả năng giải quyết vấn đề có tính tích hợp liên môn giữa Tin học với các môn học khác.

Năng lực riêng:

- Biết cách phân tích độ phức tạp thời gian thuật toán.

- Nhận biết được phép toán tích cực trong chương trình.

- Biết và thực hiện được tính toán độ phức tạp thời gian của một số thuật toán đã biết.

- Tính và ước lượng được thời gian thuật toán và chương trình.

- Tính được độ phức tạp thời gian thuật toán.

3. Phẩm chất

- Trách nhiệm, tính cẩn thận khi làm việc nhóm, phẩm chất làm việc chăm chỉ, chuyên cần để hoàn thành một nhiệm vụ.

II. THIẾT BỊ DẠY HỌC VÀ HỌC LIỆU

1. Đối với giáo viên

- SGK, tài liệu giảng dạy, giáo án PPT.

- Máy tính, máy chiếu.

2. Đối với học sinh:

- SGK, SBT Tin học 11, vở ghi chép.

- Tài liệu, thiết bị có liên quan đến nội dung bài học.

III. TIẾN TRÌNH DẠY HỌC

A. HOẠT ĐỘNG KHỞI ĐỘNG

a) Mục tiêu: GV khơi gợi sự tò mò của HS đến việc đánh giá tính tối ưu, hiệu quả của chương trình.

b) Nội dung: GV tổ chức trả lời câu hỏi ở phần Mở đầu, thông qua đó tiếp cận đến khái niệm Độ phức tạp thời gian thuật toán và khái niệm “bậc” của độ phức tạp .

c) Sản phẩm: Dựa vào kiến thức của bản thân, HS thực hiện yêu cầu GV đưa ra.

d) Tổ chức thực hiện:

Bước 1: GV chuyển giao nhiệm vụ:

- GV dẫn dắt, đặt vấn đề cho HS: Quan sát Hình 24.1, chúng ta dễ thấy phép nhân hai số có n chữ số sẽ cần n² phép nhân và 2n phép cộng, vậy tổng số các phép tính đơn của phép nhân này là n² + 2n, chúng ta nói độ phức tạp thời gian của phép nhân này có bậc m².

Năm 1960, trong một tiết dạy về công nghệ thông tin, nhà toán học Nga, Viện sĩ Kolmogorov đã hỏi các sinh viên của mình là có ai tìm được cách tính phép nhân trên với thời gian tốt hơn bậc n² được không? Khi đó đây là một bài toán chưa có lời giải. Đúng một tuần sau, một sinh viên tên là Karatsuba đã đưa cho Viện sĩ Kolmogorov một lời giải tốt hơn về phép tính nhân trên chỉ với độ phức tạp thời gian bậc n^1,58496.

Quan sát và ước lượng thời gian thực hiện các đoạn chương trình 1 và 2 trong Hình 24.2. Chương trình nào chạy nhanh hơn? Vì sao?

Bước 2: HS thực hiện nhiệm vụ học tập: HS lắng nghe, suy nghĩ câu trả lời.

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

- GV gọi đại diện một số HS trả lời.

Gợi ý: Chương trình 1 chạy nhanh hơn vì chương trình 1 có 1 vòng lặp, chương trình 2 có 2 vòng lặp.

- HS khác nhận xét, bổ sung.

Bước 4: Đánh giá kết quả thực hiện:

- GV nhận xét câu trả lời của HS. Trên cơ sở đó, GV dẫn dắt HS vào bài học mới: Trong bài học trước, chúng ta đã được làm quen với khái niệm Độ phức tạp thời gian của thuật toán, được xác định là thời gian thực hiện chương trình/thuật toán. Thời gian này phụ thuộc vào khối lượng của dữ liệu cần phải lưu trữ trong quá trình thực hiện chương trình/thuật toán, đặc biệt liên quan tới các bước giải quyết một vấn đề cụ thể đưa ra trong chương trình thuật toán. Vậy căn cứ vào đâu để đánh giá thời gian thực hiện của một chương trình? Để tìm ra câu trả lời chính xác nhất trong câu hỏi Khởi động trên, chúng ta cùng vào - Bài 24: Đánh giá độ phức tạp thời gian thuật toán.

B. HOẠT ĐỘNG HÌNH THÀNH KIẾN THỨC

Hoạt động 1: Tìm hiểu về đánh giá thời gian thực hiện chương trình

a) Mục tiêu:

- HS biết và hiểu cách đánh giá (ước lượng) gần đúng thời gian chạy của thuật toán và chương trình.

- HS biết được khái niệm phép toán tích cực trong quá trình đánh giá.

b) Nội dung: GV đặt vấn đề, HS tìm hiểu thông tin mục 1 trang 111 - 113 SGK và thực hiện nhiệm vụ được giao.

c) Sản phẩm: Đánh giá thời gian thực hiện chương trình.

d) Tổ chức thực hiện:

HOẠT ĐỘNG CỦA GV VÀ HS	SẢN PHẨM DỰ KIẾN
Bước 1: GV chuyển giao nhiệm vụ: - GV đặt vấn đề theo Hoạt động 1 trang 112 SGK, yêu cầu HS thảo luận nhóm đôi trả lời câu hỏi: Quan sát và thực hiện đánh giá thời gian chạy của các chương trình 1 và 2 trong Hình 24.2. Từ đó biết và hiểu được cách đánh giá thời gian thực hiện chương trình.	1. Đánh giá thời gian thực hiện chương trình Cách đánh giá thời gian chạy chương trình được dựa trên một bộ khung các nguyên tắc dùng làm căn cứ để tính toán. Các nguyên tắc khung như sau: 1. Các phép toán đơn giản như phép tính số học + - */ phép lấy thương nguyên và số dư, các phép so sánh sẽ tinh là 1 đơn vị thời gian.

................................

................................

................................

Trên đây tóm tắt một số nội dung miễn phí trong bộ Kế hoạch bài dạy (KHBD) hay Giáo án Tin học 11 mới nhất, để mua tài liệu đầy đủ, Thầy/Cô vui lòng xem thử:

Xem thử

Xem thêm các bài soạn Giáo án Tin học lớp 11 Kết nối tri thức hay, chuẩn khác:

• Giáo án Tin học 11 Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

• Giáo án Tin học 11 Bài 26: Phương pháp làm mịn dần trong thiết kế chương trình

• Giáo án Tin học 11 Bài 27: Thực hành thiết kế chương trình theo phương pháp làm mịn dần

• Giáo án Tin học 11 Bài 28: Thiết kế chương trình theo mô đun

• Giáo án Tin học 11 Bài 29: Thực hành thiết kế chương trình theo mô đun

---