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

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

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

BÀI 13: THỰC HÀNH THIẾT LẬP ĐỒ THỊ

(2 tiết)

I. MỤC TIÊU

1. Kiến thức

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

• Thực hành thiết lập đồ thị theo các bộ dữ liệu khác nhau.

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

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 thực hiện thao tác bóc tách dữ liệu từ các file văn bản (Data.inp, Edges.inp) chứa thông tin đồ thị và nạp vào các cấu trúc dữ liệu tương ứng (V, E, A, Adj) bằng Python nhằm phục vụ lưu trữ và truy xuất dễ dàng trên máy tính).
• 1.3.NC1b: Quản lý dữ liệu, thông tin và nội dung số (HS biểu diễn được đồ thị bằng 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 Python IDE để trực tiếp lập trình, thực thi và kiểm thử hoạt động của các cấu trúc ma trận kề, danh sách kề và bậc của đồ thị, từ đó đổi mới phương thức làm việc toán học truyền thống bằng giải pháp công nghệ hiện đại).
• 3.4.NC1a: Lập trình (HS tự viết, đọc, chỉnh sửa và gỡ lỗi cú pháp các hàm Python (In_danh_sach_dinh_ke, AdjacencyMatrix, show, show_deg, BuildGraph) thực hiện các thao tác chuyển đổi và tính toán thuộc tính trên cấu trúc đồ thị).
• 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ố: chủ động tư duy giải thuật độc lập và tự gõ mã nguồn trước; chỉ sử dụng Chatbot AI có kiểm soát như một trợ lý để gỡ lỗi (debug) cú pháp, bắt ngoại lệ dữ liệu tệp trống hoặc tối ưu hoá dòng lệnh; cam kết liêm chính kỉ nguyên số và không lạm dụng copy code của AI để đối phó).
• 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 thiết lập prompt thích hợp để nhờ Chatbot AI phân tích so sánh sự khác biệt về dung lượng lưu trữ bộ nhớ và tốc độ truy cập khi biểu diễn đồ thị vô hướng/có hướng bằng ma trận kề và danh sách kề đối với trường hợp đồ thị thưa hoặc đồ thị đầy đủ, từ đó lựa chọn ý tưởng thiết kế tối ưu hệ thống thực 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

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

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

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

2. HOẠT ĐỘNG THỰC HÀNH

Nhiệm vụ 1. Viết chương trình hiển thị danh sách kề

a. Mục tiêu: Thiết lập được chương trình hiển thị danh sách kề từ dữ liệu đầu vào là ma trận kề.

b. Nội dung: GV hướng dẫn HS thực hành trên máy tính theo hướng dẫn trong SGK để hoàn thành Nhiệm vụ 1.

c. Sản phẩm: Chương trình hiển thị danh sách kề.

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

Nhiệm vụ 2. Viết chương trình hiển thị ma trận kề, danh sách kề và bậc của đồ thị

a. Mục tiêu: Thiết lập được chương trình từ đầu vào là danh sách các cạnh, cần tính ma trận kề A, danh sách kề Adj và chi tiết bậc của các đỉnh của đồ thị.

b. Nội dung: GV hướng dẫn HS thực hành trên máy tính theo hướng dẫn trong SGK để hoàn thành Nhiệm vụ 2.

c. Sản phẩm: Chương trình hiển thị ma trận kề, danh sách kề và bậc của đồ thị.

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

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

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

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

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

a. Mục tiêu: HS thông hiểu chương trình, chỉnh sửa được chương trình thiết lập đồ thị.

b. Nội dung: GV hướng dẫn HS thực hiện hoạt động Luyện tập SGK tr.64.

c. Sản phẩm học tập: HS hoàn thành hoạt động Luyện tập SGK tr.64.

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

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

- GV tổ chức trò chơi trắc nghiệm trên website kenhhoctap.edu.vn để củng cố toàn bài.

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

Câu 1. Trong Nhiệm vụ 1, hàm In_danh_sach_dinh_ke() lấy thông tin từ ma trận kề A. Có thể sử dụng hàm này với dữ liệu là danh sách kề Adj được không? Nếu có thì viết lại hàm này với dữ liệu đầu vào là danh sách kề Adj.

Câu 2. Trong Nhiệm vụ 2, chúng ta có thể thấy các đỉnh kề không được in ra theo thứ tự tăng dần của chỉ số trong biểu diễn danh sách kề. Em hãy giải thích tại sao. Có thể chỉnh sửa chương trình để in ra các đỉnh kề theo thứ tự chỉ số tăng dần được không?

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

- HS suy nghĩ, hoàn thành hoạt động Luyện tậpSGK tr.64.

- GV quan sát, theo dõi và hỗ trợ HS khi cần thiết.

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

- Với mỗi câu hỏi, GV mời 1 đến 2 HS trình bày và thao tác Câu 1 cho cả lớp quan sát. 

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

Câu 1. Có thể sử dụng hàm In_danh_sach_dinh_ke()với dữ liệu là danh sách kề Adj:

Câu 2. Muốn in ra danh sách các đỉnh kề theo thứ tự tăng dần của số thứ tự các đỉnh của đồ thị, cần thực hiện việc sắp xếp từng phần tử của Adj ngay từ khi nhập dữ liệu gốc.

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.

[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 viết lại hàm In_danh_sach_dinh_ke() với dữ liệu đầu vào là danh sách kề.

5.3.NC1a: HS sử dụng công cụ lập trình IDE thực thi chương trình và kiểm nghiệm tính đúng đắn.]

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

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

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

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

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

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

E. THÔNG TIN BỔ SUNG

- Trên thực tế, hay trong các bài tập thực hành, một bộ dữ liệu đầy đủ các thông tin của đồ thị G = (V, E) là bộ gồm các thông tin sau:

• n – số lượng đỉnh của đồ thị.
• V – danh sách các đỉnh.
• E – danh sách các cạnh.
• A – ma trận kề.
• Adj – danh sách kề.

- Trong Python thì các dữ liệu trên thường được mô tả như sau:

• V là list các chỉ số đỉnh, đánh số từ 0 đến n – 1. Nếu các đỉnh của đồ thị có tên riêng (ví dụ a, b, c,…) thì cần thêm một mảng nữa để lưu các tên đỉnh này.
• E là list các cạnh:
• Nếu G là đồ thị vô hướng thì mỗi cạnh được biểu diễn bằng kiểu tập hợp 2 đỉnh kề của cạnh đó.

Ví dụ: e = {1,3}. 

• Nếu G là đồ thị có hướng thì mỗi cạnh được biểu diễn bằng cặp có thứ tự các đỉnh xuất phát và đỉnh kết thúc của cạnh này, ví dụ có thể dùng kiểu dữ liệu list hoặc tuple để mô tả một cạnh. 

Ví dụ: e = [1, 3] hoặc e = (1, 3).

• A được biểu diễn bằng mảng 2 chiều kích thước n n trong Python, mỗi phần tử của ma trận này là 0 hoặc 1. Nếu đồ thị G vô hướng thì A sẽ là ma trận đối xứng.
• Adj được biểu diễn bằng một list of list trong Python. Với mỗi đỉnh i, Adj[i] là danh sách các đỉnh kề của đỉnh i, như vậy Adj[i] có dạng là một list.

* HƯỚNG DẪN VỀ NHÀ

- Xem lại các nội dung thực hành ở Bài 13.

- Xem trước nội dung Bài 14: Kĩ thuật duyệt đồ thị theo chiều sâu.