Giáo án Chuyên đề Tin học 12 Kết nối tri thức Bài 15: Thực hành 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 15: Thực hành 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ẽ:

- Thực hành duyệt đồ thị 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.

- Kiểm tra được đồ thị có chu trình hay khô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 nhắc lại khái niệm chu trình và bài toán kiểm tra một đồ thị cho trước có chu trình hay không?

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

c. Sản phẩm học tập: Thuật toán DFS 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 lập, nhớ lại kiến thức đã học và thực hiện hoạt động Khởi động SGK trang 72:

Trong lí thuyết đồ thị, chu trình được định nghĩa là một đường đi không tầm thường khép kín, tức là đường đi có số cạnh lớn hơn 1 và đỉnh xuất phát trùng với đỉnh kết thúc. Làm cách nào để kiểm tra một đồ thị cho trước có chu trình hay 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:

Đồ thị dưới đây là một đồ thị có chu trình:

Có thể sử dụng thuật toán DFS duyệt theo chiều sâu để kiểm tra một đồ thị cho trước có chu trình hay không:

+ Bắt đầu từ một đỉnh bất kì trong đồ thị.

+ Thực hiện duyệt DFS từ đỉnh này.

+ Trong quá trình duyệt, nếu đỉnh nào đã được thăm trước đó và không phải là đỉnh cha của đỉnh hiện tại (trong trường hợp của cây), tức là tìm thấy một chu trình.

+ Nếu tất cả các đỉnh đều đã được duyệt và không tìm thấy chu trình, đồ thị không chứa chu trình.

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

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

Nhiệm vụ. Hệ thống chuyên đề học tập

a. Mục tiêu: HS biết và hiểu thuật toán kiểm tra một đồ thị có chu trình hay không và áp dụng giải bài toán có ý nghĩa cụ thể trong thực 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 kiểm tra một đồ thị có chu trình hay khô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 tổ chức cho HS thực hành cá nhân, đọc Nhiệm vụ SGK tr.72. Trường em từ năm học này sẽ tổ chức mở rất nhiều chuyên đề học tập cho học sinh lựa chọn, các chuyên đề sẽ được học trong các thời gian khác nhau. Các chuyên đề được đánh số từ 0 đến n – 1 với n là số tự nhiên. Tuy nhiên giữa các chuyên đề này có quan hệ ràng buộc kiến thức, ví dụ quan hệ (i, j) chỉ ra rằng muốn học chuyên đề i thì cần học trước chuyên đề j. Dữ liệu đầu vào dưới dạng tệp văn bản Data.inp như sau: • Dòng đầu tiên là số tự nhiên n (số các chuyên đề học tập của trường em).

Nhiệm vụ. Hệ thống chuyên đề học tập - Nếu coi tập hợp các chuyên đề học tập của trường em là một mô hình đồ thị thì: • Mỗi chuyên đề là một đỉnh được đánh số từ 0 đến n – 1. • Mỗi quan hệ ràng buộc kiến thức (i, j) là một cạnh có hướng từ đỉnh i đến đỉnh j. $\to$ Đồ thị là đồ thị có hướng. - Đồ thị này không có chu trình tương đương với tính hợp lí của hệ thống các chuyên đề. $\Rightarrow$ Với bài toán trên chúng ta cần kiểm tra xem đồ thị các chuyên đề có chu trình hay không. - Ý tưởng của việc kiểm tra này sẽ được thực hiện bằng cách duyệt theo chiều sâu của đồ thị, bắt đầu từ một đỉnh bất kì. Để thực hiện được việc này chúng ta sẽ đưa vào mảng tổng thể các trạng thái status[] của đồ thị có ý nghĩa như sau: • status[v] = 0 nếu đỉnh v chưa được xét (hoặc duyệt). • status[v] = 1 chỉ ra đỉnh này đang trong quá trình duyệt. • status[v] = 2 nếu đỉnh này đã được duyệt xong. - Công việc kiểm tra chu trình được thực hiện thông qua hai bước sau: • Hàm DFS_acyclic(Adj,s) kiểm tra trong quá trình duyệt bắt đầu từ đỉnh s có gặp chu trình hay không. Việc kiểm tra này khá đơn giản, bắt đầu duyệt từ đỉnh s có trạng thái bằng 0, nếu trong quá trình duyệt gặp đỉnh có trạng thái 1, tức là đã có chu trình.

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

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

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

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

---