Giáo án chuyên đề Khoa học máy tính 12 kết nối Bài 13: Thực hành thiết lập đồ 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 13: Thực hành thiết lập đồ 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

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

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, phòng thực hành.

  • 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 ôn lại các kiến thức đã biết từ hai bài học trước.

b. Nội dung: GV tổ chức cho HS hoạt động nhóm và thực hiện phần Khởi động SGK tr.62. 

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

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 3 – 4 HS, yêu cầu các nhóm trao đổi, thảo luận và thực hiện hoạt động Khởi động SGK trang 62

Em hãy trao đổi, thảo luận và trả lời một số câu hỏi sau:

- Nếu đồ thị là vô hướng thì ma trận kề có đặc điểm gì?

- Phân biệt sự giống nhau và khác nhau giữa ma trận kề và danh sách kề?

- Khái niệm bậc của các đỉnh có gì khác nhau trong trường hợp đồ thị là vô hướng, có hướng?

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

- HS thảo luận 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 đại diện 3 nhóm trình bày kết quả thảo luận.

Các nhóm còn lại chú ý lắng nghe, nhận xét và bổ sung.

Gợi ý trả lời:

- Nếu đồ thị vô hướng thì ma trận kề sẽ là ma trận đối xứng, nghĩa là với mọi đỉnh i, j ta có BÀI 13: THỰC HÀNH THIẾT LẬP ĐỒ THỊ.

- Sự giống nhau và khác nhau giữa ma trận kề và danh sách kề:

+ Khác nhau:

  • Khác nhau về định nghĩa.

  • Khác nhau về khuôn dạng thể hiện.

+ Giống nhau:

  • Đều là bộ dữ liệu xác định duy nhất để biểu diễn một đồ thị.

  • Đều được biểu diễn bằng list trong Python.

- Khái niệm bậc của các đỉnh:

+ Đối với đồ thị vô hướng: Bậc của đỉnh u (deg(u)) là số lượng các đỉnh kề với u.

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

Đồ thị vô hướng

Ta có: 

  • Số cạnh của đồ thị là 6.
  • deg(0) + deg(1) + deg(2) + deg(3) + deg(4) = 2 + 2 + 4 + 2 + 2 = 12 = 6 BÀI 13: THỰC HÀNH THIẾT LẬP ĐỒ THỊ 2.

BÀI 13: THỰC HÀNH THIẾT LẬP ĐỒ THỊ Trong đồ thị vô hướng thì tổng số bậc của tất cả các đỉnh bằng hai lần số cạnh.

+ Đối với đồ thị có hướng:

  • Bậc ra của đỉnh u (deg+(u)) là số lượng các đỉnh kề với u.

  • Bậc vào của đỉnh u (deg-(u)) là số các đỉnh có cạnh nối đến u.

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

Đồ thị có hướng

Ta có:

  • deg+(0) + deg+(1) + deg+(2) + deg+(3) + deg+(4) = 1 + 3 + 1 + 2 + 0 = 7.
  • deg-(0) + deg-(1) + deg-(2) + deg-(3) + deg-(4) = 3 + 0 + 1 + 1 + 2 = 7.

BÀI 13: THỰC HÀNH THIẾT LẬP ĐỒ THỊ Trong đồ thị có hướng thì tổng số bậc ra của tất cả các đỉnh bằng tổng số bậc vào của tất cả các đỉnh.

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: Trong hai bài học trước, các em đã được làm quen với khái niệm đồ thị và các cách biểu diễn biểu diễn đồ thị. Để giúp các em ôn tập lại kiến thức và được thực hành dựa trên lí thuyết đã học, chúng ta sẽ cùng nhau đến với Bài 13: Thực hành thiết lập đồ thị.

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

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 tổ chức cho HS thực hành cá nhân, đọc yêu cầu, phân tích Nhiệm vụ 1 và viết chương trình hiển thị danh sách kề trên máy tính theo hướng dẫn.

Đơn đồ thị vô hướng G = (V,E) được cho bởi ma trận kề A. Ma trận A được cho trong tệp văn bản có dạng như hình bên.

Data.inp

4

0 1 1 0

1 0 1 1

1 1 0 1

0 1 1 0

Hình 13.1. Tệp ma trận kề

Yêu cầu xác định danh sách kề của đồ thị trên.  

Hướng dẫn:

+ Tạo tệp Data.inp, dữ liệu biểu diễn của đồ thị là ma trận kề trong tệp Data.inp

+ Trong bài trước, chúng ta đã thiết lập hàm BuildGraph(fname) lấy dữ liệu từ tệp ma trận kề và trả về cặp dữ liệu V, A là danh sách đỉnh và ma trận kề của đồ thị. 

+ Hãy viết hàm thể hiện danh sách kề trên màn hình theo đúng yêu cầu trên với tham số đầu vào là ma trận kề A.

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

- HS tiếp nhận và thực hiện theo đúng hướng dẫn để hoàn thành yêu cầu Nhiệm vụ 1.

- Trong quá trình HS thực hành, GV quan sát, hỗ trợ, giải đáp các vướng mắc của HS.

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

- HS chạy chương trình và báo cáo kết quả cho GV.

- GV quan sát bài làm của những HS đã chạy được trên máy tính.

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

- Từ kết quả thực hành của HS, GV nhận xét, đánh giá quá trình HS thực hiện nhiệm vụ.

- Nhiệm vụ 1 được gọi là hoàn thành khi HS chạy chương trình và ra được  kết quả như yêu cầu.

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

Hàm hiển thị danh sách kề:

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

* Chương trình đầy đủ:

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

Kết quả thể hiện ra màn hình:

Đỉnh kề với 0: 1 2

Đỉnh kề với 1: 0 2 3

Đỉnh kề với 2: 0 1 3

Đỉnh kề với 3: 1 2

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:
 

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 tổ chức cho HS thực hành cá nhân, đọc yêu cầu, phân tích Nhiệm vụ 2 và viết chương trình hiển thị ma trận kề, danh sách kề và bậc của đồ thị trên máy tính theo hướng dẫn.

Đơn đồ thị vô hướng G = (V,E) được cho bởi danh sách các cạnh. Danh sách các cạnh được cho trong tệp văn bản, trong đó dòng đầu tiên là số các đỉnh của đồ thị, các dòng tiếp theo mỗi dòng mô tả một cạnh của đồ thị.

Edges.inp

4

0 1 

1 3

0 2

2 3

1 2

Hình 13.2. Tệp danh sách các cạnh

Yêu cầu tính ma trận kề, danh sách kề và bậc của tất cả các đỉnh của đồ thị G.

Hướng dẫ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ị

- Hàm AdjacencyMatrix(Adj):

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

- Hàm show(A,op):

\

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

- Hàm  show_deg(Adj):

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

- Phần chương trình chính:

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

* Chương trình đầy đủ:

……………………..

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

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

Hệ thống có đầy đủ các tài liệu:

  • Giáo án word (350k)
  • Giáo án Powerpoint (400k)
  • Trắc nghiệm theo cấu trúc mới (200k)
  • Đề thi cấu trúc mới: ma trận, đáp án, thang điểm..(200k)
  • Phiếu trắc nghiệm câu trả lời ngắn (200k)
  • Trắc nghiệm đúng sai (200k)
  • Lý thuyết bài học và kiến thức trọng tâm (200k)
  • File word giải bài tập sgk (150k)
  • Phiếu bài tập để học sinh luyện kiến thức (200k)
  • .....

Nâng cấp lên VIP đê tải tất cả ở tài liệu trên

  • Phí nâng cấp VIP: 900k

=> Chỉ gửi 500k. Tải về dùng thực tế. Nếu hài lòng, 1 ngày sau mới gửi phí còn lại

Cách tải hoặc nâng cấp:

  • Bước 1: Chuyển phí vào STK: 1214136868686 - cty Fidutech - MB(QR)
  • Bước 2: Nhắn tin tới Zalo Fidutech - nhấn vào đây để thông báo và nhận tài liệu

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

ĐẦY ĐỦ GIÁO ÁN CÁC BỘ SÁCH KHÁC

GIÁO ÁN WORD LỚP 12 KẾT NỐI TRI THỨC

Giáo án toán 12 kết nối tri thức
Giáo án đại số 12 kết nối tri thức
Giáo án hình học 12 kết nối tri thức

Giáo án vật lí 12 kết nối tri thức
Giáo án hoá học 12 kết nối tri thức
Giáo án sinh học 12 kết nối tri thức

Giáo án ngữ văn 12 kết nối tri thức
Giáo án lịch sử 12 kết nối tri thức
Giáo án địa lí 12 kết nối tri thức
Giáo án kinh tế pháp luật 12 kết nối tri thức

Giáo án Công nghệ Điện - điện tử 12 kết nối tri thức
Giáo án Công nghệ 12 Lâm nghiệp - Thuỷ sản kết nối tri thức
Giáo á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 Tin học 12 - Định hướng Tin học ứng dụng kết nối tri thức

Giáo án thể dục 12 bóng rổ kết nối tri thức
Giáo án thể dục 12 cầu lông kết nối tri thức
Giáo án thể dục 12 bóng chuyền kết nối tri thức

Giáo án mĩ thuật 12 kết nối tri thức
Giáo án âm nhạc 12 kết nối tri thức
Giáo án hoạt động trải nghiệm hướng nghiệp 12 kết nối tri thức

GIÁO ÁN POWERPOINT LỚP 12 KẾT NỐI TRI THỨC

Giáo án Powerpoint Toán 12 kết nối tri thức
Giáo án Powerpoint hình học 12 kết nối tri thức
Giáo án Powerpoint đại số 12 kết nối tri thức

Giáo án powerpoint vật lí 12 kết nối tri thức
Giáo án powerpoint ngữ văn 12 kết nối tri thức
Giáo án powerpoint địa lí 12 kết nối tri thức

Giáo án powerpoint lịch sử 12 kết nối tri thức
Giáo án powerpoint địa lí 12 kết nối tri thức
Giáo án Powerpoint Kinh tế pháp luật 12 kết nối tri thức

Giáo án Powerpoint Mĩ thuật 12 kết nối tri thức
Giáo án Powerpoint Tin học 12 - Định hướng Tin học ứng dụng kết nối tri thức
Giáo án Powerpoint Tin học 12 - Định hướng Khoa học máy tính kết nối tri thức

Giáo án powerpoint Công nghệ 12 Điện - điện tử kết nối tri thức
Giáo án powerpoint Công nghệ 12 Lâm nghiệp - Thuỷ sản kết nối tri thức
Giáo án powerpoint hoạt động trải nghiệm hướng nghiệp 12 kết nối tri thức

GIÁO ÁN CHUYÊN ĐỀ LỚP 12 KẾT NỐI TRI THỨC

Giáo án chuyên đề toán 12 kết nối tri thức
Giáo án chuyên đề vật lí 12 kết nối tri thức
Giáo án chuyên đề hoá học 12 kết nối tri thức
Giáo án chuyên đề sinh học 12 kết nối tri thức

Giáo án chuyên đề ngữ văn 12 kết nối tri thức
Giáo án chuyên đề lịch sử 12 kết nối tri thức
Giáo án chuyên đề địa lí 12 kết nối tri thứ
Giáo án chuyên đề kinh tế pháp luật 12 kết nối tri thức

Giáo án chuyên đề Công nghệ 12 Công nghệ điện - điện tử kết nối tri thức
Giáo án chuyên đề Công nghệ 12 Lâm nghiệp - Thuỷ sản kết nối tri thức
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 đề Tin học 12 - Định hướng Tin học ứng dụng kết nối tri thức

GIÁO ÁN POWERPOINT CHUYÊN ĐỀ LỚP 12 KẾT NỐI TRI THỨC

 

GIÁO ÁN DẠY THÊM LỚP 12 KẾT NỐI TRI THỨC

Giáo án dạy thêm ngữ văn 12 kết nối tri thức
Giáo án powerpoint dạy thêm ngữ văn 12 kết nối tri thức
Giáo án dạy thêm toán 12 kết nối tri thức
Giáo án powerpoint dạy thêm toán 12 kết nối tri thức

Tài liệu giảng dạy

Xem thêm các bài khác

I. GIÁO ÁN WORD CHUYÊN ĐỀ TIN HỌC 12 (KHOA HỌC MÁY TÍNH) KẾT NỐI TRI THỨC

GIÁO ÁN WORD CHUYÊN ĐỀ 1. TÌM HIỂU MỘT VÀI KIỂU DỮ LIỆU TUYẾN TÍNH

Giáo án chuyên đề Khoa học máy tính 12 kết nối Bài 1: Mô hình dữ liệu ngăn xếp và hàng đợi
Giáo án chuyên đề Khoa học máy tính 12 kết nối Bài 2: Kiểu dữ liệu ngăn xếp
Giáo án chuyên đề Khoa học máy tính 12 kết nối Bài 3: Thực hành kiểu dữ liệu ngăn xếp
Giáo án chuyên đề Khoa học máy tính 12 kết nối Bài 4: Kiểu dữ liệu hàng đợi
Giáo án chuyên đề Khoa học máy tính 12 kết nối Bài 5: Thực hành kiểu dữ liệu ngăn xếp và hàng đợi

GIÁO ÁN WORD CHUYÊN ĐỀ 2. TÌM HIỂU CÂY TÌM KIẾM NHỊ PHÂN TRONG SẮP XẾP VÀ TÌM KIẾM

Giáo án chuyên đề Khoa học máy tính 12 kết nối Bài 6: Cây nhị phân
Giáo án chuyên đề Khoa học máy tính 12 kết nối Bài 7: Cây tìm kiếm nhị phân
Giáo án chuyên đề Khoa học máy tính 12 kết nối Bài 8: Thực hành cây tìm kiếm nhị phân
Giáo án chuyên đề Khoa học máy tính 12 kết nối Bài 9: Các thuật toán duyệt trên cây tìm kiếm nhị phân
Giáo án chuyên đề Khoa học máy tính 12 kết nối Bài 10: Thực hành tổng hợp với cây tìm kiếm nhị phân

GIÁO ÁN WORD CHUYÊN ĐỀ 3. TÌM HIỂU KĨ THUẬT DUYỆT ĐỒ THỊ VÀ ỨNG DỤNG

Giáo án chuyên đề Khoa học máy tính 12 kết nối Bài 11: Khái niệm đồ thị
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 chuyên đề Khoa học máy tính 12 kết nối Bài 13: Thực hành thiết lập đồ thị
Giáo án chuyên đề Khoa học máy tính 12 kết nối Bài 14: Kĩ thuật duyệt đồ thị theo chiều sâu
Giáo án chuyên đề Khoa học máy tính 12 kết nối Bài 15: Thực hành duyệt đồ thị theo chiều sâu
Giáo án chuyên đề Khoa học máy tính 12 kết nối Bài 16: Kĩ thuật duyệt đồ thị theo chiều rộng
Giáo án chuyên đề Khoa học máy tính 12 kết nối Bài 17: Thực hành duyệt đồ thị tổng hợp

II. GIÁO ÁN POWERPOINT CHUYÊN ĐỀ TIN HỌC 12 (KHOA HỌC MÁY TÍNH) KẾT NỐI TRI THỨC

GIÁO ÁN POWERPOINT CHUYÊN ĐỀ 1. TÌM HIỂU MỘT VÀI KIỂU DỮ LIỆU TUYẾN TÍNH

Giáo án điện tử chuyên đề khoa học máy tính 12 kết nối bài 1: Mô hình dữ liệu ngăn xếp và hàng đợi
Giáo án điện tử chuyên đề khoa học máy tính 12 kết nối bài 2: Kiểu dữ liệu ngăn xếp
Giáo án điện tử chuyên đề khoa học máy tính 12 kết nối bài 3: Thực hành kiểu dữ liệu ngăn xếp
Giáo án điện tử chuyên đề khoa học máy tính 12 kết nối bài 4: Kiểu dữ liệu hàng đợi
Giáo án điện tử chuyên đề khoa học máy tính 12 kết nối bài 5: Thực hành kiểu dữ liệu ngăn xếp và hàng đợi

GIÁO ÁN POWERPOINT CHUYÊN ĐỀ 2. TÌM HIỂU CÂY TÌM KIẾM NHỊ PHÂN TRONG SẮP XẾP VÀ TÌM KIẾM

Giáo án điện tử chuyên đề Khoa học máy tính 12 kết nối Bài 6: Cây nhị phân
Giáo án điện tử chuyên đề Khoa học máy tính 12 kết nối Bài 7: Cây tìm kiếm nhị phân
Giáo án điện tử chuyên đề Khoa học máy tính 12 kết nối Bài 8: Thực hành cây tìm kiếm nhị phân
Giáo án điện tử chuyên đề Khoa học máy tính 12 kết nối Bài 9: Các thuật toán duyệt trên cây tìm kiếm nhị phân
Giáo án điện tử chuyên đề Khoa học máy tính 12 kết nối Bài 10: Thực hành tổng hợp với cây tìm kiếm nhị phân

GIÁO ÁN POWERPOINT CHUYÊN ĐỀ 3. TÌM HIỂU KĨ THUẬT DUYỆT ĐỒ THỊ VÀ ỨNG DỤNG

Giáo án điện tử chuyên đề Khoa học máy tính 12 kết nối Bài 11: Khái niệm đồ thị
Giáo án điện tử 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 điện tử chuyên đề Khoa học máy tính 12 kết nối Bài 13: Thực hành thiết lập đồ thị
Giáo án điện tử chuyên đề Khoa học máy tính 12 kết nối Bài 14: Kĩ thuật duyệt đồ thị theo chiều sâu
Giáo án điện tử chuyên đề Khoa học máy tính 12 kết nối Bài 15: Thực hành duyệt đồ thị theo chiều sâu
Giáo án điện tử chuyên đề Khoa học máy tính 12 kết nối Bài 16: Kĩ thuật duyệt đồ thị theo chiều rộng
Giáo án điện tử chuyên đề Khoa học máy tính 12 kết nối Bài 17: Thực hành duyệt đồ thị tổng hợp

Chat hỗ trợ
Chat ngay