Ngày soạn:…/…/…

Ngày dạy:…/…/…

BÀI 13: THỰC HÀNH THIẾT LẬP ĐỒ THỊ

(2 tiết)

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:

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

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

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.

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. Data.inp 4 0 1 1 0 1 0 1 1 1 1 0 1 0 1 1 0 Hình 13.1. Tệp ma trận kề Yêu cầu xác định danh sách kề của đồ thị trên. Hướng dẫn: + Tạo tệp Data.inp, dữ liệu biểu diễn của đồ thị là ma trận kề trong tệp Data.inp. + Trong bài trước, chúng ta đã thiết lập hàm BuildGraph(fname) lấy dữ liệu từ tệp ma trận kề và trả về cặp dữ liệu V, A là danh sách đỉnh và ma trận kề của đồ thị. + Hãy viết hàm thể hiện danh sách kề trên màn hình theo đúng yêu cầu trên với tham số đầu vào là ma trận kề A. 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 theo đúng hướng dẫn để hoàn thành yêu cầu Nhiệm vụ 1. - Trong quá trình HS thực hành, GV quan sát, hỗ trợ, giải đáp các vướng mắc của HS. Bước 3: Báo cáo kết quả hoạt động và thảo luận - HS chạy chương trình và báo cáo kết quả cho GV. - GV quan sát bài làm của những HS đã chạy được trên máy tính. Bước 4: Đánh giá kết quả, thực hiện nhiệm vụ học tập - Từ kết quả thực hành của HS, GV nhận xét, đánh giá quá trình HS thực hiện nhiệm vụ. - Nhiệm vụ 1 được gọi là hoàn thành khi HS chạy chương trình và ra được kết quả như yêu cầu.

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 đủ: Kết quả thể hiện ra màn hình: Đỉnh kề với 0: 1 2 Đỉnh kề với 1: 0 2 3 Đỉnh kề với 2: 0 1 3 Đỉnh kề với 3: 1 2

Nhiệm vụ 2. Viết chương trình hiển thị ma trận kề, danh sách kề và bậc của đồ thị

a. Mục tiêu: Thiết lập được chương trình từ đầu vào là danh sách các cạnh, cần tính ma trận kề A, danh sách kề Adj và chi tiết bậc của các đỉnh của đồ thị.

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

c. Sản phẩm: Chương trình hiển thị ma trận kề, danh sách kề và bậc của đồ thị.

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ụ 2 và viết chương trình hiển thị ma trận kề, danh sách kề và bậc của đồ thị trên máy tính theo hướng dẫn. Đơn đồ thị vô hướng G = (V,E) được cho bởi danh sách các cạnh. Danh sách các cạnh được cho trong tệp văn bản, trong đó dòng đầu tiên là số các đỉnh của đồ thị, các dòng tiếp theo mỗi dòng mô tả một cạnh của đồ thị. Edges.inp 4 0 1 1 3 0 2 2 3 1 2 Hình 13.2. Tệp danh sách các cạnh Yêu cầu tính ma trận kề, danh sách kề và bậc của tất cả các đỉnh của đồ thị G. Hướng dẫn: ………………….

Nhiệm vụ 2. Viết chương trình hiển thị ma trận kề, danh sách kề và bậc của đồ thị - Hàm AdjacencyMatrix(Adj): - Hàm show(A,op): \ - Hàm show_deg(Adj): - Phần chương trình chính: * Chương trình đầy đủ: ……………………..

--------------------------------------

--------------------- Còn tiếp ----------------------