Giáo án Tin học 11 Kết nối tri thức 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 Kết nối tri thức Bài 25: Thực hành xác định độ 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:

- Thực hành xác định độ phức tạp thời gian thuật toán.

- Biết cách ước lượng thời gian thuật toán, chương trình và 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:

- Thực hành xác định độ phức tạp thời gian thuật toán.

- Biết cách ước lượng thời gian thuật toán, chương trình và 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: HS nhắc lại các bước để xác định độ phức tạp thời gian tính toán của thuật toán.

b) Nội dung: GV tổ chức trả lời câu hỏi ở phần Mở đầu.

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: Biết cách phân tích, đánh giá độ phức tạp thuật toán là kĩ năng quan trọng của người thiết kế thuật toán và chương trình.

- GV đặt câu hỏi yêu cầu HS trả lời: Các quy tắc đơn giản tính độ phức tạp thời gian mạng lại cho em điều khi khi đánh giá thuật toán?

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: Đánh giá được mức đơn giản của thuật toán, từ đó tìm ra được cách giải nhanh nhất.

- 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 các bài học trước, chúng ta được được thực hành viết chương trình cho bài toán tìm kiếm và bài toán sắp xếp. Hãy vận dụng kiến thức đã học để xác định độ phức tạp thời gian tính toán của các bài toán trên. Chúng ta cùng vào - Bài 25: Thực hành xác định độ phức tạp thời gian của thuật toán.

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

Hoạt động 1: Thực hiện nhiệm vụ 1

a) Mục tiêu: Giúp HS xác định độ phức tạp thời gian tính toán của thuật toán tìm kiếm tuần tự.

b) Nội dung: GV tổ chức cho HS thực hiện theo các hoạt động trong SGK và thực hiện xác định độ phức tạp thời gian tính toán của thuật toán tìm kiếm tuần tự.

c) Sản phẩm: Sản phẩm thực hành của HS.

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 chia lớp thành các nhóm từ 2 – 4 HS. - GV chiếu nhiệm vụ học tập: Xác định độ phức tạp thời gian tính toán của thuật toán tìm kiếm tuần tự được thể hiện bằng chương trình sau: 1 def LinearSearch(A,K): 2           for i in range(len(A)): 3                   if A[i] == K: 4                           return i 5           return -1 - GV hướng dẫn HS theo hai bước: Bước 1. Phân tích thời gian tính toán của thuật toán dựa vào phân tích các câu lệnh để tính tổng số phép tính cơ bản của chương trình. Bước 2. Từ tổng số phép tính cơ bản của chương trình, GV hướng dẫn HS xác định độ phức tạp của thuật toán. Bước 2: HS thực hiện nhiệm vụ học tập: - HS lắng nghe GV hướng dẫn, thực hiện nhiệm vụ. - GV quan sát và trợ giúp HS. Bước 3: Báo cáo kết quả hoạt động, thảo luận: - HS báo cáo kết quả xác định độ phức tạp thời gian tính toán của thuật toán tìm kiếm tuần tự. - HS khác nhận xét, bổ sung cho bạn. Bước 4: Đánh giá kết quả thực hiện: - Sau khi HS hoàn thành chương trình, GV nhận xét và tổng kết nội dung nhiệm vụ 1. - GV chuyển sang hoạt động tiếp theo.

Nhiệm vụ 1 Bước 1. Phân tích thời gian tính toán của thuật toán. - Gọi n là kích thước của mảng đầu vào, T(n) là thời gian thực hiện thuật toán. - Đối với mã lệnh trên, chương trình sẽ thực hiện duyệt mảng và với mỗi bước lặp sẽ kiểm tra phần tử thứ i có bằng với phần tử cần tìm kiếm không (dòng 3). + Nếu bằng thì chương trình sẽ trả về chỉ số của phần tử tìm thấy và kết thúc (dòng 4). → Chương trình có thể kết thúc khi chưa duyệt hết mảng (trường hợp đã tìm thấy phần tử) và tối đa là duyệt hết mảng. → Trong trường hợp tồi nhất vòng lặp ở dòng 2 sẽ thực hiện n bước lặp, mỗi bước lặp sẽ thực hiện lệnh so sánh ở dòng 3 tốn 1 đơn vị thời gian. - Lệnh trả về sẽ được thực hiện duy nhất một lần ở dòng 4 (trường hợp tìm thấy phần tử trong mảng) hoặc dòng 5 (trường hợp không tìm thấy phần tử trong mảng) → mất 1 đơn vị thời gian. Do đó, tổng số phép tính cơ bản của chương trình trong trường hợp tồi nhất là T(n) = n + 1. Bước 2. Xác định độ phức tạp O-lớn của thuật toán T(n) = n + 1 = O(n + 1) = O(max(n, 1)) = O(n). Vậy thuật toán tìm kiếm tuần tự có độ phức tạp tuyến tính.

Hoạt động 2: Thực hiện nhiệm vụ 2

a) Mục tiêu: Giúp HS xác định độ phức tạp của thuật toán sắp xếp chọn.

b) Nội dung: GV tổ chức cho HS thực hiện theo các hoạt động trong SGK và thực hiện xác định độ phức tạp của thuật toán sắp xếp chọn.

c) Sản phẩm: Sản phẩm thực hành của HS.

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 chiếu nhiệm vụ học tập: Xác định độ phức tạp của thuật toán sắp xếp chọn được thể hiện bằng chương trình sau: 1 def SelectionSort(A): 2           n = len(A) 3           for i in range(n-1):

Nhiệm vụ 2 Bước 1. Phân tích thời gian tính toán của thuật toán. Gọi n là kích thước của mảng A, T(n) là thời gian chạy của thuật toán. Thời gian chạy của thuật toán được phân tích như sau: - Lệnh gán ở dòng 2 tốn 1 đơn vị thời gian, - Vòng lặp tại dòng 3 biến i sẽ chạy từ 0 đến n - 2, vậy vòng lặp này có n - 1 bước lặp. - Tại mỗi bước lặp của lệnh for tại dòng 3 chương trình sẽ thực hiện các lệnh sau: + Lệnh gán tại dòng 4 tốn 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 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

• Giáo án Tin học 11 Bài 30: Thiết lập thư viện cho chương trình

---