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

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

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ẽ:

- Thực hành duyệt đồ thị theo chiều rộng.

- Thực hành ứng dụng kĩ thuật duyệt đồ thị trong một số bài toán thực tế.

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, phòng thực hành.

- 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 được gợi ý tìm hiểu các ứng dụng của thuật toán duyệt đồ thị theo chiều rộng.

b. Nội dung: HS hoạt động cá nhân và thực hiện phần Khởi động SGK tr.80.

c. Sản phẩm học tập: Một số ứng dụng thực tế của thuật toán duyệt đồ thị theo chiều rộng.

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 lập, vận dụng những kiến thức đã học và thực hiện hoạt động Khởi động SGK trang 80:

Trong bài thực hành trước chúng ta đã được ôn tập và giải một số bài toán có áp dụng thuật toán duyệt đồ thị theo chiều sâu. Còn về thuật toán duyệt theo chiều rộng em có biết gì về các ứng dụng thực tế của bài toán này không?

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

- HS tiếp nhận 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 1 – 2 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.

Gợi ý trả lời:

Một số ứng dụng thực tế của thuật toán duyệt đồ thị theo chiều rộng:

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

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

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 đã được làm quen với kĩ thuật duyệt đồ thị theo chiều rộng. Để giúp các em ôn tập lại kiến thức và được thực hành dựa trên lí thuyết đã học, chúng ta sẽ cùng nhau đến với Bài 17: Thực hành duyệt đồ thị tổng hợp.

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

Nhiệm vụ. Tìm đường đi xe đạp

a. Mục tiêu: HS tìm hiểu, trao đổi để hiểu bài toán cần giải quyế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 tìm đường đi xe đạp.

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 tổ chức cho HS thực hành cá nhân, đọc Nhiệm vụ SGK tr.80. Các bạn học sinh lớp em (được đánh số từ 0 đến n – 1) có nhà ở trải rộng khắp thành phố. Trong thành phố có những đường đi chỉ dành cho xe cơ giới, nhưng cũng có đường đi dành cho xe đạp. Các bạn học sinh lớp em chỉ biết đi xe đạp. Dữ liệu đầu vào gồm hai tệp. Tệp Danh-sach.inp sẽ lưu tên các bạn trong lớp, tên mỗi bạn ghi trên một dòng. Tệp thứ hai, Xe-dap.inp mô tả các con đường có thể đi xe đạp từ nhà một bạn trong lớp đến nhà bạn khác. Tệp này cũng có nhiều dòng, mỗi dòng là hai số tự nhiên i, j cách nhau bởi dấu cách, chỉ ra từ nhà bạn thứ i có thể đi xe đạp được đến nhà bạn j. Các đường đi xe đạp này là hai chiều. Tệp danh sách lớp học Danh-sach.inp bắt đầu là số tự nhiên n, n dòng tiếp theo mỗi dòng là tên của các bạn học sinh trong lớp. Tệp lưu thông tin các đường đi xe đạp xe-dap.inp có dòng đầu tiên là số tự nhiên n, các dòng tiếp theo, mỗi dòng chỉ một đường đi bằng xe đạp giữa hai bạn học sinh trong lớp được mô tả bằng hai số tự nhiên cách nhau bởi dấu cách.

Nhiệm vụ. Tìm đường đi xe đạp - Nếu coi tập hợp các đường đi xe đạp là một mô hình đồ thị thì: • Mỗi học sinh là một đỉnh được đánh số từ 0 đến n – 1. • Mỗi đường đi bằng xe đạp giữa hai bạn học sinh là một cạnh. - Từ dữ liệu đầu vào (tệp Danh-sach.inp và Xe-dap.inp) dễ dàng thiết lập được đồ thị vô hướng G = (V, E) ứng với danh sách kề Adj. Bài toán: Cho trước hai đỉnh i, j bất kì của đồ thị, cần tìm một đường đi (nếu có) từ i đến j. - Bài toán có thể giải được dễ dàng bằng cách duyệt đồ thị theo chiều rộng, bắt đầu từ đỉnh i, nếu trong quá trình duyệt gặp đỉnh j thì có thể thiết lập đường đi từ i đến j. - Xây dựng chương trình: • Hàm BFS(Adj,s) duyệt theo chiều rộng bắt đầu từ đỉnh s sử dụng hai mảng mark[] và prev[]: o mark[v] = True khi và chỉ khi đỉnh v đã được đánh dấu khi duyệt đồ thị. o prev[v] = Đỉnh đã được duyệt trước v. Như vậy, nếu u = prev[v] tức là nếu có đường đi từ vị trí s ban đầu đến v thì u sẽ đứng ngay trước v o Ban đầu toàn bộ mảng mark[] được gán giá trị False, toàn bộ mảng prev[] được gán giá trị None. Vậy nếu prev[v] = None, tức là không tồn tại đường đi từ s đến v. • Hàm đệ quy printpath(s,t) biểu diễn đường đi từ đỉnh s đến t. Trong hàm này sử dụng mảng names[] lưu tên các học sinh trong lớp. Mảng này là kết quả của hàm Getnames(fname).

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

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

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

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 16: Kĩ thuật duyệt đồ thị theo chiều rộng

---