Tải bản chuẩn giáo án chuyên đề học tập 11 bộ sách mới cánh diều CĐ 2 Bài 2: Một vài ứng dụng của lí thuyết đồ thị (P2). giáo án soạn ch1 t1ết, hướng dẫn học sinh hoạt động để tìm tò1, khám phá ra k1ến thức mới, vận dụng chúng vào v1ệc giải quyết các vấn đề của học tập và của thực tiễn cuộc sống. Mờ1 thầy cô kéo xuống tham khảo
Rõ nét về file powerpoint trình chiếu. => Xem thêm
Hoạt động 2: Vận dụng đồ thị để giải quyết những vấn đề liên quan đến khoa học tự nhiên và công nghệ.
- HS vận dụng được các khái niệm, thuật toán, tính chất của đồ thị để giải quyết các bài toán liên quan đến khoa học tự nhiên, công nghệ,…
HOẠT ĐỘNG CỦA GV VÀ HS |
SẢN PHẨM DỰ KIẾN |
Bước 1: Chuyển giao nhiệm vụ:
Nhiệm vụ 1: Tìm hiểu liên hệ của đồ thị với khoa học tự nhiên - GV trình chiếu Hình 26 a) và b), và chỉ cho HS thấy bằng cách vận dụng đồ thị thì các vấn đề khoa học tự nhiên sẽ được giải quyết dễ dạng hơn.
- GV cho HS quan sát Ví dụ 3 và hướng dẫn HS minh họa đồ thị của Methanol và Propane như hướng dẫn của SGK. + GV đặt câu hỏi: + Đỉnh của đồ thị là nguyên tử nào? + Cạnh của đồ thị là liên kết nào? - HS thực hiện Luyện tập 3 theo nhóm đôi. + GV mời 5 HS lên bảng viết các đồng phân của . + GV đặt câu hỏi, mời 1 HS trả lời: Các nguyên tử nào là đỉnh của đồ thị ? Các liên kết nào là cạnh của đồ thị? + GV mời 5 HS khác lên biểu diễn đồ thị minh họa cho 5 đồng phân đó. + GV nhận xét và chốt đáp án.
- HS thực hiện đọc - hiểu Ví dụ 4 và trình bày lại đáp án vào vở.
- GV giới thiệu đồ thị minh họa Định luật Kirchhoff của cường độ dòng điện hướng vào và ra tại một nút ở Ví dụ 5 + GV trình bày theo hướng dẫn của SGK. Nhiệm vụ 2: Tìm hiểu liên hệ giữa đồ thị và công nghệ. - GV giới thiệu về sự liên hệ của đồ thị với công nghệ, ví dụ với một robot tự hành chúng có thể tránh được các vật cản và tìm đường đi ngắn nhất như thế nào. - GV có thể cho HS tìm hiểu thêm các Ví dụ khác thông qua các công cụ Internet. Bước 2: Thực hiện nhiệm vụ: - HS theo dõi SGK, chú ý nghe, tiếp nhận kiến thức, suy nghĩ trả lời câu hỏi, hoàn thành các yêu cầu. - GV: quan sát và trợ giúp HS. Bước 3: Báo cáo, thảo luận: - HS giơ tay phát biểu, lên bảng trình bày - Một số HS khác nhận xét, bổ sung cho bạn. Bước 4: Kết luận, nhận định: GV tổng quát lưu ý lại kiến thức trọng tâm và yêu cầu HS ghi chép đầy đủ vào vở. |
II. Vận dụng đồ thị để giải quyết những vấn đề liên quan đến khoa học tự nhiên và công nghệ. 1. Liên hệ với khoa học tự nhiên Đồ thị Hình 26b minh họa một phần của hệ thống điện ở Hình 26a. Ví dụ 3: (SGK – tr.47) Hướng dẫn giải (SGK – tr.48)
Luyện tập 3 Minh họa bằng đồ thị Ví dụ 4: (SGK – tr.48) Hướng dẫn giải (SGK – tr.48)
Ví dụ 5: (SGK – tr.48) Hướng dẫn giải (SGK – tr.48)
2. Liên hệ với công nghệ
- Bài toán tìm đường cho robot tự hành là tìm đường dẫn tốt nhất từ điểm bắt đầu đến điểm kết thúc trong môi trường có vật cản. - Các tiêu chí tối ưu thường được sử dụng là ngắn nhất về mặt khoảng cách, ngắn nhất về mặt thời gian, hoặc tiêu tốn năng lượng ít nhất.
|
Bước 1: Chuyển giao nhiệm vụ:
- GV tổ chức cho HS hoạt động thực hiện Bài 1 (SGK – tr.49).
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, hoàn thành các bài tập GV yêu cầu.
- GV quan sát và hỗ trợ.
Bước 3: Báo cáo, thảo luận:
- Mỗi bài tập GV mời HS trình bày. Các HS khác chú ý chữa bài, theo dõi nhận xét bài trên bảng.
Bước 4: Kết luận, nhận định:
- GV chữa bài, chốt đáp án, tuyên dương các hoạt động tốt, nhanh và chính xác.
Kết quả:
1.
Giả sử các điểm lần lượt biểu diễn cho các thành phố Seoul, Tokyo, Sydney, Hà Nội, Beijing, New York.
Ta có đồ thị biểu diễn mạng lưới máy chủ và tốc độ truyền dữ liệu (đơn vị: Megabit/ giây, kí hiệu là Mbps) giữa một số thành phố như sau:
- Học sinh thực hiện làm bài tập vận dụng để nắm vững kiến thức.
Bước 1: Chuyển giao nhiệm vụ
- GV yêu cầu HS hoạt động hoàn thành bài tập 2, 3, 4, 5 (SGK – tr.49).
Bước 2: Thực hiện nhiệm vụ
- HS suy nghĩ, trao đổi, thảo luận thực hiện nhiệm vụ.
- GV điều hành, quan sát, hỗ trợ.
Bước 3: Báo cáo, thảo luận
- Bài tập: đại diện HS trình bày kết quả, các HS khác theo dõi, đưa ý kiến.
Bước 4: Kết luận, nhận định
- GV nhận xét, đánh giá, đưa ra đáp án đúng, chú ý các lỗi sai của học sinh hay mắc phải.
Gợi ý đáp án:
Bài 2.
* Dễ thấy đồ thị Hình 32 có chu trình Hamilton. Sử dụng thuật toán láng riềng gần nhất đối với đỉnh xuất phát từ , ta có :
+ Từ , đến đỉnh gần nhất là .
+ Từ , đến đỉnh gần nhất là .
+ Từ , đến đỉnh gần nhất là .
+ Từ về .
=> Tổng quãng đường theo chu trình là :
* Tương tự bắt đầu với những đỉnh khác, ta có :
+ Chu trình : ; ; đều có độ dài là .
Bài 3.
* Hình 33 có chu trình Hamilton. Sử dụng thuật toán láng giềng gần nhất đối với đỉnh xuất phát từ , ta có :
+ Từ , đến đỉnh gần nhất là . (nghìn đồng)
+ Từ , đến đỉnh gần nhất là . (nghìn đồng)
+ Từ , đến đỉnh gần nhất là . (nghìn đồng)
+ Từ quay vè . (nghìn đồng)
=> Tổng chi phí di chuyển theo chu trình là : (nghìn đồng)
* Tương tự với những đỉnh khác, ta có :
+ Chu trình : có chi phí thấp nhất là (nghìn đồng).
Bài 4.
Dễ thấy đồ thị Hình 34 có chu trình Hamilton :
Ta thấy chỉ có chu trình xuất phát từ đỉnh là thỏa mãn đề bài.
Tổng quãng đường : (km)
Bài 5.
+ Từ bảo tàng, đi đến trường có thời gian ngắn nhất : 19 phút
+ Từ trường , đi đến trường có thời gian ngắn nhất : phút
+ Trừ trường , đi đến trường có thời gian ngắn nhất : phút
+ Từ trường về Bảo tàng : phút
=> Chu trình : đi hết : (phút)
* HƯỚNG DẪN VỀ NHÀ
HĐ CỦA GV VÀ HS |
SẢN PHẨM DỰ KIẾN |
||||||||||||||||||||||||
Bước 1: Chuyển giao nhiệm vụ:
Nhiệm vụ 1: Tìm hiểu đồ thị có trọng số - GV triển khai HĐ1, cho HS thực hiện nhóm đôi thực hiện yêu cầu. + GV chỉ định 1 HS nhắc lại khái niệm đồ thị đã học ở bà trước. + GV mời 2 HS lên bảng vẽ đồ thị mô tả tình huống. + HS dưới lớp nhận xét bài làm của bạn. GV dẫn dắt: Những đồ thị mà mỗi cạnh có gắn với số thực như hình 22 được gọi là đồ thị có trọng số. + GV mời 1 HS đọc phần Định nghĩa trong SGK.
- HS thực hiện đọc – hiểu Ví dụ 1 theo hướng dẫn của SGk và trình bày lại đáp án. - GV cho HS suy nghĩ thực hiện Luyện tập 1 theo từng bàn. + GV chỉ định 2 HS lên bảng thực hiện yêu cầu. + GV nhận xét và chốt đáp án cho HS.
Nhiện vụ 2: Tìm hiểu thuật toán tìm đường đi ngắn nhất trên đồ thị có trọng số. - GV triển khai HĐ2 cho HS đọc yêu cầu của HĐ và quan sát Hình 24. + GV có thể phân tích và gợi ý: • Vì mỗi đoạn nối 2 điểm trên đồ thị sẽ có một độ dài riêng nên ta có thể xét điểm xuất phát là điểm . • Từ điểm đi đến điểm nào là ngắn nhất? Cứ liên tiếp tương tự như vậy ta sẽ tìm được đường đi thỏa mãn yêu cầu đề bài. + GV chỉ định 1 HS đứng tai chỗ trình bày đáp án. HS khác nhận xét. GV chốt đáp án và trình bày ngắn gọn phần Nhận xét cho HS nắm được phương pháp giải các kiểu bài toán như HĐ2.
- GV giảng giải cho HS cách xây dựng một thuật toán láng giềng gần nhất thì trước hết cần chứng minh đồ thị có chu trình Hamilton. + GV chỉ định 2 HS nhắc lại về chu trình Hamilton và các định lí của nó.
- GV lưu ý cách tìm chu trình “tốt nhất” thông qua thuật toán láng riềng gần nhất cho HS.
- GV cho HS thực hiện Ví dụ 2 theo hướng dẫn của SGK. + Trình bày các chu trình xuất phát từ các đỉnh trong Hình 25? + Những đường đi nào là ngắn nhất? - GV triển khai Luyện tập 2 cho HS thảo luận nhóm 3 thực hiện yêu cầu. + GV mời 1 HS đứng tại chỗ chứng minh Hình 24 có chu trình Hamilton. + Các nhóm vận dụng phương pháp đã thực hiện trong Ví dụ 2 để thực hiện. + GV chỉ định 2 HS lên bảng thực hiện bài giải. + GV chữa bài chi tiết cho HS và rút ra kinh nghiệm làm vài cho HS.
Bước 2: Thực hiện nhiệm vụ: - HS theo dõi SGK, chú ý nghe, tiếp nhận kiến thức, hoàn thành các yêu cầu, thảo luận nhóm. - GV quan sát hỗ trợ. Bước 3: Báo cáo, thảo luận: - HS giơ tay phát biểu, lên bảng trình bày - Một số HS khác nhận xét, bổ sung cho bạn. Bước 4: Kết luận, nhận định: GV tổng quát lưu ý lại kiến thức trọng tâm: + Khái niệm đồ thị có trọng số. + Thuật toán tìm đường đi ngắn nhất trên đồ thị có trọng số. + Các bước chứng minh đồ thị có chu trình Hamilton. |
I. Vận dụng đồ thị để giải quyết những vấn đề về tìm đường đi ngắn nhất trong những trường hợp đơn giản
1. Đồ thị có trọng số
HĐ1 Đồ thị mô tả tình huống:
Định nghĩa Nếu mỗi cạnh của đồ thị được gắn với một số thực (có thể là độ dài của đường đi trên mỗi cạnh, hay chi phí vận chuyển trên mỗi cạnh đó,…) thì đồ thị được gọi là đồ thị có trọng số. Ví dụ 1: (SGK – tr.44) Hướng dẫn giải (SGK – tr.44)
Luyện tập 1 Có 4 trạm xe bus được nối với nhau theo những con đường với độ dài lần lượt là . Ta có đồ thị mô tả tình huống trên như sau. Mô tả: 2. Thuật toán tìm đường đi ngắn nhất trên đồ thị có trọng số HĐ2 Đường đi ngắn nhất và thỏa mãn yêu cầu đề bài: với tổng quãng đường đi là .
Nhận xét - Những bài toán như HĐ2 được gọi là bài toán về tìm đường có trọng số. - Người ta sử dụng thuật toán Láng giềng gần nhất và thuật toán các nhà tóa học Dijkstra, Whiting và Hillier. Các bước thực hiện xây dựng thuật toán + Bước 1. Chọn một đỉnh bắt đầu, ta gọi là đỉnh . + Bước 2. Xuất phát từ đỉnh hiện hành, chọn cạnh có độ dài nhỏ nhất nối đến một trong các đỉnh của đến. Đánh dầu đỉnh cuối của cạnh vừa chọn. + Bước 3. Xuất phát từ đỉnh vừa đánh dấu, nếu còn đỉnh chưa đến thì quay lại Bước 2. + Bước 4. Quay lại đỉnh . Chú ý Để tìm đường đi ngắn nhất trên đồ thị có trọng số, ta áp dụng thuật toán láng riềng gần nhất để tìm tất cả các chu trình xuất pát từ 1 đỉnh ban đầu. Sau đó so sánh độ dài của các chu trình để tìm ra chu trình “tốt nhất” thỏa mãn yêu cầu đề bài. Ví dụ 2: (SGK – tr.46) Hướng dẫn giải (SGK – tr.46+47)
Luyện tập 2 Ta thấy đồ thị hình 24 có chu trình Hamilton. Áp dụng thuật toán láng giềng gần nhất Từ đỉnh gần nhất là . Từ , đỉnh chưa đến gần nhất là Từ , đỉnh chưa đến gần nhất là ; Từ , đỉnh chưa đến gần nhất là ; Từ , đỉnh chưa đến gần nhất là ; Đến đây không còn đỉnh chưa đến, vì vậy quay về . Tổng quãng đường theo chu trình là: * Tương tự với các đỉnh khác, ta có bảng sau:
=> Vậy người giao hàng chọn 1 đường đi trong 7 đường đi trên thì quãng đường phải di chuyển là ngắn nhất.
|
Nâng cấp lên tài khoản VIP để tải tài liệu và dùng thêm được nhiều tiện ích khác
Tải bản chuẩn Tải bản chuẩn giáo án chuyên đề Toán 11 Cánh diều, Tải bản chuẩn giáo án chuyên đề học tập Toán 11 Cánh diều CĐ 2 Bài 2: Một vài ứng dụng, soạn giáo án chuyên đề Toán 11 cánh diều CĐ 2 Bài 2: Một vài ứng dụng