Kênh giáo viên » Giáo án chuyên đề Tin học 12 - Định hướng Khoa học máy tính kết nối tri thức

Giáo án chuyên đề Khoa học máy tính 12 kết nối Bài 12: Biểu diễn đồ thị

Giáo án giảng dạy theo sách Chuyên đề học tập Tin học 12 - Định hướng Khoa học máy tính bộ sách Kết nối tri thức Bài 12: Biểu diễn đồ thị. Bộ giáo án giúp giáo viên hướng dẫn học sinh mở rộng kiến thức, phát triển năng lực, nâng cao khả năng định hướng nghề nghiệp cho các em sau này. Thao tác tải về rất đơn giản, tài liệu file word có thể chỉnh sửa dễ dàng. Mời quý thầy cô tham khảo bài soạn.

Xem: => Giáo án Tin học 12 - Định hướng Khoa học máy tính kết nối tri thức

Hướng dẫn tải giáo án

Xem toàn bộ: Giáo án chuyên đề Khoa học máy tính 12 kết nối tri thức đủ cả năm

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.

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 đượ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 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 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 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ị.

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

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 yêu cầu HS đọc 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 SGK tr.59, từ đó dẫn dắt HS tìm hiểu kiến thức.

Tìm hiểu, thảo luận cách thiết lập dữ liệu của đồ thị trong trường hợp tệp dữ liệu biểu diễn danh sách các cạnh.

……………………

3. Thiết lập đồ thị từ danh sách các cạnh

- Tệp dữ liệu danh sách các cạnh có:

+ Dòng đầu tiên là n (số đỉnh của đồ thị).

+ Các dòng tiếp theo mô tả danh sách các cạnh, mỗi dòng có hai số i, j cách nhau bởi dấu cách. Mỗi dòng ứng với một cạnh nối đỉnh i đến đỉnh j của đồ thị.

- Nếu đồ thị có hướng thì cần cập nhật một lần vào ma trận kề và danh sách kề của đồ thị.

- Nếu đồ thị vô hướng thì cần cập nhật hai lần.

……………………..

--------------------------------------

--------------------- Còn tiếp ----------------------

Trên chỉ là 1 phần của giáo án. Giáo án khi tải về có đầy đủ nội dung của bài. Đủ nội dung của học kì I + học kì II