Giáo án chuyên đề Khoa học máy tính 12 cánh diều Bài 3: Thực hành các thao tác cơ bản với đồ thị trên máy tính

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

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

BÀI 3: THỰC HÀNH CÁC THAO TÁC CƠ BẢN 
VỚI ĐỒ THỊ TRÊN MÁY TÍNH

(2 tiết)

I. MỤC TIÊU

1. Kiến thức

Sau bài học này, HS sẽ:

• Thực hiện được các thao tác cơ bản với đồ thị được biểu diễn bằng ma trận kề và danh sách kề. Biết được ưu, nhược điểm của hai cách biểu diễn.

• Đọc hiểu được một số đoạn chương trình sử dụng cách biểu diễn ma trận kề, danh sách kề.

• Biết được ưu, nhược điểm của hai cách biểu diễn.

2. Năng lực

Năng lực chung:

• Tự chủ và tự học: Chủ động, tích cực thực hiện công việc của cá nhân.

• Giao tiếp và hợp tác: Phân tích được các công việc cần thực hiện để hoàn thành nhiệm vụ của nhóm trong các hoạt động nhóm.

• Giải quyết vấn đề và sáng tạo: Nêu được nhiều ý tưởng mới trong học tập, suy nghĩ không theo lối mòn, tạo ra yếu tố mới dựa trên những ý tưởng khác nhau.

Năng lực Tin học:

• Thực hiện được các thao tác cơ bản với đồ thị được biểu diễn bằng ma trận kề và danh sách kề trên máy tính.

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, các máy tính có kết nối internet.

• SGK, SGV Chuyên đề học tập Tin học 12 – Định hướng Khoa học máy tính – Cánh diều.

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 – Cánh diều.

III. TIẾN TRÌNH DẠY HỌC

A. HOẠT ĐỘNG KHỞI ĐỘNG

a. Mục tiêu: HS ôn tập lại cách biểu diễn đồ thị bằng ma trận kề, danh sách kề.

b. Nội dung: HS dùng danh sách kề để biểu diễn đồ thị. 

c. Sản phẩm học tập: Ma trận kề và danh sách kề.

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á nhân, hoàn thành yêu cầu sau: 

Em hãy dùng ma trận kề và danh sách kề biểu diễn đồ thị sau:

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

- HS vận dụng những kiến thức đã học để hoàn thành hoạt động.

Bước 3: Báo cáo kết quả hoạt động và thảo luận

- GV mời một số HS xung phong trình bày đáp án.

- HS khác lắng nghe, nhận xét và bổ sung.

Gợi ý trả lời:

+ Ma trận kề:

+ Danh sách kề

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 đã biết cách biểu diễn đồ thị trên máy tính bằng ma trận kề và danh sách kề. Để giúp các em ôn tập lại kiến thức đồng thời được thực hành theo nội dung lí thuyết đã học, chúng ta sẽ cùng nhau đến với Bài 3: Thực hành các thao tác cơ bản với đồ thị trên máy tính.

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

a. Mục tiêu: HS xây dựng được ma trận kề và danh sách kề biểu diễn đồ thị.

b. Nội dung: HS làm việc độc lập, thực hiện các yêu cầu của bài toán Giao hữu bóng đá.

c. Sản phẩm: HS hoàn thành các yêu cầu của bài toán Giao hữu bó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 yêu cầu HS đọc sách, dựa vào đồ thị minh hoạ ở Hình 1 để hiểu rõ về bài toán và nắm được thông tin các trận đấu tại thời điểm xét, sau đó thực hiện các yêu cầu của bài toán theo hướng dẫn. Bài toán Giao hữu bóng đá Có 6 đội bóng (các đội được đánh số từ 0 đến 5) tham gia đá giao hữu, theo thể thức mỗi cặp đội thi đấu với nhau không quá một trận và với mỗi trận sẽ luôn phân định thắng thua, không có hòa. Hình 1 là một đồ thị biểu diễn thông tin các trận đấu đã diễn ra tính đến thời điểm hiện tại, trong đó mỗi đội tương ứng với một đỉnh của đồ thị, nếu có một cạnh nối từ đỉnh i tới đỉnh j thì cho biết hai đội i, j đã đấu với nhau và đội i giành chiến thắng (0 ≤ i, j ≤ 5). a) Em hãy cho biết đến thời điểm hiện tại có bao nhiêu trận đấu đã diễn ra; liệt kê tất cả các trận, mỗi trận được mô tả bằng cặp số i, j có ý nghĩa là đội i đấu với đội j và đội i giành chiến thắng. b) Xây dựng ma trận kề biểu diễn đồ thị. c) Xây dựng danh sách kề biểu diễn đồ thị. d) Em hãy cho biết đội số 2 đã thi đấu bao nhiêu trận, trong đó có bao nhiêu trận thắng, bao nhiêu trận thua. Hình 1. Đồ thị biểu diễn thông tin các trận đấu đã diễn ra ở thời điểm hiện tại Hướng dẫn: a) Xét lần lượt từng đội, với mỗi đội i (0 ≤ i ≤ 5) liệt kê các trận thắng của đội đó. b) Coi mỗi đội là một đỉnh của đồ thị, mỗi trận đấu là một cạnh của đồ thị. Xây dựng ma trận gồm 6 hàng và 6 cột (các hàng đánh số từ 0 đến 5 và từ trên xuống dưới; các cột đánh số từ 0 đến 5 và từ trái sang phải). Điền lần lượt cho từng hàng; Nếu đội i thắng đội j thì trên hàng i, cột j ghi số 1; ngược lại ghi số 0. c) Dựa vào ma trận đã xây dựng ở yêu cầu b) để liệt kê các đỉnh kề của mỗi đỉnh. d) Số trận thắng của đội i (0 ≤ i ≤ 5) là số các số 1 trên hàng i của ma trận đã xây dựng ở yêu cầu b), còn số trận thua của đội i (0 ≤ i ≤ 5) là số các số 1 trên cột i của ma trận. ………………………..

Bài toán Giao hữu bóng đá a) Đến thời điểm hiện tại có 8 trận đấu đã diễn ra (chính là số cạnh của đồ thị): (0, 1), (0, 2), (0, 5), (2, 1), (2, 3), (3, 4), (3, 5),  (4, 5). b) Ma trận kề biểu diễn đồ thị:   0 1 2 3 4 5 0 0 1 1 0 0 1 1 0 0 0 0 0 0 2 0 1 0 1 0 0 3 0 0 0 0 1 1 4 0 0 0 0 0 1 5 0 0 0 0 0 0 c) Danh sách kề biểu diễn đồ thị: PHẦN TỬ GIÁ TRỊ g[0] [1, 2, 5] g[1] [] g[2] [1, 3] g[3] [4, 5] g[4] [5] g[5] [] d) Đội số 2 đã thi đấu 3 trận, trong đó có 2 trận thắng và 1 trận thua.

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

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