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

Ngày soạn: …/…/…

Ngày dạy: …/…/…

BÀI 12: BIỂU DIỄN ĐỒ THỊ

(2 tiết)

I. MỤC TIÊU

1. Kiến thức

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

• Thiết lập và biểu diễn được đồ thị bằng 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:

• Biểu diễn được đồ thị bằng ma trận kề và danh sách kề.
• Cài đặt được chương trình bằng ngôn ngữ Python.

Năng lực số:

• 1.2.NC1a: Đánh giá dữ liệu, thông tin và nội dung số (HS thực hiện phân tích đối chiếu kết quả biểu diễn sơ đồ đồ thị tự vẽ trên giấy với lý thuyết để đánh giá tính chuẩn xác của các mối liên kết).
• 1.3.NC1a: Quản lý dữ liệu, thông tin và nội dung số (HS thao tác xử lý đọc các tệp dữ liệu đầu vào (tệp danh sách cạnh, tệp ma trận kề, tệp danh sách kề) để bóc tách thông tin về số đỉnh (n) và lưu trữ vào cấu trúc ma trận kề (A) hoặc danh sách kề (Adj) trong bộ nhớ tạm thông qua Python).
• 1.3.NC1b: Quản lý dữ liệu, thông tin và nội dung số (HS vẽ được đồ thị dựa vào dữ liệu ma trận kề và danh sách kề).
• 2.1.NC1a: Tương tác thông qua công nghệ số (HS xem video được tạo bởi công cụ AI và trả lời câu hỏi, sử dụng máy tính cá nhân hoặc thiết bị di động có kết nối Internet để làm bài tập trắc nghiệm củng cố trên môi trường số).
• 5.3.NC1a: Sử dụng sáng tạo công nghệ số (HS sử dụng môi trường lập trình Python IDE trên máy tính để trực tiếp thiết kế, thực thi và kiểm thử tính đúng đắn của các cấu trúc ma trận kề và danh sách kề từ tệp đầu vào, từ đó đổi mới phương thức biểu diễn đồ thị thủ công).
• 3.4.NC1a: Lập trình (HS viết, đọc và điều chỉnh các hàm Python thực hiện thao tác chuyển đổi định dạng và biểu diễn dữ liệu đồ thị trên máy tính).
• 6.2.NC1a: Sử dụng trí tuệ nhân tạo (HS sử dụng công cụ AI hoặc sản phẩm số do GV cung cấp để tiếp nhận thông tin, trả lời câu hỏi đơn giản).
• 1.1.NC1a: Duyệt, tìm kiếm và lọc dữ liệu, thông tin và nội dung số (HS tiếp cận, khai thác được thông tin từ nguồn học liệu số dưới sự hướng dẫn của GV).

Năng lực AI:

• 12.A3.1: Trách nhiệm công dân trong xã hội có AI (HS thể hiện trách nhiệm học thuật số bằng việc tự lập luận logic, tự gõ code Python trước; chỉ sử dụng Chatbot AI dưới sự kiểm soát để giải thích lỗi cú pháp (debug), bắt ngoại lệ dữ liệu trống hoặc đề xuất tối ưu hóa dòng lệnh, cam kết liêm chính học thuật kỉ nguyên số).
• 12.C2.1: Các yêu cầu dành cho công cụ AI hỗ trợ các hoạt động học tập và xã hội (HS biết thiết lập prompt thích hợp nhờ Chatbot AI (như ChatGPT hoặc Gemini) so sánh sự khác biệt về dung lượng lưu trữ (không gian bộ nhớ) và tốc độ truy cập khi biểu diễn đồ thị bằng ma trận kề so với danh sách kề trong trường hợp đồ thị thưa hoặc đồ thị đầy đủ để chọn ý tưởng thiết kế hệ thống tối ưu nhất).

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

• SGK, KHBD Chuyên đề học tập Tin học 12 – Định hướng Khoa học máy tính.
• Phòng thực hành máy tính cài đặt sẵn môi trường lập trình Python (IDLE, PyCharm, VS Code,…) và có kết nối Internet, máy trình chiếu.
• Học liệu số & Công cụ AI:
• Phiếu bài tập số/bộ câu hỏi trắc nghiệm trên phần mềm Quizizz/website kenhhoctap.edu.vn.
• Video AI được tạo bằng các công cụ AI để khởi động bài học.
• Công cụ Chatbot AI (ChatGPT/Gemini).

2. Đối với học sinh

• SGK Chuyên đề học tập Tin học 12 – Định hướng Khoa học máy tính.
• Vở ghi. 

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

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

a. Mục tiêu: HS được làm quen và nhận biết khuôn dạng dữ liệu đầu vào của đồ thị dưới dạng các tệp dữ liệu.

b. Nội dung: GV cho HS quan sát hình ảnh đồ thị và các tệp dữ liệu, HS dự đoán dữ liệu nào có trong các tệp này.

c. Sản phẩm học tập: Ý nghĩa của các tệp dữ liệu ở phần Khởi động SGK tr.56.

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

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

- GV yêu cầu xem video AI được thiết kế để phục vụ bài dạy và trả lời câu hỏi xuất hiện trong video đó.

- GV yêu cầu HS quan sát Hình 12.1 và thực hiện hoạt động Khởi động SGK trang 56: 

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

- HS xem video và suy nghĩ câu trả lời.

- HS quan sát hình ảnh 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ố HS xung phong trả lời câu hỏi Khởi động tr.56 SGK.

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

Gợi ý trả lời:

+ Tệp 1: Danh sách các cạnh của đồ thị.

+ Tệp 2: Ma trận kề của đồ thị.

+ Tệp 3: Danh sách kề của đồ thị.

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

- GV nhận xét, đánh giá và kết luận.

[6.2.NC1a: HS sử dụng công cụ AI hoặc sản phẩm số do GV cung cấp để tiếp nhận thông tin, trả lời câu hỏi đơn giản.

2.1.NC1a: HS thực hiện các tương tác cơ bản với học liệu số (xem video, trả lời câu hỏi trên môi trường số).

1.1.NC1a: HS tiếp cận, khai thác được thông tin từ nguồn học liệu số dưới sự hướng dẫn của GV.]

- GV đánh giá kết quả của HS, dẫn dắt HS vào bài học mới: Có nhiều cách biểu diễn dữ liệu của một đồ thị, trong đó ba cách thường gặp là sử dụng danh sách các cạnh của đồ thị, sử dụng ma trận kề kích thước n n (n là số đỉnh) và sử dụng danh sách kề. Để tìm hiểu về ba phương pháp này, chúng ta sẽ cùng nhau đến với Bài 12: Biểu diễn đồ thị.

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

Hoạt động 1. Tìm hiểu các mô hình dữ liệu đồ thị (vô hướng hoặc có hướng)

a. Mục tiêu: HS nhận biết và nắm vững ba dạng tệp dữ liệu đầu vào thường gặp nhất của đồ thị.

b. Nội dung: GV giao nhiệm vụ; HS làm việc độc lập, tìm hiểu nội dung mục 1. Mô hình dữ liệu đồ thị và thực hiện nhiệm vụ.

c. Sản phẩm: Các mô hình dữ liệu đồ thị.

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

…………………………………………..

…………………………………………..

…………………………………………..

Hoạt động 2. Tìm hiểu cách thiết lập đồ thị từ ma trận kề và danh sách kề

a. Mục tiêu: HS biết và nắm được cách thiết lập bộ dữ liệu chính của đồ thị từ tệp dữ liệu ma trận kề và danh sách kề.

b. Nội dung: GV giao nhiệm vụ; HS tìm hiểu nội dung mục 2. Thiết lập đồ thị từ tệp ma trận kề và tệp danh sách kề và thực hiện nhiệm vụ.

c. Sản phẩm: Chương trình thiết lập đồ thị từ ma trận kề và danh sách kề.

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

Hoạt động 3. Tìm hiểu cách thiết lập dữ liệu đồ thị từ tệp dữ liệu danh sách các cạnh

a. Mục tiêu: HS biết và nắm được cách thiết lập bộ dữ liệu chính của đồ thị từ tệp dữ liệu danh sách các cạnh.

b. Nội dung: GV giao nhiệm vụ; HS tìm hiểu nội dung mục 3. Thiết lập đồ thị từ danh sách các cạnh và thực hiện nhiệm vụ.

c. Sản phẩm: Cách biểu diễn đồ thị.

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

…………………………………………..

…………………………………………..

…………………………………………..

3. HOẠT ĐỘNG LUYỆN TẬP

a. Mục tiêu: Giúp HS hệ thống lại kiến thức đã học.

b. Nội dung: GV giao nhiệm vụ cho HS, HS hoàn thành phiếu bài tập và phần Luyện tập SGK tr.61.

c. Sản phẩm học tập: Phiếu bài tập và phần Luyện tập SGK tr.61.

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

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

- GV tổng hợp các kiến thức cần ghi nhớ cho HS.

- GV tạo phiếu bài tập số bằng Google Forms/Liveworksheets/Azota hoặc tổ chức trò chơi trắc nghiệm trên Quizizz/website kenhhoctap.edu.vn để củng cố toàn bài.

- GV cung cấp mã QR hoặc đường Links cho HS chơi và làm bài tập.

- GV yêu cầu HS hoạt động cá nhân, đọc phần Luyện tập SGK tr.61 và sử dụng các kiến thức đã học để thực hiện.

Câu 1. Bổ sung thêm đoạn chương trình kiểm tra khi đọc dữ liệu danh sách các cạnh đồ thị của Hoạt động 3 như sau: Với mỗi dòng dữ liệu, nếu hai chỉ số i = j thì bỏ qua dòng này.

Câu 2. Từ ma trận kề A của đồ thị G có thể tính được số các cạnh của đồ thị không? Nếu được thì tính bằng cách nào?

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

- HS suy nghĩ, hoàn thành phiếu bài tập và phần Luyện tập SGK tr.61.

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

- HS trả lời nhanh câu hỏi trắc nghiệm.

- Mỗi câu hỏi Luyện tập GV mời 1 đến 2 HS trình bày. Các HS khác chú ý chữa bài, theo dõi nhận xét bài làm của các bạn.

Gợi ý đáp án: 

* PHIẾU BÀI TẬP

* LUYỆN TẬP

Câu 1. Chương trình nhập danh sách các cạnh và trả về V, Adj cho đồ thị có hướng có thể sửa lại như sau:

Câu 2. Tính được:

+ Nếu đồ thị là vô hướng thì số cạnh của đồ thị bằng tổng số các phần tử bằng 1 của ma trận A nằm phía trên đường chéo chính, hay bằng tổng các số 1 chia cho 2.

+ Nếu đồ thị là có hướng thì số cạnh của đồ thị bằng tổng số các phần tử bằng 1 của ma trận.

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

- 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.

- GV chạy chương trình ở Câu 1 phần Luyện tập cho cả lớp quan sát kết quả.

[2.1.NC1a: HS thực hiện tương tác số bằng cách truy cập và hoàn thành phiếu học tập trên nền tảng số.

3.4.NC1a: HS tự viết và điều chỉnh chương trình BuildGraph(fname).]

4. HOẠT ĐỘNG VẬN DỤNG

a. Mục tiêu: HS vận dụng kiến thức đã học về đồ thị viết được các hàm dựng đồ thị, biểu diễn đồ thị.

b. Nội dung: HS thực hiện hoạt động Vận dụng SGK tr.61.

c. Sản phẩm học tập: HS hoàn thành hoạt động Vận dụng SGK tr.61.

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

…………………………………………..

…………………………………………..

…………………………………………..