Giáo án NLS chuyên đề Tin học 11 KHMT Bài 2: Thiết kế thuật toán đệ quy

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

Ngày dạy:…/…/…

BÀI 2: THIẾT KẾ THUẬT TOÁN BẰNG ĐỆ QUY

I. MỤC TIÊU

1. Kiến thức

Sau bài học này, HS sẽ:

• Ứng dụng được kĩ thuật đệ quy trong việc thiết kế một vài thuật toán đơn giản.
• Nhận biết được tính ưu việt của kĩ thuật đệ quy trong thiết kế thuật toán.

2. 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 giải quyết vấn đề với sự hỗ trợ của công nghệ thông tin và truyền thông.
• Sử dụng được ngôn ngữ lập trình bậc cao, qua đó phát triển tư duy điều khiển và tự động hóa.

Năng lực số:

• 2.1.NC1a: Tương tác thông qua công nghệ số (HS xem video được tạo bởi công cụ AI và trả lời câu hỏi, sử dụng máy tính cá nhân hoặc thiết bị di động có kết nối Internet để làm bài tập trắc nghiệm củng cố trên môi trường số).
• 3.4.NC1a: Lập trình (HS tự thực hiện viết code và chạy chương trình Python cài đặt các hàm đệ quy đơn giản).
• 5.1.NC1a: Giải quyết các vấn đề kĩ thuật (HS tự chẩn đoán nguyên nhân và áp dụng các giải pháp khắc phục các lỗi kỹ thuật số phát sinh khi lập trình trên Python).
• 5.3.NC1a: Sử dụng sáng tạo công nghệ số (HS sử dụng công cụ lập trình Python (PyCharm, VS Code hoặc công cụ trực tuyến) để tự tay thiết kế, viết code, chạy thử và hoàn thiện các chương trình đệ quy đơn giản).
• 6.2.NC1a: Sử dụng trí tuệ nhân tạo (HS sử dụng công cụ AI hoặc sản phẩm số do GV cung cấp để tiếp nhận thông tin, trả lời câu hỏi đơn giản).
• 1.1.NC1a: Duyệt, tìm kiếm và lọc dữ liệu, thông tin và nội dung số (HS tiếp cận, khai thác được thông tin từ nguồn học liệu số dưới sự hướng dẫn của GV).

Năng lực AI:

• 11.A1.2: AI để nâng cao năng lực (HS nhận thức rõ AI giúp lập trình viên viết code cực nhanh để nâng cao hiệu suất của con người, nhưng con người (lập trình viên) vẫn phải giữ quyền kiểm soát tối cao để kiểm thử, phát hiện lỗi sai, phê duyệt và chịu trách nhiệm pháp lý cao nhất đối với chất lượng phần mềm).
• 11.B2.1: Phòng tránh rủi ro khi sử dụng AI (HS thể hiện trách nhiệm học thuật số bằng việc tự lực tư duy thuật toán, tự viết code Python và thực hiện kiểm chứng chéo kết quả, cam kết sử dụng AI có kiểm soát và không lạm dụng sao chép code đối phó).

3. Phẩm chất

• Hình thành, phát triển năng lự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; sử dụng được ngôn ngữ lập trình bậc cao, qua đó phát triển tư duy điểu khiển và tự động hoá.
• Hình thành ý thức 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, KHBD Chuyên đề học tập Tin học 11 – Định hướng Khoa học máy tính.
• Phòng thực hành máy tính đã cài đặt Python và có kết nối Internet, máy chiếu.
• Hình ảnh, sơ đồ minh họa cho các bước thực hiện trên một mẫu dữ liệu đơn giản hoặc có thể sử dụng các phần mềm mô phỏng thuật toán để minh họa thêm trong quá trình giảng dạy.
• Học liệu số & Công cụ AI:
• Bộ câu hỏi trắc nghiệm trên phần mềm Quizizz/website kenhhoctap.edu.vn.
• Video AI được tạo bằng các công cụ AI để khởi động bài học.
• Công cụ Chatbot AI (ChatGPT/Gemini).

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

• SGK Chuyên đề học tập Tin học 11 – Định hướng Khoa học máy tính.
• Vở ghi. 

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

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

a. Mục tiêu: 

- Gợi ý để dẫn đến việc thiết kế chương trình hay hàm đệ quy. Từ ý tưởng của bạn An. GV khơi gợi HS đến ý tưởng của thiết kế đệ quy.

- Kích thích sự tò mò cho người học.

b. Nội dung: GV cho các nhóm HS trao đổi để nhận ra các tính chất chung nhất của các hiện tượng, khái niệm này và tìm thêm nhiều ví dụ khác trong thực tế

c. Sản phẩm học tập: HS dựa vào kiến thức và hiểu biết cá nhân để đưa ra câu trả lời.

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

Bước 1: GV chuyển giao nhiệm vụ học tập

- GV yêu cầu xem video AI được thiết kế để phục vụ bài dạy và trả lời câu hỏi xuất hiện trong video đó.

- GV dẫn dắt: An được giao tìm một thiết kế mới cho bài toán tính tổng S(n)= 1+2 +..+n

An nhận thấy S(n) có thẻ được viết như sau:

S(n)=1+2+..+n=1+2+..+n-1+n=S(n-1)+n

Do đó, việc tính S(n) có thể được tính từ S(n - 1), tương tự S(n - 1) lại có thể được tính từ S(n - 2), cứ như vậy, cuối cùng sẽ dẫn đến cần tính S(0), nhưng S(0) = 0.

- GV đặt câu hỏi: Em có thẻ giúp An hoàn thiện ý tưởng trên thành một chương trình hay không?

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

- HS xem video và suy nghĩ câu trả lời.

- HS lắng nghe, suy nghĩ và đưa ra câu trả lời.

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

- GV mời HS trả lời câu hỏi. 

- Các HS khác nhận xét, nêu ý kiến khác (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, đánh giá và kết luận.

[6.2.NC1a: HS sử dụng công cụ AI hoặc sản phẩm số do GV cung cấp để tiếp nhận thông tin, trả lời câu hỏi đơn giản.

2.1.NC1a: HS thực hiện các tương tác cơ bản với học liệu số (xem video, trả lời câu hỏi trên môi trường số).

1.1.NC1a: HS tiếp cận, khai thác được thông tin từ nguồn học liệu số dưới sự hướng dẫn của GV.]

- GV dẫn dắt vào nội dung bài mới: Qua bài học này, chúng ta có thể học được cách để giúp bạn An hoàn thiện ý tưởng của mình bằng một chương trình - Bài 2: Thiết kế thuật toán bằng đệ quy.

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

Hoạt động 1: Ý tưởng thiết kế theo kĩ thuật đệ quy

a. Mục tiêu: HS biết được các ý tưởng và thiết kế đệ quy của một số bài toán đơn giản.

b. Nội dung: GV yêu cầu HS tìm hiểu Hoạt động 1 SGK trang 11, đọc thông tin mục 1, thảo luận nhóm và xây dựng kiến thức mới.

c. Sản phẩm học tập: HS nêu được khái niệm ý tưởng thiết kế theo kĩ thuật đệ quy và trả lời được các Câu hỏi củng cố kiến thức SGK trang 13.

d. Tổ chức hoạt động:

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

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

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

Hoạt động 2: Thuật toán tìm kiếm nhị phân

a. Mục tiêu: HS hiểu được cách thiết kế đệ quy cho bài toán tìm kiếm nhị phân.

b. Nội dung: GV đọc và yêu cầu thực hiện Hoạt động 2 SGK trang 13, trả lời Câu hỏi SGK trang 14.

c. Sản phẩm học tập: HS nêu được cách thiết kế đệ quy cho bài toán tìm kiếm nhị phân., hoàn thành các bài tập trong phần Câu hỏi SGK trang 14.

d. Tổ chức hoạt động:

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

a. Mục tiêu: HS vận dụng kiến thức, hoàn thành bài tập phần Luyện tập và các câu hỏi trắc nghiệm.

b. Nội dung: GV giao nhiệm vụ, HS thảo luận.

c. Sản phẩm học tập: HS viết các hàm đệ quy cho chương trình để giải các bài toán.

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

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

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

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

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

a. Mục tiêu: HS vận dụng kiến thức, liên hệ với thực tế để giải quyết vấn đề.

b. Nội dung: GV tổ chức cho HS làm bài tập phần Vận dụng SGK trang 14.

c. Sản phẩm học tập: HS viết và chạy thử chương trình.

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

Bước 1: GV chuyển giao nhiệm vụ học tập

- GV nêu yêu cầu bài toán:

Bài 1. Viết chương trình tính tổng S = 1!+ 2! +... +n! theo hai cách:

a) Không sử dụng kĩ thuật đệ quy.

b) Có sử dụng kĩ thuật đệ quy.

Bài 2. Chúng ta đã biết thuật toán sắp xếp chèn trên dãy A cho trước theo hàm sau

Hãy thiết kế lại chương trình trên sử dụng kĩ thuật đệ quy.

Bài 3. Bạn An đã nghĩ ra thuật toán tìm kiếm nhị phân bằng kĩ thuật đệ quy theo cách khác như sau:

a) Chương trình của bạn An có đúng không?

b) Trong chương trình trên, phần cơ sở là những lệnh nào?

- GV nhấn mạnh: "Sự hỗ trợ của AI trong việc sinh code giúp gia tăng năng suất đáng kể, nhưng không thay thế được vai trò kiểm soát và trách nhiệm pháp lý của lập trình viên đối với sản phẩm".

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

- HS thực hiện nhiệm vụ ở nhà.

- Đầu tiết học sau, GV kiểm tra bài làm của HS.

- GV hướng dẫn, theo dõi, hỗ trợ HS nếu cần thiết. 

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

- GV gợi ý:

Bài 1. a) Hàm tính tổng S = 1!+ 2! +... +n! không sử dụng kĩ thuật đệ quy.

b) Hàm tính tổng ở câu a có sử dụng kĩ thuật đệ quy.

Bài 2. Có thể viết lại hàm sắp xếp chèn sử dụng kĩ thuật đệ quy như sau: 

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

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

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

- GV mời đại diện HS 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 giá, nhận xét, chuẩn kiến thức.

[3.4.NC1a: HS tự thực hiện viết code và chạy chương trình Python.

5.1.NC1a: HS tự chẩn đoán nguyên nhân và áp dụng các giải pháp khắc phục các lỗi kỹ thuật số phát sinh khi lập trình trên Python.

6.2.NC1a: HS sử dụng công cụ AI hỗ trợ tìm, phân tích và gỡ lỗi.

11.B2.1: HS tự tư duy thuật toán và viết code; không copy code từ Chatbot AI để đối phó, tránh vi phạm nội quy nhà trường.

11.A1.2: HS nhận thức rõ: AI lập trình tự động để nâng cao hiệu suất của con người, nhưng con người (lập trình viên) vẫn phải giữ quyền kiểm soát tối cao để kiểm thử, phát hiện lỗi sai, phê duyệt và chịu trách nhiệm pháp lý cao nhất đối với chất lượng chương trình.]

* HƯỚNG DẪN VỀ NHÀ:

• Ôn lại kiến thức đã học.
• Hoàn thành bài tập phần Vận dụng.
• Đọc và tìm hiểu trước Bài 3: Thực hành giải toán theo kĩ thuật đệ quy.