Giáo án điện tử 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ị

CHÀO ĐÓN CẢ LỚP

ĐẾN BUỔI HỌC MỚI!

KHỞI ĐỘNG

Hãy cho biết thứ tự duyệt các đỉnh với phương pháp duyệt đồ thị theo chiều rộng xuất phát từ đỉnh X của đồ thị sau:

KHỞI ĐỘNG

Có nhiều kết quả duyệt đồ thị theo chiều rộng xuất phát từ đỉnh X, ví dụ: X, C, D, H, B, A, F, K, E, G.

BÀI 6: DỰ ÁN HỌC TẬP:

TÌM HIỂU CÁC VẤN ĐỀ

ỨNG DỤNG ĐỒ THỊ

NỘI DUNG BÀI HỌC

Giới thiệu dự án học tập: Tìm hiểu các vấn đề ứng dụng đồ thị

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

2. Yêu cầu chung

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

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

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

Giới thiệu dự án học tập: Tìm hiểu các vấn đề

ứng dụng đồ thị

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

• Mục đích: giúp 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, HS 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.

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

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á

Tiêu chí

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

Đánh giá theo 4 mức A, B, C, D.

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

Gợi ý:

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

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

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

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.

Yêu cầu

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òn tiếp ----------------------