Giáo án chuyên đề Khoa học máy tính 12 cánh diều Bài 5: Thực hành duyệt đồ thị

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

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

BÀI 5: THỰC HÀNH DUYỆT ĐỒ THỊ

(2 tiết)

I. MỤC TIÊU

1. Kiến thức

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

• Tìm hiểu được một số ứng dụng thực tế của duyệt đồ thị.

• So sánh được hai cách duyệt đồ thị theo chiều rộng và chiều sâu.

2. Năng lực

Năng lực chung:

• Tự chủ và tự học: Chủ động, tích cực thực hiện công việc của cá nhân.

• Giao tiếp và hợp tác: Phân tích được các công việc cần thực hiện để hoàn thành nhiệm vụ của nhóm trong các hoạt động nhóm.

• Giải quyết vấn đề và sáng tạo: Nêu được nhiều ý tưởng mới trong học tập, suy nghĩ không theo lối mòn, tạo ra yếu tố mới dựa trên những ý tưởng khác nhau.

Năng lực Tin học:

• Vận dụng thuật toán duyệt đồ thị vào các bài toán thực tế.

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:

• Máy chiếu, máy tính, màn hình hiển thị, hoặc ti vi.

• Phòng thực hành, các máy tính có kết nối internet.

• SGK, SGV Chuyên đề học tập Tin học 12 – Định hướng Khoa học máy tính – Cánh diều.

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

• Các dụng cụ học tập theo yêu cầu của GV; SGK Chuyên đề học tập Tin học 12 – Định hướng Khoa học máy tính – Cánh diều.

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

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

a. Mục tiêu: HS ôn tập lại cách duyệt đồ thị theo chiều sâu.

b. Nội dung: HS thực hiện nhiệm vụ học tập theo yêu cầu của GV. 

c. Sản phẩm học tập: Kết quả duyệt đồ thị theo chiều sâu.

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 yêu cầu sau: 

Hãy liệt kê thứ tự duyệt các đỉnh với thuật toán duyệt đồ thị theo chiều sâu xuất phát từ đỉnh A của đồ thị sau:

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

- HS vận dụng những kiến thức đã học để hoàn thành nhiệm vụ học tập.

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 xung phong trình bày đáp án.

- HS khác lắng nghe, nhận xét và bổ sung.

Gợi ý trả lời:

Có nhiều kết quả duyệt theo chiều sâu xuất phát từ đỉnh A, ví dụ: A, G, F, I, H, J…

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

GV đánh giá kết quả của HS, dẫn dắt HS vào bài học mới: Trong bài học trước, các em đã biết cách duyệt đồ thị theo chiều rộng và chiều sâu. Để giúp các em ôn tập lại kiến thức đồng thời được thực hành theo nội dung lí thuyết đã học, chúng ta sẽ cùng nhau đến với Bài 5: Thực hành duyệt đồ thị.

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

a. Mục tiêu: HS ứng dụng được thuật toán duyệt đồ thị theo chiều rộng để giải bài toán thực tế.

b. Nội dung: HS thực hành theo nhóm, thực hiện bài toán Phân nhóm người nghi nhiễm COVID-19.

c. Sản phẩm: HS hoàn thành bài toán Phân nhóm người nghi nhiễm COVID-19.

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

HOẠT ĐỘNG CỦA GV - HS

DỰ KIẾN SẢN PHẨM

Bước 1: GV chuyển giao nhiệm vụ học tập - GV chia lớp thành các nhóm 3 – 4 HS. - GV yêu cầu các nhóm đọc sách, dựa vào đồ thị minh hoạ ở Hình 1 để hiểu rõ về bài toán, sau đó thảo luận nhóm và thực hiện nhiệm vụ theo hướng dẫn. Bài toán Phân nhóm người nghi nhiễm COVID-19 Một nhóm gồm 7 người được đánh số từ 0 đến 6, có một số cặp người thường xuyên tiếp xúc trao đổi với nhau được mô tả như trong Hình 1. Một ngày, người 0 xét nghiệm và được xác định là bị nhiễm COVID-19, người ta cần phân 7 người thành các nhóm, người 0 sẽ thuộc nhóm F0, những người tiếp xúc với người ở nhóm F0 sẽ được xếp vào nhóm F1, những người tiếp xúc với người ở nhóm F1 sẽ được xếp vào nhóm F2,… Hình 1. Nhóm gồm 7 người và mối quan hệ thường xuyên tiếp xúc Nhiệm vụ: Dùng thuật toán duyệt đồ thị theo chiều rộng bắt đầu từ người 0 để phân nhóm người nghi nhiễm COVID-19. Gợi ý: Dùng mảng hàng đợi Q để thăm các đỉnh theo chiều rộng, mảng level để ghi nhận nhóm nghi nhiễm, Hình 2, 3, 4 mô tả ba bước đầu tiên trong quá trình thực hiện. Hình 4. Trạng thái ở bước 3 Bước 2: HS thực hiện nhiệm vụ học tập - Các nhóm thảo luận và thực hiện nhiệm vụ thực hành theo hướng dẫn. - GV quan sát và trợ giúp 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 đại diện các nhóm báo cáo kết quả thảo luận. - Các nhóm nhận xét, bổ sung cho nhau.  Bước 4: Đánh giá kết quả, thực hiện nhiệm vụ học tập - Từ kết quả thực hành, GV nhận xét, đánh giá quá trình HS thực hiện nhiệm vụ.

Bài toán Phân nhóm người nghi nhiễm COVID-19 Quá trình thực hiện phân nhóm người nghi nhiễm COVID-19: Bước 1: Q 0             level 0             Bước 2: Q 0 1 2         level 0 1 1         Bước 3: Q 0 1 2 3 4     level 0 1 1 2 2     Bước 4: Q 0 1 2 3 4     level 0 1 1 2 2     Bước 5: Q 0 1 2 3 4 5   level 0 1 1 2 2 3   Bước 6: Q 0 1 2 3 4 5   level 0 1 1 2 2 3   Bước 7: Q 0 1 2 3 4 5 6 level 0 1 1 2 2 3 4 Bước 8: Q 0 1 2 3 4 5 6 level 0 1 1 2 2 3 4

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

a. Mục tiêu: HS luyện tập duyệt đồ thị theo chiều sâu.

b. Nội dung: HS thực hiện duyệt đồ thị theo chiều sâu.

c. Sản phẩm học tập: Kết quả duyệt đồ thị theo chiều sâu.

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

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

- GV tiếp tục tổ chức cho HS thực hành theo nhóm, hoàn thành bài tập sau:

Cho đồ thị sau:

Nếu thực hiện duyệt theo chiều sâu bắt đầu từ đỉnh A thì thứ tự các đỉnh được duyệt sẽ như thế nào? 

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

- HS thảo luận nhóm và thực hiện nhiệm vụ học tập.

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

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

- GV mời đại diện các nhóm trình bày từng bước thực hiện.

- Các nhóm chú ý theo dõi và nhận xét cho nhau.

Gợi ý đáp án: 

Bước 1: Thực hiện DFS(A), đánh dấu đỉnh A đã thăm và thêm đỉnh A vào ngăn xếp; chỉ có B là đỉnh kề của đỉnh A và đỉnh B chưa được thăm, gọi DFS(B).

Bước 2: Thực hiện DFS(B), đánh dấu đỉnh B đã thăm và thêm đỉnh B vào ngăn xếp. Có hai đỉnh C, H kề với B và đều chưa được thăm, theo thứ tự DFS(C) được gọi và thực hiện trước.

Bước 3: Thực hiện DFS(C), đánh dấu đỉnh C đã thăm và thêm đỉnh C vào ngăn xếp. Có hai đỉnh D, E kề với C và đều chưa được thăm, theo thứ tự DFS(D) được gọi và thực hiện trước.

Bước 4: 

+ Thực hiện DFS(D), đánh dấu đỉnh D đã thăm và thêm đỉnh D vào ngăn xếp.

+ Do đã xét hết đỉnh kề của đỉnh D nên DFS(D) kết thúc. Lấy đỉnh D ra khỏi ngăn xếp.

Bước 5: 

+ Quay về DFS(C), xét E là đỉnh kề tiếp theo của đỉnh C; vì đỉnh E chưa được thăm nên gọi DFS(E).

+ Thực hiện DFS(E), đánh dấu đỉnh E đã thăm và thêm đỉnh E vào ngăn xếp. Có ba đỉnh F, G, H kề với E và đều chưa được thăm, theo thứ tự DFS(F) được gọi và thực hiện trước.

--------------------------------------

--------------------- Còn tiếp ----------------------