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

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

Xem thử

Chỉ từ 200k mua trọn bộ Kế hoạch bài dạy (KHBD) hay Giáo án Chuyên đề Tin học 12 Kết nối tri thức chuẩn kiến thức, trình bày đẹp mắt, dễ dàng chỉnh sửa:

• B1: gửi phí vào tk: 1133836868 - CT TNHH DAU TU VA DV GD VIETJACK - Ngân hàng MB (QR)
• B2: Nhắn tin tới Zalo VietJack Official - nhấn vào đây để thông báo và nhận giáo án

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.

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.

- SGK, SGV Chuyên đề học tập Tin học 12 – Định hướng Khoa học máy tính – Kết nối tri thức.

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 – Kết nối tri thức.

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

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

Chúng ta đã làm quen với thuật toán duyệt đồ thị theo chiều sâu, quá trình duyệt đi “sâu” nhất có thể theo các cạnh của đồ thị. Ngoài ra còn có cách duyệt đồ thị theo chiều rộng, được hình dung như khi đổ nước xuống một sàn nhà phẳng, nước sẽ lan toả ra xung quanh theo các hình tròn đồng tâm. Cách duyệt theo chiều rộng có thể được mô phỏng như Hình 16.1a. Hình 16.1. Duyệt đồ thị lan toả theo các mức Giả sử ta bắt đầu duyệt từ đỉnh 0 của đồ thị Hình 16.1b theo chiều rộng. Theo em, chúng ta sẽ duyệt các đỉnh theo nguyên tắc nào và duyệt theo thứ tự nào?

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

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

B. 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 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 yêu cầu HS làm việc theo nhóm 3 – 4 HS, thực hiện Hoạt động 1 – Làm quen ý tưởng của thuật toán duyệt đồ thị theo chiều rộng SGK tr.75. Thực hiện công việc duyệt theo chiều rộng của đồ thị Hình 16.1b, bắt đầu từ đỉnh 0. Các bước thực hiện sẽ duyệt các đỉnh theo trình tự sau: • Mức 0: Bản thân đỉnh 0. • Mức 1: Các đỉnh kề với đỉnh mức 0. • Mức 2: Các đỉnh là kề với đỉnh mức 1. Đỉnh mức 2 là các đỉnh mà tồn tại đường đi từ đỉnh 0 đến đỉnh này theo 2 cạnh, qua đỉnh mức 1. Quá trình cứ tiếp tục như vậy cho đến khi không thể duyệt thêm được nữa. Trao đổi, thảo luận nhóm để nhận biết sự khác biệt giữa hai phương pháp duyệt đồ thị theo chiều sâu và chiều rộng khác nhau như thế nào. - GV cho HS quan sát lại Hình 16.1b và yêu cầu: + Em hãy dựa vào các bước duyệt đồ thị theo chiều rộng bắt đầu từ đỉnh 0 được trình bày ở Hoạt động 1 để hoàn thành bảng sau:

1. Ý tưởng duyệt đồ thị theo chiều rộng - Bảng các đỉnh được duyệt theo chiều rộng, xuất phát từ đỉnh 0. Bảng 16.1. Duyệt các đỉnh theo mức $\to$ Nếu duyệt theo cách trên thì thứ tự các đỉnh được duyệt là: 0  1  2  6  9  3  4  7  8  10  5 - Theo cách trên, việc duyệt đồ thị theo chiều rộng được bắt đầu từ đỉnh s bất kì. Thực hiện lần lượt theo các đỉnh cùng mức 0, 1, 2,… • Đỉnh mức 0 chính là s. • Mức 1 bao gồm các đỉnh kề với s,… • Mức k sẽ bao gồm các đỉnh kề với đỉnh mức k − 1, tức là có tồn tại đường đi k cạnh từ đỉnh s. - Cho trước hai đỉnh s và f: • Nếu tồn tại đường đi k cạnh từ s đến f và k là số nhỏ nhất thì ta nói f có khoảng cách k đến đỉnh s. • Nếu không có đường đi từ s đến f thì ta nói khoảng cách từ s đến f là $\infty$ (vô cùng).

................................

................................

................................

Trên đây tóm tắt một số nội dung miễn phí trong bộ Kế hoạch bài dạy (KHBD) hay Giáo án Chuyên đề Tin học 12 mới nhất, để mua tài liệu đầy đủ, Thầy/Cô vui lòng xem thử:

Xem thử

Xem thêm các bài soạn Giáo án Chuyên đề Tin học lớp 12 Kết nối tri thức hay, chuẩn khác:

• Giáo án Chuyên đề Tin học 12 Bài 12: Biểu diễn đồ thị

• Giáo án Chuyên đề Tin học 12 Bài 13: Thực hành thiết lập đồ thị

• Giáo án Chuyên đề Tin học 12 Bài 14: Kĩ thuật duyệt đồ thị theo chiều sâu

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

• Giáo án Chuyên đề Tin học 12 Bài 17: Thực hành duyệt đồ thị tổng hợp

---