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

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

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 thiết lập đồ thị theo các bộ dữ liệu khác nhau.

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:

- Biểu diễn được đồ thị bằng ma trận kề và danh sách kề.

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 ôn lại các kiến thức đã biết từ hai bài học trước.

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

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

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 trao đổi, thảo luận và thực hiện hoạt động Khởi động SGK trang 62:

Em hãy trao đổi, thảo luận và trả lời một số câu hỏi sau: - Nếu đồ thị là vô hướng thì ma trận kề có đặc điểm gì? - Phân biệt sự giống nhau và khác nhau giữa ma trận kề và danh sách kề? - Khái niệm bậc của các đỉnh có gì khác nhau trong trường hợp đồ thị là vô hướng, có hướng?

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

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

Gợi ý trả lời:

- Nếu đồ thị vô hướng thì ma trận kề sẽ là ma trận đối xứng, nghĩa là với mọi đỉnh i, j ta có $A_{ịj}= A_{ji}$.

- Sự giống nhau và khác nhau giữa ma trận kề và danh sách kề:

+ Khác nhau:

• Khác nhau về định nghĩa.

• Khác nhau về khuôn dạng thể hiện.

+ Giống nhau:

• Đều là bộ dữ liệu xác định duy nhất để biểu diễn một đồ thị.

• Đều được biểu diễn bằng list trong Python.

- Khái niệm bậc của các đỉnh:

+ Đối với đồ thị vô hướng: Bậc của đỉnh u (deg(u)) là số lượng các đỉnh kề với u.

Đồ thị vô hướng

Ta có:

• Số cạnh của đồ thị là 6.

• deg(0) + deg(1) + deg(2) + deg(3) + deg(4) = 2 + 2 + 4 + 2 + 2 = 12 = 6 x 2.

$\Rightarrow$ Trong đồ thị vô hướng thì tổng số bậc của tất cả các đỉnh bằng hai lần số cạnh.

+ Đối với đồ thị có hướng:

• Bậc ra của đỉnh u (deg+(u)) là số lượng các đỉnh kề với u.

• Bậc vào của đỉnh u (deg-(u)) là số các đỉnh có cạnh nối đến u.

Đồ thị có hướng

Ta có:

• deg+(0) + deg+(1) + deg+(2) + deg+(3) + deg+(4) = 1 + 3 + 1 + 2 + 0 = 7.

• deg-(0) + deg-(1) + deg-(2) + deg-(3) + deg-(4) = 3 + 0 + 1 + 1 + 2 = 7.

$\Rightarrow$Trong đồ thị có hướng thì tổng số bậc ra của tất cả các đỉnh bằng tổng số bậc vào của tất cả các đỉ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 hai bài học trước, các em đã được làm quen với khái niệm đồ thị và các cách biểu diễn biểu diễn đồ thị. Để 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 13: Thực hành thiết lập đồ thị.

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

Nhiệm vụ 1. Viết chương trình hiển thị danh sách kề

a. Mục tiêu: Thiết lập được chương trình hiển thị danh sách kề từ dữ liệu đầu vào là ma trận kề.

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

c. Sản phẩm: Chương trình hiển thị danh sách kề.

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 yêu cầu, phân tích Nhiệm vụ 1 và viết chương trình hiển thị danh sách kề trên máy tính theo hướng dẫn. Đơn đồ thị vô hướng G = (V,E) được cho bởi ma trận kề A. Ma trận A được cho trong tệp văn bản có dạng như hình bên.	Nhiệm vụ 1. Viết chương trình hiển thị danh sách kề Hàm hiển thị danh sách kề: * Chương trình đầy đủ:

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

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

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

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

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

---