Giáo án chuyên đề Khoa học máy tính 12 cánh diều Bài 6 Dự án học tập: Tìm hiểu các vấn đề ứng dụng đồ thị

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 nêu mục đích, yêu cầu chung của dự án học tập.

- GV đưa ra một số hướng dẫn, gợi ý thực hiện dự án và tiêu chí đánh giá sản phẩm học tập.

- GV gợi ý một số vấn đề có thể thực hiện trong dự án học tập.

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

- HS chú ý lắng nghe.

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

- HS hiểu được mục đích, yêu cầu chung, cách thực hiện dự án và tiêu chí đánh giá sản phẩm.

Bước 4: Đánh giá kết quả, thực hiện nhiệm vụ học tập

- GV tổng kết lại các nội dung chính liên quan đến dự án.

1. Mục đích của dự án học tập

Dự án nhằm mục đích giúp học sinh khám phá, tìm hiểu các vấn đề liên quan đến đồ thị. Sau khi hoàn thành xong dự án, học sinh có khả năng:

• Tìm kiếm, khai thác, học hỏi mở rộng kiến thức từ các nguồn tài nguyên về lập trình trên mạng Internet.

• Vận dụng được kiến thức đã học để giải quyết các vấn đề cụ thể, thông thường.

• Tăng cường được khả năng làm việc nhóm.

2. Yêu cầu chung

• Lớp chia thành 4 nhóm độc lập. Mỗi nhóm lập trưởng nhóm và thảo luận tự chọn một vấn đề liên quan đến đồ thị.

• Thời gian thực hiện dự án là 2 tuần. Các nhóm sẽ thực hiện tạo sản phẩm ngoài giờ lên lớp và trong 2 tiết các nhóm báo cáo kết quả tại lớp, mỗi nhóm 15 phút.

3. Hướng dẫn thực hiện dự án

a) Lập kế hoạch

Bước 1. Xác định mục tiêu dự án.

• Nhóm thảo luận lựa chọn, thống nhất bài toán.

• Các nhóm có thể lựa chọn một trong các bài toán ở mục 5.

Bước 2. Lập danh sách các công việc chính, thời gian thực hiện, hoàn thành.

Bước 3. Dự kiến sản phẩm.

b) Thực hiện dự án

• Xác định các vấn đề liên quan đến dự án.

• Xây dựng một số ví dụ minh hoạ và mã giả giải quyết vấn đề.

• Sử dụng các lệnh trong Python để viết chương trình, thử nghiệm, kiểm thử để sửa lỗi, hiệu chỉnh chương trình (nếu có).

c) Báo cáo kết quả

Tiến trình thực hiện như đề xuất tham khảo trong bảng sau đây:

4. Tiêu chí đánh giá

Việc đánh giá nội dung dựa trên các tiêu chí sau: 

• Vấn đề có hấp dẫn, thú vị không? 

• Mức độ khó của vấn đề? 

• Ý nghĩa về khoa học? 

• Ý nghĩa về thực tế?

Mỗi tiêu chí được đánh giá theo 4 mức A, B, C, D.

5. Gợi ý một số vấn đề

Vấn đề 1. Tìm đường đi ngắn nhất trên đơn đồ thị có hướng

Vấn đề 2. Kiểm tra tính liên thông của đơn đồ thị vô hướng

Vấn đề 3. Kiểm tra tính liên thông của đơn đồ thị có hướng

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 các nhóm HS đọc Vấn đề 1 SGK tr.73 và thực hiện theo hướng dẫn.

Vấn đề 1. Tìm đường đi ngắn nhất trên đơn đồ thị có hướng

Một dãy đỉnh a = , ,…,  = b (a  b) được gọi là đường đi từ đỉnh a tới đỉnh b nếu hai đỉnh liên tiếp trên đường đi có cạnh nối.

Trong cuộc sống chúng ta gặp rất nhiều bài toán liên quan đến tìm đường đi, dưới đây là một ví dụ cụ thể.

Có n sân bay được đánh số từ 0 đến 
n – 1, có m tuyến bay giữa các sân bay, tuyến thứ k sẽ bay từ sân bay sang sân bay . Em hãy tìm cách di chuyển từ sân bay a tới sân bay b với số tuyến bay là ít nhất.

Hướng dẫn: Bài toán này có thể giải quyết bằng cách duyệt đồ thị theo chiều rộng bắt đầu từ đỉnh A. Sử dụng mảng len và mảng trace trong quá trình duyệt đồ thị, trong đó len[v] là độ dài đường đi ngắn nhất từ đỉnh xuất phát đến đỉnh v và trace[v] = u cho biết để đến được đỉnh v là từ đỉnh u. Cụ thể thuật toán gồm hai bước:

Bước 1. BFS từ đỉnh xuất phát để tính được mảng len là mảng độ dài đường đi; mỗi khi tính len[v] = len[u] + 1 thì cũng ghi nhận trace [v] = u.

Bước 2. Sử dụng mảng trace để tìm đường.

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

- Các nhóm trao đổi, thảo luận, thực hiện theo hướng dẫn trong SGK để hoàn thành dự án.

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

- GV tổ chức đánh giá.

- HS báo cáo kết quả thực hiện dự án theo hướng dẫn trong SGK.

- GV kiểm tra kết quả thực hiện dự án của HS.

Bước 4: Đánh giá kết quả, thực hiện nhiệm vụ học tập

- Từ demo sản phẩm và báo cáo của các nhóm, GV nhận xét, đánh giá quá trình HS thực hiện dự án.

Vấn đề 1. Tìm đường đi ngắn nhất trên đơn đồ thị có hướng

Chương trình tìm đường đi ngắn nhất trên đơn đồ thị có hướng: