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

Ngày soạn: .../.../...

Ngày dạy: .../.../...

BÀI 25: THỰC HÀNH XÁC ĐỊNH ĐỘ PHỨC TẠP THỜI GIAN THUẬT TOÁ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.

Năng lực số:

• 6.2.NC1b: Sử dụng AI để hỗ trợ phân tích mã nguồn, kiểm tra lại kết quả tính toán độ phức tạp thủ công).
• 5.2.NC1b: Sử dụng IDE để chạy thực nghiệm, đo lường thời gian xử lý thực tế nhằm kiểm chứng lý thuyết.
• 1.2.NC1a: Đánh giá hiệu quả giải thuật dựa trên năng lực xử lý của phần cứng máy tính hiện đại.

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 GV 

• SGK, tài liệu giảng dạy, giáo án PPT.
• Phòng thực hành máy tính kết nối Internet.
• Máy chiếu.
• Video AI tạo bằng công cụ AI được dùng để khởi động bài học.

2. Đối với HS 

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

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

1. 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:

…………………………………………..

…………………………………………..

…………………………………………..
 

2. HOẠT ĐỘNG THỰC HÀNH

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:

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:

…………………………………………..

…………………………………………..

…………………………………………..
 

3. HOẠT ĐỘNG LUYỆN TẬP

a) Mục tiêu: HS củng cố cách xác định độ phức tạp của thuật toán.

b) Nội dung: HS vận dụng các kiến thức đã học để hoàn thành bài tập phần Luyện tập trang 117 SGK.

c) Sản phẩm học tập: Câu trả lời nội dung Luyện tập.

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

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

- GV tổ chức cho HS làm Bài 1, 2 phần Luyện tập trang 117 SGK:

Bài 1: Xác định độ phức tạp của thuật toán sắp xếp nổi bọt sau:

1        def BubbleSort(A):

2                 n = len(A)

3                 for i in range(n-1):

4                           for j in range(n-1-i):

5                                    if A[j] > A[j+1]:

6                                              A[j],A[j+1] = A[j+1],A[j]

Bài 2: Cho biết hàm sau sẽ trả về giá trị là bao nhiêu? Xác định độ phức tạp thời gian O-lớn của chương trình.

1        def Mystery(n):

2                 r = 0

3                 for i in range(n-1):

4                           for j in range(i+1,n):

5                                    for k in range(1,j):

6                                              r = r+1

7                 return r

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

- HS suy nghĩ, hoàn thành các bài tập GV yêu cầu.

- GV quan sát và hỗ trợ, hướng dẫn.

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

- HS thực hiện các thao tác.

Bài 1. Xác định độ phức tạp của thuật toán sắp xếp nổi bọt

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, T(n) là thời gian thực hiện của thuật toán. Thời gian chạy của thuật toán được phân tích như sau:

- Câu lệnh tại dòng 2 tốn một đơn vị thời gian.

- Vòng lặp for tại dòng 3, biến i chạy từ o đến n – 2, nên vòng lặp này có n – 1 bước lặp.

- Tại mỗi bước lặp của vòng lặp for tại dòng 3, chương trình sẽ thực hiện:

• Vòng lặp for tại dòng 4, biến j chạy từ 0 đến n-1-i-1, vậy vòng lặp này thực hiện n-i-1 bước lặp.
• Tại mỗi bước lặp của vòng lặp tại dòng 4, chương trình thực hiện một lệnh so sánh tại dòng 5 và 3 lệnh để thực hiện việc đổi chỗ tại dòng 6 (nếu điều kiện thỏa mãn).

Tổng hợp lại, chương trình của thuật toán sắp xếp nổi bọt đưa ra có thời gian chạy là:

T(n) = 1 +

T(n) = 1 + 4*

T(n) = 1 + 4*

T(n) = 1+ 2n(n – 1)

T(n) = 2n² – 2n + 1.

Bước 2. Xác định độ phức tạp O của thuật toán.

T(n) = 2n² – 2n + 1 = O(n²).

Bài 2. Viết lại thuật toán cần tính độ phức tạp thời gian:

…………………………………………..

…………………………………………..

…………………………………………..
 

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

- GV chữa bài, chốt đáp án, tuyên dương các hoạt động tốt, nhanh và chính xác.

[1.2.NC1a: HS tính được độ phức tạp thời gian của thuật toán.]

4. HOẠT ĐỘNG VẬN DỤNG

a) Mục tiêu: HS thực hiện làm bài tập Vận dụng để nắm vững kiến thức.

b) Nội dung: HS vận dụng kiến thức đã học và hiểu biết của bản thân để làm bài tập Vận dụng trang 117 SGK.

c) Sản phẩm: Câu trả lời nội dung Vận dụng.

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

…………………………………………..

…………………………………………..

…………………………………………..