Giáo án NLS chuyên đề Tin học 12 KHMT Bài 15: Thực hành duyệt đồ thị theo chiều sâu

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

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

BÀI 15: THỰC HÀNH DUYỆT ĐỒ THỊ THEO CHIỀU SÂU

(2 tiết)

I. MỤC TIÊU

1. Kiến thức 

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

• Thực hành duyệt đồ thị theo chiều sâu.

2. Năng lực

Năng lực chung:

• Tự chủ và tự học: Chủ động học tập, tìm hiểu nội dung bài học.
• Giải quyết vấn đề và sáng tạo: Trả lời được các câu hỏi, giải quyết được các vấn đề với sự hỗ trợ của công nghệ thông tin và truyền thông.
• Giao tiếp và hợp tác: Biết lựa chọn hình thức làm việc nhóm với quy mô phù hợp với yêu cầu và thực hiện tốt nhiệm vụ.

Năng lực Tin học:

• Duyệt được đồ thị theo chiều sâu.
• Kiểm tra được đồ thị có chu trình hay không.

Năng lực số:

• 3.4.NC1a: Lập trình (HS tự viết, đọc, chỉnh sửa và gỡ lỗi cú pháp các hàm Python DFS_acyclic, Acyclic, DFS_acyclic_trace để thực thi nhiệm vụ xác định chu trình đồ thị).
• 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ố).
• 5.3.NC1a: Sử dụng sáng tạo công nghệ số (HS sử dụng môi trường Python IDE để trực tiếp lập trình, biên dịch và chạy thực tế thuật toán phát hiện chu trình, thay thế cách giải quyết toán học truyền thống bằng giải pháp công nghệ tối ưu).
• 1.3.NC1a: Quản lí dữ liệu, thông tin và nội dung số (HS thực hiện thao tác bóc tách thông tin về ràng buộc kiến thức chuyên đề từ tệp văn bản Data.inp và tổ chức cấu trúc nạp vào mảng trạng thái status và danh sách kề Adj bằng ngôn ngữ Python để lưu trữ và truy xuất dễ dàng trên máy tính).
• 1.2.NC1a: Đánh giá dữ liệu, thông tin và nội dung số (HS thực hiện phân tích, đối chiếu kết quả tìm chu trình tự vẽ trên giấy với kết quả do công cụ Chatbot AI đề xuất để đánh giá độ chính xác và độ tin cậy của thông tin số).
• 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:

• 12.A3.1: Trách nhiệm công dân trong xã hội có AI (HS thể hiện trách nhiệm học thuật số: tự suy nghĩ giải thuật toán kiểm tra chu trình và vẽ sơ đồ vết đi ra giấy trước khi lập trình; cam kết liêm chính số, chỉ sử dụng Chatbot AI dưới sự kiểm soát như một trợ lý để giải thích lỗi cú pháp (debug), bắt lỗi ngoại lệ tệp dữ liệu hoặc gợi ý tối ưu thuật toán tìm chu trình cụ thể, tuyệt đối không lạm dụng copy code của AI để đối phó).
• 12.C2.1: Các yêu cầu dành cho công cụ AI hỗ trợ các hoạt động học tập và xã hội (HS biết cách thiết lập prompt phù hợp nhờ Chatbot AI so sánh sự khác biệt và hiệu năng khi phát hiện chu trình đồ thị bằng thuật toán DFS (status 0,1,2) với thuật toán sắp xếp liên tục (Topological Sort / Kahn's algorithm) để tích lũy kiến thức thiết kế hệ thống thông minh tối ưu).

3. Phẩm chất

• Chăm chỉ: Tích cực tìm tòi và sáng tạo trong học tập.
• Trung thực: Thực hiện đúng phần việc của bản thân và hợp tác làm việc nhóm khi được giao nhiệm vụ. Có ý thức báo cáo kết quả một cách chính xác.
• Trách nhiệm: Hoàn thành các bài tập theo yêu cầu của GV thông qua hệ thống câu hỏi, phiếu học tập, thông qua sản phẩm.

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 12 – Định hướng Khoa học máy tính.
• Phòng thực hành máy tính cài đặt sẵn môi trường lập trình Python (IDLE, PyCharm, VS Code,…) và có kết nối Internet, máy trình chiếu.
• Học liệu số & Công cụ AI:
• Bộ câu hỏi trắc nghiệm trên 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 12 – Đị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

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

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

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

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

Nhiệm vụ. Hệ thống chuyên đề học tập

a. Mục tiêu: HS biết và hiểu thuật toán kiểm tra một đồ thị có chu trình hay không và áp dụng giải bài toán có ý nghĩa cụ thể trong thực tế.

b. Nội dung: GV hướng dẫn HS thực hành trên máy tính theo hướng dẫn trong SGK để hoàn thành Nhiệm vụ.

c. Sản phẩm: Chương trình kiểm tra một đồ thị có chu trình hay không.

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

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

a. Mục tiêu: HS thông hiểu các hàm đã xây dựng và chỉnh sửa được chương trình đáp ứng yêu cầu bài toán.

b. Nội dung: GV hướng dẫn HS thực hiện hoạt động Luyện tập SGK tr.74.

c. Sản phẩm học tập: HS hoàn thành hoạt động Luyện tập SGK tr.74.

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 đã học về đồ thị, thuật toán duyệt chiều sâu chỉnh sửa, viết được chương trình kiểm tra đồ thị có chu trình hay không biết đồ thị biểu diễn đồ thị dưới dạng ma trận kề hoặc danh sách kề.

b. Nội dung: GV hướng dẫn HS thực hiện hoạt động Vận dụng SGK tr.74.

c. Sản phẩm học tập: HS hoàn thành hoạt động Vận dụng SGK tr.74.

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 HS làm việc cá nhân, hoàn thành bài tập phần Vận dụng SGK tr.74.

Câu 1. Sửa lại chương trình bổ sung thông báo nếu hệ thống chuyên đề không hợp lí thì thông báo dãy các chuyên đề có mâu thuẫn về kiến thức.

Câu 2. Mở rộng bài tập trên cho đồ thị có hướng bất kì G = (V, E), được biểu diễn bởi ma trận kề A hoặc danh sách kề Adj. Viết hàm kiểm tra xem đồ thị G có chu trình hay không, nếu có thì hiển thị trên màn hình chu trình đó, bao gồm dãy các đỉnh tham gia vào chu trình.

- GV định hướng khai thác AI có trách nhiệm (Khi nào nên/không nên dùng AI): 

+ HS tư duy và tự lập trình mã nguồn Python. 

+ Sau khi tự gõ xong bản nháp code, HS được phép sử dụng Chatbot AI làm trợ lý để tối ưu hóa code và gỡ lỗi biên dịch (nếu có).

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

- HS tiếp nhận, suy nghĩ thực hiện nhiệm vụ.

- GV quan sát, theo dõi và hỗ trợ HS khi cần thiết.

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

- GV lần lượt mời HS thao tác viết từng hàm cho cả lớp quan sát.

- HS khác chú ý quan sát và nhận xét bài làm của các bạn.

Gợi ý đáp án:

Câu 1. Chương trình được sửa lại như sau:

+ Sửa lại hàm kiểm tra tính không mâu thuẫn của các chuyên đề:

+ Bổ sung hàm in dãy các chuyên đề có mâu thuẫn, nếu có:

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

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

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

Bước 4: Đánh giá kết quả thực hiện nhiệm vụ học tập

- GV chữa bài.

- GV nhận xét quá trình HS thực hành và kết thúc tiết học.

[3.4.NC1a: HS viết, đọc và điều chỉnh các hàm Python giải quyết bài toán sử dụng kĩ thuật duyệt đồ thị theo chiều sâu.

5.3.NC1a: HS áp dụng công cụ lập trình Python IDE thiết kế, thực thi thành công chương trình kiểm thử các bài toán vận dụng trên môi trường lập trình.

12.A3.1: HS thể hiện trách nhiệm học thuật số thông qua việc tự lập trình thuật toán trước, sử dụng AI có kiểm soát để debug mã nguồn, rà soát tính chuẩn xác và cam kết không phụ thuộc hoàn toàn vào công cụ công nghệ.]

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

- Xem lại các nội dung thực hành ở Bài 15.

- Xem trước nội dung Bài 16: Kĩ thuật duyệt đồ thị theo chiều rộng.