Giáo án Chuyên đề Tin học 12 Kết nối tri thức Bài 11: Khái niệm đồ thị

Giáo án Chuyên đề Tin học 12 Kết nối tri thức Bài 11: Khái niệm đồ thị

Xem thử

Chỉ từ 200k mua trọn bộ Kế hoạch bài dạy (KHBD) hay Giáo án Chuyên đề Tin học 12 Kết nối tri thức chuẩn kiến thức, trình bày đẹp mắt, dễ dàng chỉnh sửa:

• B1: gửi phí vào tk: 1133836868 - CT TNHH DAU TU VA DV GD VIETJACK - Ngân hàng MB (QR)
• B2: Nhắn tin tới Zalo VietJack Official - nhấn vào đây để thông báo và nhận giáo án

I. MỤC TIÊU

1. Kiến thức

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

- Biết và trình bày được khái niệm đồ thị và các định nghĩa có liên quan.

- Mô tả được cấu trúc và ý nghĩa của ma trận kề và danh sách kề.

2. Năng lực

Năng lực chung:

- Tự chủ và tự học: Chủ động học tập, tìm hiểu nội dung bài học.

- Giải quyết vấn đề và sáng tạo: Trả lời được các câu hỏi, giải quyết được các vấn đề với sự hỗ trợ của công nghệ thông tin và truyền thông.

- Giao tiếp và hợp tác: Biết lựa chọn hình thức làm việc nhóm với quy mô phù hợp với yêu cầu và thực hiện tốt nhiệm vụ.

Năng lực Tin học:

- Trình bày được các định nghĩa và khái niệm liên quan đến đồ thị: Bậc của đỉnh đồ thị, đường đi, chu trình, tính liên thông, ma trận kề, danh sách kề.

- Mô tả được cấu trúc và ý nghĩa của ma trận kề và danh sách kề.

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.

- SGK, SGV Chuyên đề học tập Tin học 12 – Định hướng Khoa học máy tính – Kết nối tri thức.

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 – Kết nối tri thức.

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

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

a. Mục tiêu: HS làm quen với một bài toán mới, qua đó gợi tò mò muốn biết về một mô hình dữ liệu mới.

b. Nội dung: GV yêu cầu HS làm việc nhóm, quan sát Hình 11.1 và thảo luận trả lời câu hỏi ở hoạt động Khởi động SGK tr.49.

c. Sản phẩm học tập: HS hoàn thành hoạt động Khởi động SGK tr.49.

d. Tổ chức thực hiện:

Bước 1: GV chuyển giao nhiệm vụ học tập

- GV chia lớp thành các nhóm 2 – 3 HS, yêu cầu các nhóm quan sát kênh hình, đọc kênh chữ và trả lời câu hỏi Khởi động SGK trang 49:

Năm 1736, nhà bác học Euler đưa ra bài toán, được gọi là bài toán 7 cây cầu ở Königsberg. Tại thành phố cổ Königsberg của nước Phổ cũ (nay thuộc nước Nga) có dòng sông Pregel vắt ngang qua, chia thành phố thành các vùng riêng biệt. Bài toán Euler đặt ra là làm sao đi qua tất cả 7 cây cầu này, mỗi cầu chỉ được phép đi qua đúng một lần. Em hãy giải bài toán trên. Có thể dùng mô hình dữ liệu nào để mô phỏng bài toán này?

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

- HS thảo luận theo nhóm và thực hiện nhiệm vụ.

- GV hướng dẫn, hỗ trợ HS (nếu cần thiết).

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

- GV mời một số nhóm trình bày kết quả thảo luận.

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

Gợi ý trả lời:

+ Bài toán có thể được giải bằng cách sử dụng cây tìm kiếm nhị phân. Mỗi nút trong cây có thể biểu diễn một câu chuyện từ điểm xuất phát đến các cây cầu, trong đó mỗi cầu được đi qua một lần. Bằng cách này, ta có thể tìm kiếm một đường đi hợp lệ (nếu tồn tại) từ điểm xuất phát đến các cây cầu và quay lại điểm xuất phát.

+ Một cách giải khác là sử dụng đồ thị vô hướng, trong đó mỗi cầu được biểu diễn bởi một cạnh của đồ thị, và mỗi khu vực của thành phố được biểu diễn bởi một đỉnh. Bài toán trở thành việc tìm một đường đi qua tất cả các cầu (cạnh) một lần và quay lại nút xuất phát (đỉnh xuất phát).

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: Bài toán ở phần Khởi động có thể được mô phỏng bằng mô hình dữ liệu đồ thị. Vậy đồ thị là gì? Đồ thị có cấu trúc và được phân loại như thế nào? Đồ thị có những tính chất gì? Để giúp các em trả lời được những câu hỏi này, chúng ta sẽ cùng nhau đến với Bài 11: Khái niệm đồ thị.

B. HOẠT ĐỘNG HÌNH THÀNH KIẾN THỨC

Hoạt động 1. Tìm hiểu khái niệm đồ thị

a. Mục tiêu: HS biết được khái niệm đồ thị và một số định nghĩa, khái niệm trực tiếp có liên quan đến đồ thị.

b. Nội dung: GV giao nhiệm vụ; HS tìm hiểu nội dung mục 1. Khái niệm đồ thị và thảo luận nhóm thực hiện nhiệm vụ.

c. Sản phẩm: Khái niệm, các loại đồ thị.

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 tiếp tục tổ chức cho HS làm việc theo nhóm 2 – 3 HS. - GV yêu cầu các nhóm thảo luận và thực hiện Hoạt động 1 – Tìm hiểu khái niệm đồ thị SGK tr.49: 1. Trao đổi, thảo luận về mô hình đồ thị, các khái niệm cơ bản của đồ thị và trả lời câu hỏi: Bài toán trong phần khởi động có thể biểu diễn được bằng mô hình đồ thị không? 2. Em hãy tìm một số bài toán thực tế khác có thể biểu diễn được bằng đồ thị.

1. Khái niệm đồ thị a) Khái niệm đồ thị - Đồ thị G = (V, E) là tập hợp hữu hạn các đỉnh V và tập hợp các cạnh E nối các đỉnh V với nhau. - Giả sử đồ thị G = (V, E) có n đỉnh và m cạnh, ta có các kí hiệu sau: + Tập hợp các đỉnh V = {$v_1, v_2, v_3,...,v_n$}; + Tập hợp các cạnh E = {$e_1, e_2, e_3,...,e_n$}. Trong đó, các cạnh có dạng e = ($v_i, v_j$) nối hai đỉnh $v_i$ và $v_j$. Ví dụ: Một số mô hình đồ thị trong thực tế:

................................

................................

................................

Trên đây tóm tắt một số nội dung miễn phí trong bộ Kế hoạch bài dạy (KHBD) hay Giáo án Chuyên đề Tin học 12 mới nhất, để mua tài liệu đầy đủ, Thầy/Cô vui lòng xem thử:

Xem thử

Xem thêm các bài soạn Giáo án Chuyên đề Tin học lớp 12 Kết nối tri thức hay, chuẩn khác:

• Giáo án Chuyên đề Tin học 12 Bài 12: Biểu diễn đồ thị

• Giáo án Chuyên đề Tin học 12 Bài 13: Thực hành thiết lập đồ thị

• Giáo án Chuyên đề Tin học 12 Bài 14: Kĩ thuật duyệt đồ thị theo chiều sâu

• Giáo án Chuyên đề Tin học 12 Bài 15: Thực hành duyệt đồ thị theo chiều sâu

• Giáo án Chuyên đề Tin học 12 Bài 16: Kĩ thuật duyệt đồ thị theo chiều rộng

---