Giáo án chuyên đề Bài toán tìm đường đi tối ưu trong một vài trường hợp đơn giản Toán 11 Kết nối tri thức

Ngày soạn: .../.../... Ngày dạy: .../.../...
CHUYÊN ĐỀ 2: LÀM QUEN VỚI MỘT VÀI KHÁI NIỆM CỦA LÍ THUYẾT ĐỒ THỊ
BÀI 10: BÀI TOÁN TÌM ĐƯỜNG ĐI TỐI ƯU TRONG MỘT VÀI TRƯỜNG
HỢP ĐƠN GIẢN (3 tiết) I. MỤC TIÊU:
1. Kiến thức, kĩ năng: Học xong bài này, HS đạt các yêu cầu sau:
- Nhận biết được thuật toán tìm đường đi tối ưu trong những trường hợp đơn giản.
- Sử dụng kiến thức về đồ thị để giải quyết một số tình huống liên quan đến thực tiễn. 2. Năng lực
Năng lực chung:
- Năng lực tự chủ và tự học trong tìm tòi khám phá
- Năng lực giao tiếp và hợp tác trong trình bày, thảo luận và làm việc nhóm
- Năng lực giải quyết vấn đề và sáng tạo trong thực hành, vận dụng.
Năng lực riêng:
- Tư duy và lập luận toán học: So sánh, phân tích dữ liệu tìm ra mối liên hệ
giữa các đối tượng đã cho và nội dung bài học, từ đó có thể áp dụng kiến
thức đã học để giải quyết các bài toán.
- Mô hình hóa toán học, giải quyết vấn đề toán học thông qua các bài toán
thực tiễn gắn với bài toán tìm đường đi tối ưu nhất.
- Giao tiếp toán học: Trình bày, phát biểu được cách giải bài toán tìm đường
đi ngắn nhất, bài toán người đưa thư khi nhìn vào đồ thị.
- Sử dụng công cụ, phương tiện học toán: Sử dụng thước kẻ, máy tính cầm tay. 3. Phẩm chất
- Có ý thức học tập, ý thức tìm tòi, khám phá và sáng tạo, có ý thức làm việc
nhóm, tôn trọng ý kiến các thành viên khi hợp tác.
- Chăm chỉ tích cực xây dựng bài, có trách nhiệm, chủ động chiếm lĩnh kiến
thức theo sự hướng dẫn của GV.
II. THIẾT BỊ DẠY HỌC VÀ HỌC LIỆU
1. Đối với GV: SGK, Tài liệu giảng dạy, giáo án, đồ dùng dạy học.
2. Đối với HS: SGK, SBT, vở ghi, giấy nháp, đồ dùng học tập (bút, thước...), bảng
nhóm, bút viết bảng nhóm.
III. TIẾN TRÌNH DẠY HỌC
A. HOẠT ĐỘNG KHỞI ĐỘNG (MỞ ĐẦU) a) Mục tiêu:
- Tạo hứng thú, thu hút HS tìm hiểu nội dung bài học.
b) Nội dung: HS đọc tình huống mở đầu, suy nghĩ trả lời câu hỏi.
c) Sản phẩm: HS đưa ra được nhận định ban đầu về câu hỏi mở đầu.
d) Tổ chức thực hiện:
Bước 1: Chuyển giao nhiệm vụ:
- GV yêu cầu HS nhắc lại về khái niệm đường đi Euler và Chu trình Euler? Lấy Ví dụ minh họa.
Bước 2: Thực hiện nhiệm vụ: HS quan sát và chú ý lắng nghe, thảo luận nhóm đôi hoàn thành yêu cầu.
Bước 3: Báo cáo, thảo luận: GV gọi một số HS trả lời, HS khác nhận xét, bổ sung.
Bước 4: Kết luận, nhận định: GV đánh giá kết quả của HS, trên cơ sở đó dẫn dắt
HS vào bài học mới: “Trong cuộc sống hàng ngày, chúng ta thường gặp phải
những bài toán cần tìm đường đi tối ưu. Ví dụ, khi đi du lịch, chúng ta muốn tìm
đường đi ngắn nhất giữa hai điểm du lịch. Khi đi mua sắm, chúng ta muốn tìm
đường đi sao cho đi qua ít cửa hàng nhất. Khi đi làm, chúng ta muốn tìm đường đi
sao cho tiết kiệm thời gian nhất. Vậy, đường đi tối ưu là gì? Đường đi tối ưu là
đường đi có tổng chi phí thấp nhất, trong đó chi phí có thể là khoảng cách, thời
gian, tiền bạc, hoặc bất kỳ một đại lượng nào khác. Trong bài học hôm nay, chúng
ta sẽ cùng nhau tìm hiểu một số thuật toán để giải bài toán tìm đường đi tối ưu”.
Bài mới: Bài toán tìm đường đi tôi ưu trong một vài trường hợp đơn giản.
B. HÌNH THÀNH KIẾN THỨC MỚI
TIẾT 1: Bài toán tìm đường đi ngắn nhất
Hoạt động 1: Phép vị tự a) Mục tiêu:
- HS nhận biết khái niệm đồ thị có trọng số.
- HS biết được cách tìm được đường đi ngắn nhất từ một đỉnh A đến đỉnh F của
một đồ thị có trọng số.
- HS vận dụng để tìm đường đi ngắn nhất. b) Nội dung:
HS đọc SGK, nghe giảng, thực hiện các nhiệm vụ được giao, suy nghĩ trả lời câu
hỏi, thực hiện các hoạt động và Ví dụ 1.
c) Sản phẩm: HS hình thành được kiến thức bài học, câu trả lời của HS cho các
câu hỏi. HS nắm được khái niệm đồ thị có trọng số; cách tìm được đường đi ngắn
nhất từ một đỉnh A đến đỉnh F của một đồ thị có trọng số.
d) Tổ chức thực hiện: HĐ CỦA GV VÀ HS
SẢN PHẨM DỰ KIẾN
Bước 1: Chuyển giao nhiệm vụ:
1. Bài toán tìm đường ngắn nhất
- GV triền khai phần HĐ và trình HĐ.
chiếu hình 2.28 cho HS quan sát và thực hiện yêu cầu.
+ ý a) GV yêu cầu một số HS đứng tại
chỗ chỉ ra hai đường đi từ A đến F,
sau đó tính và so sánh độ dài của hai con đường đó.
+ ý b) GV giải thích cho HS hiểu a) Hai đường đi từ A đến F, chẳng hạn là
được khái niệm Nhãn vĩnh viễn của ABEF và ACEF. đỉnh V.
Sau đó HS tìm nhãn vĩnh viễn Độ dài của đường đi ABEF là:
I ( B) , I (C ).
AB+BE+EF=3+2+8=13.
Độ dài của đường đi ACEF là:
AC+CE+EF=1+5+8=14.
Do đó, đường đi ABEF có độ dài ngắn hơn đường đi ACEF.
b) I (B) và I (C) lần lượt là các khoảng cách
ngắn nhất để đi từ A đến B và C.
Ta có I (B)=AB=3, I (C)=AC=1.
- GV nhận xét câu trả lời của HS và
dẫn dắt: “Để tìm đường ngắn nhất từ
A đến F trên đồ thị có trọng số, chúng
ta cần xác định đường đi sao cho tổng
các trọng số là nhỏ nhất, hay nói cách
khác, cần xác định nhãn vĩnh viễn cho F trong đồ thị” Ghi nhớ
→ GV trình chiếu phần nội dung - Đồ thị có trọng số là một đồ thị liên thông
trong khung kiến thức trọng tâm trong và mỗi cạnh được gắn với một số không âm,
SGK cho HS quan sát và ghi bài.
gọi là trọng số của cạnh đó.
- Để tìm đường đi ngắn nhất từ đỉnh A đến
đỉnh F của một đồ thị có trọng số, ta xuất
phát từ đỉnh A và di chuyển theo các cạnh của
đồ thị. Với mỗi đỉnh V , ta gắn một số I (V ) là
khoảng cách ngắn nhất để đi từ A đến V , gọi
là nhãn vĩnh viễn của đỉnh V . Như vậy, để tìm
độ dài của đường đi ngắn nhất nối A với F , ta
cần tìm I (F).
Ví dụ 1: SGK – tr.46
- GV cho HS quan sát hình 2.29
Hướng dẫn giải: SGK – tr.46+47