Giáo án NLS chuyên đề Tin học 12 KHMT Bài 16: Kĩ thuật duyệt đồ thị theo chiều rộng

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

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

BÀI 16: KĨ THUẬT DUYỆT ĐỒ THỊ THEO CHIỀU RỘNG

(2 tiết)

I. MỤC TIÊU

1. Kiến thức 

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

• Trình bày được ý tưởng của duyệt đồ thị theo chiều rộng.
• Mô phỏng được thuật toán duyệt theo chiều rộng.

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 rộ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 (BFS, BFS_Traversal, BFS_cycle, isCycle, FindPath) dựa trên hướng dẫn lập trình để giải quyết các bài toán duyệt đồ thị và tìm kiếm hành trình thực tế).
• 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 lập trình Python IDE để thiết kế, thực thi và kiểm thử hoạt động của giải thuật duyệt đồ thị theo chiều rộng (BFS) nhằm đổi mới phương thức biểu diễn và duyệt thủ công 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 đọc dữ liệu từ các file dữ liệu đầu vào (graph.inp hoặc danh sách kề) chứa thông tin đồ thị và nạp vào cấu trúc dữ liệu hàng đợi Q và mảng trạng thái mark bằng Python để tổ chức, lưu trữ và truy xuất dễ dàng trong quá trình duyệt đồ thị theo chiều rộng (BFS)).
• 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ả thứ tự duyệt BFS do Chatbot AI gợi ý với kết quả mô phỏng thủ công và lý thuyết SGK để đá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ố: chủ động tư duy giải thuật độc lập và tự gõ mã nguồn trước; chỉ sử dụng Chatbot AI dưới sự kiểm soát để gỡ lỗi (debug) cú pháp hàng đợi hoặc tối ưu hoá dòng lệnh; cam kết liêm chính học thuật và 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 thiết lập prompt thích hợp để nhờ Chatbot AI phân tích so sánh ưu, nhược điểm về hiệu năng (thời gian) và dung lượng bộ nhớ (không gian) của thuật toán BFS so với DFS, từ đó có định hướng thiết kế và tối ưu cấu trúc của hệ thống thông minh thực tế (như hệ thống tìm đường đi ngắn nhất GPS)).

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:
• Phiếu bài tập số/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 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

a. Mục tiêu: HS làm quen với ý tưởng của thuật toán duyệt theo chiều rộng và dự đoán cách thực hiện của thuật toán duyệt đồ thị này.

b. Nội dung: HS thực hiện hoạt động Khởi động SGK tr.75. 

c. Sản phẩm học tập: HS hoàn thành hoạt động Khởi động SGK tr.75.

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 yêu cầu HS hoạt động cá nhân, đọc kênh chữ, quan sát kênh hình và thực hiện hoạt động Khởi động SGK tr.75:

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 quan sát hình ảnh và thực hiện nhiệm vụ.

- GV hướng dẫn, 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 mời một số HS trả lời câu hỏi.

- Các HS còn lại chú ý lắng nghe, nhận xét và bổ sung (nếu cần thiết).

Gợi ý trả lời:

+ Nguyên tắc duyệt:

• Duyệt tất cả các đỉnh kề với đỉnh hiện tại trước khi chuyển sang đỉnh kề tiếp theo.
• Sử dụng hàng đợi (queue) để lưu trữ thứ tự duyệt.

+ Thứ tự duyệt có thể là:

• Bắt đầu từ đỉnh 0, thăm tất cả các đỉnh kề với đỉnh 0.
• Sau đó, duyệt qua các đỉnh kề với các đỉnh đã thăm theo thứ tự từ hàng đợi.
• Tiếp tục quá trình này cho đến khi tất cả các đỉnh đều được thăm.

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 đánh giá kết quả của HS, dẫn dắt HS vào bài học mới: Ngoài phương pháp duyệt đồ thị theo chiều sâu đã được giới thiệu ở Bài 14, chúng ta còn có thể duyệt đồ thị theo chiều rộng. Để tìm hiểu về phương pháp này, thầy/cô và cả lớp sẽ cùng nhau đến với Bài 16: Kĩ thuật duyệt đồ thị theo chiều rộng.

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

Hoạt động 1. Làm quen ý tưởng của thuật toán duyệt đồ thị theo chiều rộng

a. Mục tiêu: HS biết và nắm được ý tưởng của cách duyệt đồ thị theo chiều rộng và thực hiện được việc duyệt đồ thị thủ công.

b. Nội dung: GV giao nhiệm vụ; HS tìm hiểu nội dung mục 1. Ý tưởng duyệt đồ thị theo chiều rộng, thảo luận nhóm và thực hiện nhiệm vụ.

c. Sản phẩm: Ý tưởng của thuật toán duyệt đồ thị theo chiều rộng.

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

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

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

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

Hoạt động 2. Tìm hiểu thuật toán duyệt đồ thị theo chiều rộng

a. Mục tiêu: HS biết và thực hiện được thuật toán, chương trình duyệt đồ thị theo chiều rộng sử dụng hàng đợi.

b. Nội dung: GV giao nhiệm vụ; HS tìm hiểu nội dung mục 2. Thuật toán duyệt đồ thị theo chiều rộng (BFS – Breadth First Search) và thực hiện nhiệm vụ.

c. Sản phẩm: Thuật toán đệ quy duyệt đồ thị theo chiều rộng.

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

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

a. Mục tiêu: Giúp HS hệ thống lại kiến thức đã học.

b. Nội dung: GV giao nhiệm vụ cho HS, HS hoàn thành phiếu bài tập và phần Luyện tập SGK tr.79.

c. Sản phẩm học tập: Phiếu bài tập và phần Luyện tập SGK tr.79.

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ị viết được chương trình kiểm tra xem đồ thị G có chu trình hay không, kiểm tra xem có tồn tại đường đi từ s đến t hay không nếu có chỉ ra hành trình đi qua các đỉnh từ s đến t.

b. Nội dung: HS thực hiện hoạt động Vận dụng SGK tr.79.

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

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.79.

Câu 1. Cho đơn đồ thị vô hướng G = (V, E). Sử dụng thuật toán duyệt theo chiều rộng BFS, viết chương trình kiểm tra xem G có chu trình hay không. Chu trình (cycle) ở đây được hiểu là một đường đi khép kín, đỉnh xuất phát trùng với đỉnh kết thúc. Cần thiết lập hàm dạng Acycle(G), hàm trả lại True nếu G không có chu trình, ngược lại hàm trả lại False.

Câu 2. Cho đơn đồ thị G = (V, E) vô hướng hoặc có hướng. Cho trước hai đỉnh bất kì s và t. Viết chương trình kiểm tra xem có tồn tại đường đi từ s đến t hay không. Nếu có thì chương trình cần chỉ ra dãy các đỉnh tương ứng trên đường đi từ s đến t, nói cách khác chương trình cần chỉ ra một dãy các đỉnh , ,…, sao cho:

(, ) là cạnh của đồ thị với j = 1, 2,..., k; 

s = , t = .

- 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ó).

- GV quán triệt: "AI là một trợ lý ảo đắc lực để gỡ lỗi và phân tích; các em tuyệt đối không được sao chép code giải sẵn của AI để đối phó. Hãy thể hiện tinh thần liêm chính học thuật số kỉ nguyên AI".

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

- HS tiếp nhận và thực hiện nhiệm vụ.

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

- GV mời HS lần lượt lên bảng viết các hàm.

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

Gợi ý đáp án:

Câu 1. 

+ Ý tưởng của việc sử dụng BFS phát hiện chu trình trong đồ thị vô hướng G:

Sử dụng hai mảng đánh dấu mark[] và prev[]:

• mark[] dùng để đánh dấu các đỉnh đã duyệt, mark[v] = True khi và chỉ khi đỉnh v đã được duyệt.
• prev[] dùng để đánh dấu đỉnh phía trước trong quá trình duyệt. 

Ví dụ: Nếu đi theo một cạnh từ đỉnh v đến u (u bắt buộc là đỉnh kề của v), khi đó đặt prev[u] = v với ý nghĩa trong đường đi hiện thời, v đứng trước u.

+ Ý tưởng của thuật toán phát hiện chu trình: …………………………………………..

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

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

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 chuẩn kiến thức và kết thúc tiết học.

E. THÔNG TIN BỔ SUNG

Nhiều bài toán trên đồ thị phải cần sử dụng các kĩ thuật duyệt đồ thị. Duyệt đồ thị theo chiều rộng thường được sử dụng trong các bài toán sau:

1. Tìm kiếm trên đồ thị

- Tìm kiếm tất cả các đỉnh có thể truy cập được từ một đỉnh cho trước.

- Tìm đường đi ngắn nhất từ một đỉnh này tới một đỉnh khác.

2. Xác định cấu trúc của đồ thị

- Kiểm tra tính liên thông của đồ thị.

- Tìm số lượng thành phần liên thông trong đô thị.

So với duyệt đồ thị theo chiều sâu, duyệt đồ thị theo chiều rộng luôn tìm ra được đường đi ngắn nhất giữa hai đỉnh và nó dễ dàng triển khai hơn so với duyệt đồ thị theo chiều sâu. Tuy nhiên, duyệt đồ thị theo chiều rộng có thể cần sử dụng nhiều bộ nhớ hơn so với duyệt theo chiều sâu.

[3.4.NC1a: HS viết các chương trình sử dụng thuật toán duyệt theo chiều rộng.

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 kiến thức đã học ở Bài 16.

- Xem trước nội dung Bài 17: Thực hành duyệt đồ thị tổng hợp.