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

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

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 sâu.

- Mô phỏng được thuật toán duyệt 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.

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 bài toán duyệt các đỉnh của đồ thị, có liên hệ với các thuật toán duyệt (tìm kiếm) đã biết trên kiểu dữ liệu mảng (một chiều) và dữ liệu cây.

b. Nội dung: GV tổ chức cho HS hoạt động nhóm và thực hiện phần Khởi động SGK tr.65.

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

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

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, yêu cầu các nhóm thảo luận và thực hiện hoạt động Khởi động SGK tr.65:

Chúng ta đã biết bài toán và thuật toán duyệt (tìm kiếm) dữ liệu trên các cấu trúc dữ liệu khác nhau: - Kiểu dữ liệu mảng (một hoặc hai chiều). - Kiểu dữ liệu cây (cây nhị phân và cây tìm kiếm nhị phân). Vậy với dữ liệu của đồ thị, việc duyệt các đỉnh của đồ thị sẽ được thực hiện như thế nào? Quan sát hai đồ thị ở Hình 14.1 và thảo luận với bạn cách thực hiện duyệt trên các đỉnh của đồ thị đó.

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

- Các nhóm quan sát hình ảnh và thảo luận 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 đại diện một số nhóm trình bày kết quả thảo luận.

- Các nhóm 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:

Có thể duyệt đồ thị theo các cách sau:

+ Duyệt theo chiều sâu: Bắt đầu từ một đỉnh, tiếp tục đi sâu vào đồ thị theo một nhánh cho đến khi không thể đi xa hơn, sau đó quay lại và tiếp tục với nhánh khác.

+ Duyệt theo chiều rộng: Bắt đầu từ một đỉnh, duyệt tất cả các đỉnh kề với nó trước, sau đó mới chuyển sang duyệt các đỉnh ở mức độ sâu tiếp theo.

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: Duyệt đồ thị là một bài toán quan trọng trong tin học. Có hai cách duyệt đồ thị chính là duyệt theo chiều sâu và duyệt theo chiều rộng. Hôm nay, chúng ta sẽ cùng nhau tìm hiểu phương pháp đầu tiên qua Bài 14: Kĩ thuật duyệt đồ thị theo chiều sâu.

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

Hoạt động 1. Tìm hiểu ý tưởng của thuật toán duyệt đồ thị theo chiều sâu

a. Mục tiêu: Thông qua một ví dụ cụ thể HS làm quen và biết được cách duyệt đầu tiên: duyệt theo chiều sâu (DFS).

b. Nội dung: GV giao nhiệm vụ; HS làm việc độc lập, tìm hiểu nội dung mục 1. Bài toán duyệt đồ thị 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 sâu.

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 - Từ hoạt động Khởi động, GV yêu cầu HS suy nghĩ và trả lời câu hỏi: + Theo em, bài toán duyệt đồ thị là gì? - GV yêu cầu HS đọc Hoạt động 1 – Tìm hiểu ý tưởng của thuật toán duyệt đồ thị theo chiều sâu SGK tr.65, từ đó dẫn dắt HS tìm hiểu kiến thức. Tìm hiểu ý tưởng của thuật toán duyệt đồ thị theo chiều sâu (DFS –  Depth First Search). - GV trình bày ý tưởng của thuật toán duyệt đồ thị theo chiều sâu và hướng dẫn HS cách duyệt thông qua ví dụ cụ thể. - GV yêu cầu HS vận dụng kiến thức vừa tìm hiểu, thực hiện hoạt động Củng cố kiến thức tr.67 SGK: Câu 1. Thứ tự các đỉnh trong danh sách kề có ảnh hưởng đến thứ tự các đỉnh được duyệt của thuật toán DFS không? Câu 2. Mô tả quá trình duyệt theo chiều sâu của đồ thị có hướng trong Hình 14.1b nếu xuất phát từ đỉnh 4.

1. Bài toán duyệt đồ thị - Bài toán duyệt đồ thị là cần duyệt (đánh dấu) tất cả các đỉnh bằng cách đi theo các cạnh của đồ thị. - Ý tưởng của thuật toán duyệt đồ thị theo chiều sâu: Mỗi khi xuất phát từ một đỉnh chưa được duyệt, cần đi dọc theo các cạnh theo hướng “sâu” nhất có thể, tức là luôn cố gắng duyệt theo hướng “ra xa” khỏi đỉnh ban đầu, đi tới đỉnh nào thì đánh dấu (duyệt) đỉnh đó, duyệt cho đến khi không đi được nữa thì quay lại đỉnh trước để tìm cách đi khác, cứ như vậy cho đến khi không tìm được đường đi nào nữa thì dừng lại. Quá trình như vậy lặp lại cho đến khi tất cả các đỉnh của đồ thị đã được đánh dấu. Ví dụ: Thuật toán duyệt đồ thị vô hướng trong Hình 14.1a theo chiều sâu. Giả sử bắt đầu duyệt từ đỉnh 0. Mũi tên màu đỏ chỉ hướng đi theo cạnh. 1. Bắt đầu từ đỉnh 0. Duyệt (đánh dấu) đỉnh 0.

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

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

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

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 15: Thực hành duyệt đồ thị theo chiều sâu

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

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

---