CHUYÊN ĐỀ 1. TÌM HIỂU MỘT VÀI KIỂU DỮ LIỆU TUYẾN TÍNH Bài 1. Mô hình dữ liệu ngăn xếp và hàng đợi A MỤC TIÊU, YÊU CẦU ĐỐI VỚI HỌC SINH 1. Kiến thức – Mô hình dữ

Phần này không yêu cầu HS trả lời chính xác. Mục đích của hoạt động khởi động là để HS làm quen và tò mò muốn biết những mô hình này có điều gì đặc biệt, giống

Hoạt động 2: Tìm hiểu mô hình dữ liệu hàng đợi Mục đích: HS biết và nắm được cơ chế hoạt động FIFO (vào trước, ra trước) của hàng đợi, các thao tác (lệnh) chính

Hoạt động luyện tập
1. Th u được dãy số sắp xếp ngược lại của dãy gốc.
2. Các số được in ra màn hình là: 1, 5.
Hoạt động vận dụng
1. GV hỗ trợ HS tìm thêm các mô hình thực tế của ngăn xếp và hàng đợi.
2. Cách thực hiện như sau:
Bước 1: Lần lượt lấy các số từ ngăn xếp S ra và đưa vào hàng đợi Q. Bước 2: Lần lượt lấy các số từ hàng đợi Q và đưa vào ngăn xếp S. Sau các bước trên ngăn xếp S sẽ chứa các phần tử theo thứ tự ngược lại so với dãy ban đầu nằm trong S.
D T HÔNG TIN BỔ SUNG
Các chú ý và kiến thức sau có tính nâng cao, GV có thể tuỳ theo tình hình học tập trên lớp để đưa thêm vào tiết học, hoặc chuyển thành phần đọc thêm, vận dụng, dành cho HS khá, giỏi.
Trong mô tả kiểu dữ liệu ngăn xếp và hàng đợi có khái niệm "dãy tuyến tính các phần
tử", khái niệm này có thể hơi khó hiểu đối với HS. GV có thể giải thích thêm từ "tuyến tính" ở đây được hiểu theo nghĩa đơn giản là "thẳng hàng", gần giống với khái niệm "dãy" hay "tuần tự". Tuy nhiên mô tả này không có ý nghĩa quyết định đến việc cài đặt dữ liệu cụ thể cho ngăn xếp và hàng đợi (sẽ học trong Bài 2, Bài 4).
2. Mô hình Undo và Redo trên thực tế được thiết lập như sau (phần kiến thức này
tương đối phức tạp nên đã không đưa vào sách chuyên đề):
Các lệnh (thao tác) trong khi soạn thảo có một số lệnh có tính chất "khả ngược", tức là có lệnh ngược, chẳng hạn lệnh gõ một kí tự, lệnh ngược là xoá kí tự đó. Th ao tác xoá một kí tự có lệnh ngược là gõ kí tự đó. Có một số thao tác không có lệnh ngược, chẳng hạn như tìm kiếm, in ấn, phóng to, thu nhỏ,...
Các lệnh Undo và Redo là hai lệnh ngược nhau, được tổ chức như sau trong phần mềm soạn thảo văn bản, mô hình một người sử dụng.
Bộ nhớ sẽ có hai ngăn xếp, tạm gọi là ngăn xếp Undo và ngăn xếp Redo. - Trong khi soạn thảo, mỗi khi chúng ta thực hiện một lệnh có lệnh ngược thì lệnh này sẽ được đưa (push) vào ngăn xếp Undo.
Khi thực hiện lệnh Undo, nếu ngăn xếp Undo không rỗng thì thực hiện lấy ra (pop) lệnh từ ngăn xếp Undo, thực hiện lệnh ngược của lệnh này và đưa (push) lệnh này vào ngăn xếp Redo.

– Khi thực hiện lệnh Redo, nếu ngăn xếp Redo không rỗng thì thực hiện lấy ra (pop) lệnh này từ ngăn xếp Redo, thực hiện lại lệnh này, sau đó đưa (push) lệnh này vào ngăn xếp Undo.
Cần chú ý về yêu cầu độ phức tạp thời gian O(1) cho tất cả các thao tác cơ bản trên ngăn xếp (Bảng 1.1 SCD) và hàng đợi (Bảng 1.2 SCD). Đây là những yêu cầu đặt ra đối với các kiểu dữ liệu này về lí thuyết. Khi tiến hành cài đặt kiểu dữ liệu ngăn xếp hay hàng đợi trên một ngôn ngữ lập trình cụ thể thì cần kiểm tra xem điều kiện về thời gian này có đạt hay không. Mỗi mô hình kiểu dữ liệu, ví dụ ngăn xếp hay hàng đợi, sẽ có nhiều cách cài đặt cụ thể, ví dụ, Python. Các yêu cầu về độ phức tạp thời gian là tương đối khó với HS, GV cần chú ý khi giảng dạy nội dung này.
Trong bài học này, HS chỉ được học và nhận biết mô hình ngăn xếp, hàng đợi ở mức mô hình và cơ chế hoạt động mà chưa có phần thực hành, cài đặt trên một ngôn ngữ lập trình cụ thể. Bài 2 và Bài 4 sẽ mô tả chi tiết quá trình cài đặt các kiểu dữ liệu này trên Python.
Bài 2. Kiểu dữ liệu ngăn xếp
A MỤC TIÊU, YÊU CẦU ĐỐI VỚI HỌC SINH
1. Kiến thức
– Cách thiết lập kiểu dữ liệu ngăn xếp bằng list trong Python.
– Các thao tác cơ bản với ngăn xếp được thực hiện trên kiểu dữ liệu list trong Python.
2. Năng lực
– Biểu diễn được ngăn xếp bằng mảng một chiều.
– Giải thích và viết được chương trình con sử dụng các hàm cơ bản của kiểu dữ liệu ngăn xếp.
3. Phẩm chất
Hình thành ý thức trách nhiệm, tính cẩn thận khi làm việc nhóm, phẩm chất làm việc chăm chỉ, chuyên cần để hoàn thành một nhiệm vụ.
B YÊU CẦU CHUẨN BỊ
Với những bài mô tả thiết kế thuật toán, GV có thể sử dụng hình ảnh, sơ đồ minh hoạ cho các bước thực hiện trên một mẫu dữ liệu đơn giản. GV có thể sử dụng các phần mềm mô phỏng thuật toán để minh hoạ thêm trong quá trình giảng dạy.

C GỢI Ý CÁC HOẠT ĐỘNG DẠY HỌC CHÍNH
Hoạ t độ ng 1, Hoạ t độ ng 2
Dùng kiểu dữ liệu mảng để biểu diễn ngăn xếp., Tìm hiểu các hàm của kiểu dữ liệu ngăn xếp.
Hoạt động khởi động
Mục đích: Gợi ý, gây tò mò cho HS về các cách khác nhau có thể biểu diễn mô hình ngăn xếp trong ngôn ngữ lập trình bậc cao cụ thể.
GV chia lớp thành ba nhóm và lần lượt, hoặc đồng thời, cho các nhóm trả lời câu hỏi: Có thể dùng kiểu dữ liệu này (ba kiểu đã mô tả trong sách) để biểu diễn mô hình dữ liệu
ngăn xếp được không? Nếu có thì các thao tác chính như pop() và push() sẽ được thiết lập như thế nào?
Lưu ý: Trong phần khởi động này không yêu cầu HS phải trả lời đúng và chính xác. Mục đích là đặt ra vấn đề để HS làm quen với bài toán chính sẽ được học trong bài.
Hoạt động 1: Dùng kiểu dữ liệu mảng để biểu diễn ngăn xếp
Mục đích: HS biết và nắm được cách sử dụng kiểu dữ liệu list trong Python để mô tả ngăn xếp thông qua sơ đồ hoặc mô tả bằng lời, chưa cần lập trình.
Tổ chức hoạt động: GV tổ chức hoạt động này theo hai bước. Bước 1: Ôn tập lại kiểu dữ liệu list của Python và một số hàm, phương thức có liên quan sẽ được sử dụng để cài đặt ngăn xếp.
Tại bước này, thông qua trao đổi nhóm hoặc dưới dạng hỏi đáp, GV hướng dẫn HS nhớ lại một số kiến thức liên quan đến kiểu dữ liệu list. Ví dụ:
List có thể hiểu là một dãy các phần tử tuyến tính, đánh chỉ số từ 0. - Có thể tạo list rỗng bằng lệnh A = [] hoặc A = list(). - List trong Python có thể có không hạn chế các phần tử. - Có thể bổ sung thêm phần tử vào cuối của danh sách bằng phương thức append(). Ví dụ A.append(x) sẽ bổ sung x vào cuối dãy A.
Phần tử cuối của list A có chỉ số len(A)-1 hoặc -1. - Phương thức (hàm) A.pop() sẽ xoá phần tử cuối của A và trả về giá trị phần tử này. Bước 2: Sử dụng list để biểu diễn ngăn xếp. Tại bước này, thông qua trao đổi nhóm hoặc dưới dạng hỏi đáp, GV hướng dẫn HS nắm được cách dùng kiểu dữ liệu danh sách (list) của Python để biểu diễn ngăn xếp. Các thao tác sau trên ngăn xếp cần được mô tả bằng lệnh tương ứng bằng các lệnh trên list của Python.

Thao tác trên ngăn xếp, Lệnh tương ứng trên list của Python Tạo ngăn xếp rỗng, Tạo list rỗng push(S, x), Bổ sung x vào list bằng lệnh append() pop(S), Phương th

Hàm top(S) 1 def top(S): 2 if isEmptyStack(S): 3 print("Ngăn xếp rỗng không thể thực hiện được lệnh này.") 4 else: 5 return S[-1] Khi sử dụng list để biểu diễn

Chương trình thiết lập kiểu dữ liệu ngăn xếp dựa trên mảng dữ liệu cho trước có độ dài cố định N có thể như sau: Stack_segment.py 1 # Thiết kế ngăn xếp sử dụng

D THÔNG TIN BỔ SUNG Với cách thiết lập ngăn xếp sử dụng list của Python như trong bài học này thì độ phức tạp thời gian của các hàm cơ bản được cho trong bảng s

C GỢI Ý CÁC HOẠT ĐỘNG DẠY HỌC CHÍNH
Hoạt động khởi động
Mục đích: GV nhắc lại các kiến thức đã học về kiểu dữ liệu ngăn xếp, lưu ý cho HS khi nào nên sử dụng kiểu dữ liệu ngăn xếp.
Hoạt động thực hành Nhiệm vụ 1: Viết chương trình mô phỏng quá trình duyệt web
Tổ chức hoạt động: - GV giao HS đọc và phân tích yêu cầu bài toán trước.
Sau khoảng 2 phút, gọi một số HS đưa ra nhận xét và GV tổng kết câu trả lời. - GV có thể chuẩn bị một số thẻ giấy ghi lại giá trị các dãy số trong dãy và yêu cầu một số HS mô phỏng lại quá trình sắp xếp dãy số bằng cách sử dụng thẻ giấy.
GV hướng dẫn HS viết chương trình và chạy chương trình mô phỏng quá trình duyệt web.
Hoạt động thực hành Nhiệm vụ 2: Viết chương trình kiểm tra các dấu ngoặc trong biểu thức
Tổ chức hoạt động: - GV giao HS đọc và phân tích yêu cầu bài toán trước. - Sau khoảng 2 phút, gọi một số HS đưa ra nhận xét và GV tổng kết câu trả lời. Có thể đưa ra thêm một số ví dụ về các biểu thức đúng, biểu thức sai, sau đó yêu cầu HS sửa các biểu thức sai thành biểu thức đúng.
GV hướng dẫn HS viết chương trình và chạy chương trình.
Hoạt động luyện tập
Mục đích: GV hướng dẫn HS thực hiện các yêu cầu trong phần luyện tập để đảm bảo HS thực sự hiểu được chương trình của Nhiệm vụ 1 và Nhiệm vụ 2 chứ không dừng lại ở mức sao chép và chạy chương trình.
Sửa lại chương trình trong Nhiệm vụ 1 để thêm chức năng đi đến trang web kế tiếp. Để làm được yêu cầu này, chúng ta cần phải sử dụng thêm 1 ngăn xếp "forward" để lưu trữ địa chỉ website trước khi thực hiện quay lại trang web cũ. Mỗi khi sử dụng chức năng "backward", chúng ta cần đưa địa chỉ trang web hiện tại vào ngăn xếp forward. Trong bài toán này, chúng ta sử dụng tuỳ chọn 1 để nhập địa chỉ mới, tuỳ chọn 2 để go backward,

tuỳ chọn 3 để go forward và tuỳ chọn 4 để dừng chương trình. Nhiệm vụ này có thể được giải quyết như sau: web.py 1 from Stack import * 2 backward = Stack() 3 fo

kiemtrabieuthuc.py 1 from Stack import * 2 def kiemtrabt(bieuthuc, tong_tron, tong_vuong): 3 hople = True 4 ngoacmo= Stack() 5 for i in range(0, len(bieuthuc)):

Bước 3: Cho phép người dùng nhập tên một quyển sách cần lấy. Lần lượt lấy các quyển sách ra khỏi ngăn xếp bằng cách sử dụng hàm pop cho đến khi lấy được quyển s

9 tmp = pop(ngoacmo) 10 if (bieuthuc[i] == ")" and tmp!="(" or (bieuthuc[i] == "]" and tmp!="[") or (bieuthuc[i] == "}" and tmp!="{"): 11 hople = False 12 break

2. Năng lực
Biểu diễn được hàng đợi bằng mảng một chiều. - Giải thích và viết được các chương trình con sử dụng các hàm cơ bản của kiểu dữ liệu hàng đợi.
3. Phẩ m chấ t
Hình thành ý thức trách nhiệm, tính cẩn thận khi làm việc nhóm, phẩm chất làm việc chăm chỉ, chuyên cần để hoàn thành một nhiệm vụ.
B YÊU CẦU CHUẨN BỊ
Với những bài mô tả thiết kế thuật toán, GV có thể sử dụng hình ảnh, sơ đồ minh hoạ cho các bước thực hiện trên một mẫu dữ liệu đơn giản. GV có thể sử dụng các phần mềm
mô phỏng thuật toán để minh hoạ thêm trong quá trình giảng dạy.
C GỢI Ý CÁC HOẠT ĐỘNG DẠY HỌC CHÍNH
Hoạ t độ ng 1, Hoạ t độ ng 2
Dùng kiểu dữ liệu mảng để biểu diễn hàng đợi., Tìm hiểu các hàm của kiểu dữ liệu hàng đợi.
Hoạt động khởi động
Mục đích: Gợi ý, gây tò mò cho HS về các cách khác nhau có thể biểu diễn mô hình hàng đợi trong ngôn ngữ lập trình bậc cao.
GV chia lớp thành các nhóm và lần lượt, hoặc đồng thời, cho các nhóm trả lời câu hỏi: Có thể dùng kiểu dữ liệu này (hai kiểu đã mô tả trong sách) để biểu diễn mô hình dữ liệu hàng đợi được không? Nếu có thì các thao tác chính như enqueue() và dequeue() sẽ được thiết lập như thế nào?
Chú ý trong phần khởi động này không yêu cầu HS phải trả lời đúng và chính xác. Mục đích là đặt ra vấn đề để HS làm quen với bài toán chính sẽ được học trong bài học.
Hoạt động 1: Dùng kiểu dữ liệu mảng để biểu diễn hàng đợi
Mục đích: HS biết và nắm được cách sử dụng kiểu dữ liệu list của Python để mô tả hàng đợi thông qua sơ đồ hoặc mô tả bằng lời, chưa cần lập trình.
Tổ chức hoạt động: GV tổ chức hoạt động này theo hai bước. Bước 1: Ôn tập lại kiểu dữ liệu list của Python và một số hàm, phương thức có liên quan sẽ được sử dụng để cài đặt hàng đợi.
Tại bước này, thông qua trao đổi nhóm hoặc dưới dạng hỏi đáp, GV hướng dẫn HS nhớ lại một số kiến thức liên quan đến kiểu dữ liệu list. Ví dụ:

List có thể hiểu là một dãy các phần tử tuyến tính, đánh chỉ số từ 0. - Có thể tạo list rỗng bằng lệnh A = [] hoặc A = list(). - List trong Python có thể có không hạn chế các phần tử. - Có thể bổ sung thêm phần tử vào cuối của danh sách bằng phương thức append(). Ví dụ A.append(x) sẽ bổ sung x vào cuối dãy A.
Phần tử cuối của list A có chỉ số len(A)-1 hoặc -1. - Phương thức (hàm) A.pop(0) sẽ xoá phần tử đầu của A và trả về giá trị phần tử này. Bước 2: Sử dụng list để biểu diễn hàng đợi. Tại bước này, thông qua trao đổi nhóm hoặc dưới dạng hỏi đáp, GV cần hướng dẫn HS nắm được cách dùng kiểu dữ liệu danh sách (list) của Python để biểu diễn hàng đợi. Các thao tác sau trên hàng đợi cần được mô tả bằng lệnh tương ứng trên list của Python.
Th ao tác trên hàng đợi, Lệnh tương ứng trên list của Python
Tạo hàng đợi rỗng, Tạo list rỗng.
enqueue(Q,x), Bổ sung x vào list bằng lệnh append().
dequeue(Q), Phương thức pop(0).
front - đầu của Q, Phần tử đầu của list.
back, rear, tail - đuôi của Q, Phần tử cuối cùng của list.
GV chốt kiến thức, khẳng định rằng có thể biểu diễn hàng đợi bằng list của Python. Lưu ý: GV nhấn mạnh rằng đây chỉ là một cách và không phải là cách duy nhất. Có rất nhiều cách biểu diễn khác nhưng trong phạm vi Bài 4 chỉ dùng cách này.
Hoạt động củng cố kiến thức
1. Số phần tử của hàng đợi Q chính là giá trị len(Q).
Sau khi thực hiện tuần tự các phép toán enqueue(Q, 2); enqueue(Q, 10); dequeue(Q);
enqueue(Q, 6); dequeue(Q); enqueue(Q, 9); enqueue(Q, 1) thì phần tử đầu của hàng đợi Q là: 6, phần tử đuôi là 1.
Hoạt động 2: Tìm hiểu các hàm của kiểu dữ liệu hàng đợi
Mục đích: HS hiểu và thực hiện được cài đặt các hàm chính của kiểu dữ liệu hàng đợi bằng list của Python.
Tổ chức hoạt động: GV chia lớp thành các nhóm, mỗi nhóm được giao nhiệm vụ viết các hàm cơ bản của hàng đợi trên giấy hoặc trực tiếp trên máy tính, sau đó GV cùng HS phân tích đúng sai và rút ra kết luận. Các hàm cần viết bao gồm:

STT, Hàm, Ý nghĩa hàm 1, Q = Queue(), Tạo hàng đợi rỗng Q. 2, enqueue(Q, x), Đưa phần tử x vào đuôi của hàng đợi Q. 3, isEmptyQueue(Q), Kiểm tra hàng đợi Q là r

3 print("Hàng đợi rỗng không thể thực hiện được lệnh này.") 4 else: 5 return Q[0] 2. Hàm length(Q) có thể viết như sau: 1 def length(Q): 2 return len(Q) Hoạt độ

25 Q[backIdx] = x 26 27 def dequeue(Q): 28 global backIdx 29 if isEmptyQueue(Q): 30 raise ValueError("Hàng đợi rỗng, không thể thực hiện được.") 31 else: 32 x =

Thực hành kiểu dữ liệu ngăn xếp và hàng đợi A MỤC TIÊU, YÊU CẦU ĐỐI VỚI HỌC SINH 1. Kiến thức Cách sử dụng cấu trúc dữ liệu ngăn xếp và hàng đợi. 2. Năng lực Có

Hoạt động luyện tập
Mục đích: GV hướng dẫn HS thực hiện các yêu cầu trong phần luyện tập để đảm bảo HS thực sự hiểu được chương trình của nhiệm vụ thực hành chứ không dừng lại ở mức sao chép và chạy chương trình.
Chúng ta có thể thấy những người phải đổi món ăn đều là những người nằm ở cuối danh sách. Điều này xuất phát từ tính chất của hàng đợi, những người ở đầu danh sách sẽ được phục vụ trước và được lấy đúng suất ăn mà mình đã chọn. Những người ở cuối danh sách là những người ở cuối hàng đợi và có thể sẽ phải đổi món ăn tuỳ theo số suất mà bếp ăn đã chuẩn bị.
Tính toán thời gian trung bình để nhận được suất ăn của mỗi người. Để làm được bài toán này, chúng ta chú ý quy luật như sau: thời gian chờ đợi trung bình của một người để nhận được suất ăn chính là thời gian trung bình một suất ăn được đưa đến tay người lao động, trong đó:
– Thời gian để suất ăn đầu tiên đến tay người lao động là 1 giây.
– Thời gian để suất ăn đầu tiên đến tay người lao động là 2 giây,...
Yêu cầu này được thực hiện như sau:
thoigian.py
from Stack import *
suatan = Stack()
file2 = open("input2.inp", encoding ="utf8")
data = file2.read()
for item in data.split(' '): # đọc thông tin suất ăn
push(suatan,item) # đưa suất ăn vào ngăn xếp
tong_thoi_gian = 0 # tổng thời gian chờ đợi của mỗi suất ăn
so_suat_an = 0
while not isEmptyStack(suatan): #lấy suất ăn ra khỏi ngăn xếp
tmp = pop(suatan)
so_suat_an = so_suat_an + 1
tong_thoi_gian = tong_thoi_gian + so_suat_an
print("Thời gian chờ đợi trung bình của mỗi người là: ",tong_thoi_gian/so_suat_an)
Hoạt động vận dụng
Ở bài toán này, chúng ta vẫn sử dụng kiểu dữ liệu hàng đợi để lưu thông tin về suất ăn mà người lao động đăng kí, sử dụng kiểu dữ liệu ngăn xếp để lưu thông tin về các suất ăn mà bếp ăn đã chuẩn bị.
Mỗi lần lấy một suất ăn ra khỏi bếp ăn, chúng ta sẽ duyệt hàng đợi để tìm người phát suất ăn đó. Chúng ta sẽ duyệt cho đến khi tìm được người đăng kí suất ăn trùng với suất ăn vừa được lấy ra khỏi ngăn xếp. Nếu duyệt đến cuối hàng đợi mà vẫn không thể tìm được người để phát suất ăn thì chương trình dừng lại. Lúc này số người không nhận được suất ăn là số người còn lại trong hàng đợi. Bài toán này có thể được thực hiện như sau:

bepan.py 1 from Queue import * 2 from Stack import * 3 def bepan(dangki, suatan): 4 while not isEmptyStack(suatan): 5 tmp1 = pop(suatan) #lấy suất ăn ra khỏi ng

Bài 6. Cây nhị phân. A MỤC TIÊU, YÊU CẦU ĐỐI VỚI HỌC SINH 1. Kiến thức Khái niệm cây và các định nghĩa có liên quan. Mô hình cây nhị phân. Phân loại cây nhị phâ

Hoạt động khởi động Mục đích: HS nhận ra được một mô hình dữ liệu mới khác với kiểu dữ liệu mảng đã học. GV chia lớp thành các nhóm và yêu cầu quan sát các sơ đ

Quan hệ anh em. - Cây con. - Mức của các nút. - Bậc của nút. - Chiều cao của cây. Cuối cùng GV chốt kiến thức. Hoạt động củng cố kiến thức 1. Một số ví dụ khác

Bước 2: Tìm hiểu cách biểu diễn cây nhị phân hoàn chỉnh bằng mảng một chiều. Tại bước này GV có thể chia lớp thành các nhóm và mỗi nhóm sẽ thực hiện việc biểu d

Hoạt động 3: Tìm hiểu một số thuật toán duyệt cây nhị phân Mục đích: HS biết và thực hiện thủ công và bằng lập trình các thuật toán duyệt trước, duyệt giữa và d

2. Chương trình như sau, chú ý các hàm Duyet_truoc(), Duyet_giua() và Duyet_sau() sẽ thực hiện các thuật toán duyệt tương ứng trên cây T. Binary_tree.py 1 def l

– Lưu trữ dữ liệu: Cây nhị phân được sử dụng để lưu trữ dữ liệu trong các cơ sở dữ liệu. Cấu trúc này cho phép truy cập dữ liệu nhanh chóng và hiệu quả thông qua việc so sánh các khoá của các nút.
– Biểu diễn cấu trúc dữ liệu: Cây nhị phân được sử dụng để biểu diễn các cấu trúc dữ liệu phức tạp khác như biểu thức toán học và đồ thị.
Ngày nay, cây nhị phân được sử dụng rộng rãi trong nhiều ứng dụng hiện đại, bao gồm:
– Hệ điều hành: Cây nhị phân được sử dụng để quản lí bộ nhớ và các tài nguyên hệ thống khác. Ví dụ, thuật toán Buddy Allocation sử dụng cây nhị phân để phân bổ hiệu quả bộ nhớ.
– Mạng máy tính: Cây nhị phân được sử dụng để định tuyến dữ liệu trong mạng. Cây định tuyến (routing tree) giúp xác định đường dẫn tối ưu để truyền dữ liệu giữa các thiết bị trong mạng.
– Trí tuệ nhân tạo: Cây nhị phân được sử dụng để biểu diễn tri thức và học máy. Ví dụ, thuật toán ID3 (Iterative Dichotomister) sử dụng cây nhị phân để xây dựng cây quyết định cho các bài toán phân loại.
– Cơ sở dữ liệu: Cây nhị phân được sử dụng để lập chỉ mục dữ liệu trong cơ sở dữ liệu. Cấu trúc B-tree là một biến thể của cây nhị phân được sử dụng phổ biến để lập chỉ mục trong các cơ sở dữ liệu lớn.
So sánh cây nhị phân với danh sách liên kết, ngăn xếp và hàng đợi:
Cấu trúc dữ liệu, Ưu điểm, Nhược điểm
Cây nhị phân, – Tìm kiếm hiệu quả: O(log n). – Sắp xếp hiệu quả: O(n log n). – Lưu trữ dữ liệu có thứ tự. – Hỗ trợ biểu diễn cấu trúc dữ liệu phức tạp., – Phức tạp hơn danh sách liên kết. – Chèn và xoá dữ liệu phức tạp hơn. – Chiếm nhiều bộ nhớ hơn danh sách liên kết.
Danh sách liên kết, – Đơn giản. – Chèn và xoá dữ liệu dễ dàng. – Tiết kiệm bộ nhớ., – Tìm kiếm chậm: O(n). – Sắp xếp chậm: O(n²). – Không lưu trữ dữ liệu có thứ tự.
Ngăn xếp, – Cơ chế LIFO. – Dễ dàng thực hiện các thao tác push và pop. – Hiệu quả cho các ứng dụng cần truy cập dữ liệu theo thứ tự ngược., – Không hỗ trợ truy cập ngẫu nhiên. – Không hiệu quả cho các ứng dụng cần truy cập dữ liệu theo thứ tự.
Hàng đợi, – Cơ chế FIFO. – Dễ dàng thực hiện các thao tác enqueue và dequeue. Hiệu quả cho các ứng dụng cần truy cập dữ liệu theo thứ tự., – Không hỗ trợ truy cập ngẫu nhiên. – Không hiệu quả cho các ứng dụng cần truy cập dữ liệu theo thứ tự ngược.

Mỗi cấu trúc dữ liệu có ưu và nhược điểm riêng. Cần lựa chọn cấu trúc dữ liệu phù hợp với yêu cầu cụ thể của từng ứng dụng. Ví dụ:
– Cây nhị phân phù hợp cho các ứng dụng cần tìm kiếm và sắp xếp dữ liệu hiệu quả, ví dụ như danh bạ điện thoại.
– Danh sách liên kết phù hợp cho các ứng dụng cần chèn và xoá dữ liệu thường xuyên, ví dụ như danh sách các bản nhạc.
– Ngăn xếp phù hợp cho các ứng dụng cần truy cập dữ liệu theo thứ tự ngược, ví dụ như undo/redo trong các chương trình soạn thảo văn bản.
– Hàng đợi phù hợp cho các ứng dụng cần truy cập dữ liệu theo thứ tự, ví dụ như hàng đợi chờ in ấn.
Bài 7. Cây tìm kiếm nhị phân
A MỤC TIÊU, YÊU CẦU ĐỐI VỚI HỌC SINH
1. Kiến thức
– Khái niệm cây tìm kiếm nhị phân.
– Các thuật toán tạo cây tìm kiếm nhị phân, chèn thêm nút vào cây tìm kiếm nhị phân.
– Thuật toán tìm kiếm khoá trên cây tìm kiếm nhị phân.
2. Năng lực
– Trình bày được khái niệm cây tìm kiếm nhị phân.
– Mô phỏng được thuật toán tạo cây tìm kiếm nhị phân từ một tập hợp các số cho trước.
– Biết và thực hiện được thuật toán tìm kiếm một giá trị của cây tìm kiếm nhị phân.
3. Phẩm chất
Hình thành ý thức trách nhiệm, tính cẩn thận khi làm việc nhóm, phẩm chất làm việc chăm chỉ, chuyên cần để hoàn thành một nhiệm vụ.
B YÊU CẦU CHUẨN BỊ
Với những bài mô tả thiết kế thuật toán, GV có thể sử dụng hình ảnh, sơ đồ minh hoạ cho các bước thực hiện trên một mẫu dữ liệu đơn giản. GV có thể sử dụng các phần mềm mô phỏng thuật toán để minh hoạ thêm trong quá trình giảng dạy.
C GỢI Ý CÁC HOẠT ĐỘNG DẠY HỌC CHÍNH
Hoạt động 1, Hoạt động 2, Hoạt động 3
Tìm hiểu cấu trúc cây tìm kiếm nhị phân., Thuật toán chèn khoá mới vào cây tìm kiếm nhị phân., Tìm hiểu thuật toán tìm kiếm trên cây tìm kiếm nhị phân.

Hoạt động khởi động
Mục đích: HS nhận biết được một dạng đặc biệt của cây nhị phân: Cây tìm kiếm nhị phân (BST - Binary Search Tree).
GV gợi ý, hướng dẫn HS quan sát và nhận ra quy luật của quan hệ giữa các khoá trong mô hình cây nhị phân trong SCĐ. Chú ý không yêu cầu HS trả lời chính xác hoàn toàn.
Hoạt động 1: Tìm hiểu cấu trúc cây tìm kiếm nhị phân
Mục đích: HS biết được định nghĩa chính xác của cây tìm kiếm nhị phân và biết được một số cách biểu diễn cây tìm kiếm nhị phân trên máy tính.
Tổ chức hoạt động: GV chia lớp thành các nhóm. Các nhóm tiến hành trao đổi, đọc, thảo luận dưới sự hướng dẫn của GV để từng bước nắm bắt kiến thức, kĩ năng chính của hoạt động này.
Hoạt động này được chia làm hai bước với các mục đích khác nhau. Bước 1: Biểu diễn của cây nhị phân tổng quát. Có hai cách biểu diễn cây nhị phân tổng quát.
Cách 1: Sử dụng cấu trúc nút liên kết. Cách biểu diễn này sẽ cần hai cấu trúc: Cấu trúc Node để thể hiện thông tin từng nút (node) của cây nhị phân. Cấu trúc Tree chỉ có thuộc tính root sẽ chỉ vào nút gốc của cây nhị phân.
a) Cấu trúc Node b) Cấu trúc Tree
Hình 7.1. Mô hình nút liên kết cây nhị phân (Hình 7.2 SCĐ) Cách 2: Sử dụng mảng một chiều. Với cách này, cây nhị phân tổng quát cần được bổ sung thêm các nút giả (có giá trị None) để tạo thành cây nhị phân hoàn chỉnh đã biến đổi, sau đó sử dụng cách biểu diễn cây hoàn chỉnh này (đã học ở Bài 6) để biểu diễn.
Cây nhị phân tổng quát
Bổ sung nút giả None để thành cây nhị
phân hoàn chỉnh
[5, 3, 7, None, None, 6]
Biểu diễn bằng mảng một chiều

Bước 2: Định nghĩa cây tìm kiếm nhị phân và biểu diễn cây tìm kiếm nhị phân. Tại bước này, GV đưa ra định nghĩa của cây tìm kiếm nhị phân. Th ời gian còn lại dà

Bước 1: Th iết lập cấu trúc nút mới với khoá 7 sẵn sàng chèn vào cây tìm kiếm nhị phân T., Bước 2: Công việc chèn bắt đầu bằng việc tìm kiếm vị trí để chèn nút

Hoạt động củng cố kiến thức Kết quả cây tìm kiếm nhị phân Hình a (Câu 1) thu được như Hình b (Câu 2). a) b) Hoạt động 3: Tìm hiểu thuật toán tìm kiếm trên cây t

Hoạt động luyện tập Có. Ví dụ: Thứ tự chèn 2, 1, 3 sẽ cho ta cây BST dạng:, Thứ tự chèn 1, 2, 3 cho ta cây BST dạng: Nếu dãy số được đưa vào cây tìm kiếm nhị ph

30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 k = right(k) else: return if k >= len(T): T.extend([Non

67 print("Không tìm thấy!") 68 if ch == 0: 69 break Hàm đệ quy insert(T, v, k) sẽ thực hiện chèn khoá v vào cây tìm kiếm nhị phân T tính từ nút có chỉ số k. Để

Điều kiện (i) ở trên chính là yêu cầu của bài vận dụng 3 tương ứng với hàm isComplete(A). Để dãy A thoả mãn điều kiện (ii) chúng ta cần kiểm tra các điều kiện s

16
17
18
19
if leftmost(A,k) >= 0:
if A[leftmost(A,k)] >= A[k]:
return False
if rightmost(A,k) >= 0:
if A[rightmost(A,k)] <= A[k]:
return False
return True
D THÔNG TIN BỔ SUNG
1. Cấu trúc cây BST sử dụng các nút liên kết đầy đủ có thể thiết lập như sau:
Cấu trúc Node mô tả các nút:
1 class Node:
2 def __init__(self,key):
3 self.key = key
4 self.left = None
5 delf.right = None
6 self.p = None
Cấu trúc cây Tree được định nghĩa như sau:
1 class Tree:
2 def __init__(self):
3 self.root = None
2. Phân tích độ phức tạp thời gian của thuật toán chèn nút mới vào cây tìm kiếm nhị
phân trong Hoạt động 2, trang 33, 34 SCĐ. Cần phân tích kĩ hơn dòng lệnh 10, 11 khi bổ sung thêm các phần tử None vào cuối dãy A. - Trong trường hợp trung bình, giả sử các nút của cây BST phân bổ đều trong vùng hình tam giác cân có đỉnh là gốc của cây. Khi đó độ dài cạnh đáy tam giác là O(n). Khi chèn thêm nút mới, số lượng các nút giả None cần chèn tỉ lệ với độ dài cạnh đáy tam giác, suy ra độ phức tạp thời gian trong trường hợp này là O(n). - Trường hợp xấu nhất, khi cây tìm kiếm nhị phân suy biến thành cây chỉ có một nhánh, khi đó n bằng chiều cao của cây. Do vậy cạnh đáy của cây sẽ là 2n - 1, nếu bổ sung thêm phần tử thì số lượng nút giả cần bổ sung sẽ xấp xỉ 2n - 1, do đó độ phức tạp thời gian của chương trình sẽ là O(2n). Chú ý rằng nếu cây BST được tổ chức theo mô hình nút liên kết thì độ phức tạp thời gian của thao tác chèn nút vào cây sẽ là O(logn) trong trường hợp trung bình và bằng O(n) trong trường hợp xấu nhất. Do vậy tổ chức dữ liệu của cây tìm kiếm nhị phân theo mảng một chiều không là tối ưu.
Mô hình BST và cách cài đặt kiểu dữ liệu BST trên các ngôn ngữ lập trình khác nhau.

Khái niệm, Định nghĩa và phân loại Định nghĩa chung BST, Tại mọi nút x của cây, tất cả các khoá của các nút thuộc cây con trái của x phải có khoá nhỏ hơn hoặc b

Mô phỏng được thuật toán tạo cây tìm kiếm nhị phân, tìm kiếm một nút trên cây theo giá trị của khoá và cập nhật các thuộc tính của nút đó.
3. Phẩ m chấ t
Hình thành ý thức trách nhiệm, tính cẩn thận khi làm việc nhóm, phẩm chất làm việc chăm chỉ, chuyên cần để hoàn thành một nhiệm vụ.
B YÊU CẦU CHUẨN BỊ
Với những bài mô tả thiết kế thuật toán, GV có thể sử dụng hình ảnh, sơ đồ minh hoạ cho các bước thực hiện trên một mẫu dữ liệu đơn giản. Hoặc có thể sử dụng các phần mềm mô phỏng thuật toán để minh hoạ thêm trong quá trình giảng dạy.
GV giới thiệu tổng quan mục đích của bài thực hành, các nhiệm vụ cần thực hiện.
Với mỗi nhiệm vụ, GV đọc đề bài, phân tích cách làm, sau đó yêu cầu HS thực hiện
dựa trên SCĐ đã có.
Trong quá trình thực hiện nếu HS gặp khó khăn, GV hướng dẫn và giải quyết các khó khăn đó.
C GỢI Ý CÁC HOẠT ĐỘNG DẠY HỌC CHÍNH
Hoạt động khởi động
Phần khởi động GV sẽ cùng HS ôn lại các kiến thức đã biết từ hai bài học trước. HS cùng trao đổi và trả lời các câu hỏi của GV đưa ra.
Ví dụ các câu trả lời có thể như sau, không yêu cầu HS trả lời chính xác:
Cây nhị phân hoàn hảo có n nút thì chiều cao của nó là bao nhiêu? Trả lời: Chiều cao của nó là log2 (n+1).
Tại sao khi sử dụng cây tìm kiếm nhị phân để tìm kiếm dữ liệu, nên cố gắng để cây trở nên cân bằng? Trả lời: Trong số các cây tìm kiếm nhị phân thì cây tìm kiếm nhị phân cân bằng có thể đảm bảo số bước tìm kiếm (thường gọi là thời gian tìm kiếm trong thuật toán) ít nhất. Cụ thể với n phần tử dữ liệu khác nhau, thời gian tìm kiếm không lớn hơn log (n).
Em hãy đề xuất thuật toán xoá một phần tử của cây tìm kiếm nhị phân được cài đặt bằng mảng. Trả lời: Để xoá một phần tử của cây tìm kiếm nhị phân, đầu tiên sử dụng thao tác tìm kiếm vị trí phần tử v (đã giới thiệu ở mục 3 Bài 7) sẽ nhận được giá trị chỉ số k trên mảng T, sau đó cập nhật phần tử đó thành None bằng lệnh T[k] = None.
Hoạt động thực hành: Viết chương trình quản lí thực đơn
Mục đích: HS được luyện tập thiết lập và sử dụng cây tìm kiếm nhị phân, áp dụng cho dữ liệu cụ thể, đặc biệt trường hợp quản lí các đối tượng có các thuộc tính khác ngoài khoá.

Tổ chức hoạt động: GV tổ chức cho các nhóm tìm hiểu nhiệm vụ, thảo luận đề xuất ý tưởng, triển khai thành mã nguồn, kiểm tra với dữ liệu sách đã cho và minh hoạ

Cơm suất 35 000 cá thu sốt Cơm sườn Cơm suất 85 000 35 000 cốt lết cá trắm Bún chả 60 000 Phở xào bò 35 000 Phở tái Cà phê đen 30 000 40 000 chín Nước ngọt 15 0

7 def right(k): 8 return 2*k+2 9 def parent(k): 10 return (k-1)//2 11 def Tree(): 12 return [] 13 14 def Tree_Insert(T, account, balance): 15 k = 0 16 while k<

Account_management.py 1 from BST_account import * #Khai báo thư viện cây tìm kiếm nhị phân 2 3 #Khởi tạo cây tìm kiếm 4 T = Tree() 5 options = ["Thoát chương tr

10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 def right(k): return 2*k+2 def parent(k): return (k-1)/

3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 Pupil_management.py from BST_pupil import * #Khai báo thư viện cây t

D THÔNG TIN BỔ SUNG Cây nhị phân (và cây tìm kiếm nhị phân) được cài đặt bằng mảng trong nhiều trường hợp xuất hiện nút giả None dẫn đến lãng phí bộ nhớ. Sau đâ

36 else: 37 y.right = z 38 def Tree_Insert_Update(T, name, price): 39 n = search(T.root, name) 40 if n is not None: 41 n.price = price 42 return 1 #Thể hiện đã

Hoạt động khởi động
Mục đích: HS nhớ lại các thuật toán duyệt cây nhị phân đã học trong Bài 6, áp dụng thử cho cây tìm kiếm nhị phân. Th ông qua trao đổi, GV đưa các câu hỏi để gợi ý HS trả lời và nhận ra được các điểm mới khi áp dụng các thuật toán duyệt đã học cho mô hình cây BST.
Không yêu cầu HS trả lời đúng và chính xác các câu hỏi.
Hoạt động 1: Tìm hiểu các thuật toán duyệt cây tìm kiếm nhị phân
Mục đích: HS biết và hiểu được cách thiết lập các thuật toán duyệt cây tìm kiếm nhị phân, biết được sự khác biệt của các thuật toán này so với các thuật toán duyệt đã biết trong Bài 6, biết được ý nghĩa thuật toán duyệt giữa và duyệt ngược trên cây tìm kiếm nhị phân.
Tổ chức hoạt động: GV chia nhóm HS. Các nhóm trao đổi, thảo luận về các thuật toán duyệt đã biết nhưng
bây giờ sẽ áp dụng cho cây tìm kiếm nhị phân.
Cần chú ý đến hai bước sau: Bước 1: Phân biệt sự khác nhau giữa các thuật toán duyệt cây nhị phân đã học trong Bài 6 và các thuật toán duyệt trong bài học này. Điểm khác biệt duy nhất như sau:
Trong Bài 6, mô hình cây được học là cây nhị phân hoàn chỉnh, còn trong bài học này thì cây tìm kiếm nhị phân đã được bổ sung thêm các phần tử giả None để trở thành cây nhị phân hoàn chỉnh, do vậy trong quá trình duyệt luôn phải kiểm tra xem nút đang duyệt có phải là nút giả None hay không.
Bước 2: Khi thực hiện các thuật toán duyệt trên cây nhị phân cần chú ý đến hai thuật toán duyệt giữa và duyệt ngược, hai thuật toán này sẽ duyệt lần lượt các phần tử của cây theo thứ tự tăng dần và giảm dần của khoá.
Cuối cùng GV chốt kiến thức.
Hoạt động củng cố kiến thức
1. Các khoá được duyệt theo thuật toán duyệt giữa là: 0, 1, 2, 5, 9.
2. Các khoá được duyệt theo thuật toán duyệt ngược là: 9, 5, 2, 1, 0.
Hoạt động 2: Tìm hiểu thuật toán sắp xếp dãy số bằng cây tìm kiếm nhị phân
Mục đích: HS hiểu được ý tưởng và cách thực hiện thuật toán sắp xếp dãy số mới dựa trên cây tìm kiếm nhị phân và so sánh với các thuật toán sắp xếp đã biết.
Tổ chức hoạt động: GV chia nhóm HS, GV cùng các nhóm trao đổi về ý tưởng thiết kế thuật toán sắp xếp dãy dựa trên thuật toán duyệt giữa của cây tìm kiếm nhị phân.
GV đưa ra hai cách cài đặt cụ thể dựa trên hai khả năng:

Cách 1: Cây tìm kiếm nhị phân với yêu cầu các khoá phải khác nhau từng đôi một. Cách 2: Cây tìm kiếm nhị phân cho phép các khoá trùng nhau. Cuối cùng GV chốt ki

Hàm minimum(T, k) sẽ tính chỉ số của phần tử minimum của cây con với gốc là nút k. 1 def minimum(T,k): 2 while left(k) < len(T) and T[left(k)] != None: 3 k = le

8 return [],[] 10 def Tree_Insert(T,C,v): 11 k = 0 12 while k < len(T) and T[k] != None: 13 if v < T[k]: 14 k = left(k) 15 elif v > T[k]: 16 k = right(k) 17 els

Khái niệm, Định nghĩa và phân loại Định nghĩa chung BST, Tại mọi nút x của cây, tất cả các khoá của các nút thuộc cây con trái của x có khoá nhỏ hơn hoặc bằng k

Thực hành tổng hợp với cây tìm kiếm nhị phân
A MỤC TIÊU, YÊU CẦU ĐỐI VỚI HỌC SINH
1. Kiến thức
Ôn luyện kiến thức tổng hợp về cây tìm kiếm nhị phân gồm các thao tác: thêm, tìm kiếm và duyệt nút gồm nhiều trường thông tin.
2. Năng lực
– Vận dụng cây tìm kiếm nhị phân vào các bài toán cụ thể.
– Sử dụng các phương thức duyệt cây tìm kiếm nhị phân để in danh sách các đối tượng theo thứ tự tăng dần hoặc giảm dần của khoá.
3. Phẩm chất
Hình thành ý thức trách nhiệm, tính cẩn thận khi làm việc nhóm, phẩm chất làm việc chăm chỉ, chuyên cần để hoàn thành một nhiệm vụ.
B YÊU CẦU CHUẨN BỊ
Với những bài mô tả thiết kế thuật toán, GV có thể sử dụng hình ảnh, sơ đồ minh hoạ cho các bước thực hiện trên một mẫu dữ liệu đơn giản hoặc có thể sử dụng các phần mềm mô phỏng thuật toán để minh hoạ thêm trong quá trình giảng dạy.
C GỢI Ý CÁC HOẠT ĐỘNG DẠY HỌC CHÍNH
Hoạt động khởi động
Phần khởi động GV sẽ cùng HS ôn lại các kiến thức đã biết từ các bài học trước. HS cùng trao đổi và trả lời các câu hỏi của GV đưa ra.
Hoạt động thực hành: Viết chương trình quản lí danh bạ điện thoại
Mục đích: HS luyện tập kiến thức tổng hợp về cây tìm kiếm nhị phân để thêm, sửa, tìm kiếm, hiển thị danh sách đối tượng theo thứ tự sắp xếp từ nhỏ đến lớn.
Tổ chức hoạt động:
GV tổ chức cho các nhóm tìm hiểu nhiệm vụ, thảo luận đề xuất ý tưởng, triển khai thành mã nguồn, kiểm tra với dữ liệu sách đã cho và minh hoạ trước lớp.
Hoạt động luyện tập
a) Để vẽ lại cây tìm kiếm nhị phân ứng với tệp contacts.inp hãy thực hiện dần các bước của thuật toán chèn cho từng liên hệ trong tệp contacts.inp. Do dữ liệu chỉ gồm 4 liên hệ trong đó 3 liên hệ đầu tiên được chèn vào lại đúng với thứ tự khoá của chúng, nút “Bố”

và "Mẹ" đều nằm ở nhánh phải của cây. Vì "ICTLab Station" < "Mẹ" nên "ICTLab Station" là nút con trái của "Mẹ". Cây tìm kiếm nhị phân thu được, không may thay,

Để in được các danh bạ ở một trang, cần phải đếm thứ tự các liên hệ khi duyệt cây. GV có thể gợi ý HS sử dụng biến toàn cục count để đếm khi duyệt bằng hàm inor

37 print("Chức năng không hợp lệ, hãy nhập số 0 đến 4") 38 continue 39 if selected == 1: #In danh bạ 40 page = int(input("In danh bạ theo thứ tự alphabet. Hãy n

7 def inorder_right2left(T,k): 8 if k < len(T) and T[k] != None: 9 inorder_right2left(T, right(k)) 10 print("Mã", T[k][0], "Họ tên:", T[k][1], "Ngày sinh:", T[k

30 day, month, year = [int(item) for item in date_components] 31 birthdate = date(year, month, day) 32 except: 33 print("Ngày tháng không hợp lệ") 34 continue 3

menu_management.py 1 from BST_menu import * #Khai báo thư viện cây tìm kiếm nhị phân 2 3 #Khởi tạo cây tìm kiếm và đọc dữ liệu từ tệp 4 T = Tree() 5 f = open("m

21 return x 22 def Tree_Insert(T,z): 23 y = None 24 x = T.root 25 while x != None: 26 y = x 27 if z.key.upper() < x.key.upper(): 28 x = x.left 29 else: 30 x = x

CHUYÊN ĐỀ 3. TÌM HIỂU KĨ THUẬT DUYỆT ĐỒ THỊ VÀ ỨNG DỤNG Bài 11. Khái niệm đồ thị. A MỤC TIÊU, YÊU CẦU ĐỐI VỚI HỌC SINH 1. Kiến thức – Khái niệm đồ thị. – Các đị

Th ông qua ví dụ này, GV hỏi HS về mô hình dữ liệu cần để mô tả bài toán. Không yêu cầu HS trả lời đúng. Hoạt động 1: Tìm hiểu khái niệm đồ thị Mục đích: HS biế

– Ma trận kề. – Danh sách kề. Hoạt động củng cố kiến thức Một đỉnh của đồ thị có bậc 0 nếu không có cạnh đi vào hoặc đi ra từ đỉnh này. a) Ma trận kề và danh sá

$Ma trận kề và danh sách kề: $$ \mathbf{A} = \begin{pmatrix} 0111 \ 1011 \ 1101 \ 1110 \end{pmatrix} \quad \text{Adj} = \begin{pmatrix} a \to b,c,d \ b \to a,c,d$

1. Mạng xã hội:
Mạng xã hội như Facebook, Twitter được biểu diễn bằng đồ thị, với các nút là người dùng và các cạnh là mối quan hệ kết bạn.
Đồ thị giúp thực hiện các chức năng như tìm kiếm bạn bè, đề xuất kết bạn, lan truyền thông tin,...
2. Bản đồ:
Bản đồ giao thông được biểu diễn bằng đồ thị, với các nút là giao lộ và các cạnh là đường.
Đồ thị giúp tìm đường đi ngắn nhất, tính toán thời gian di chuyển,...
3. Lập kế hoạch:
Lập kế hoạch dự án được biểu diễn bằng đồ thị, với các nút là các nhiệm vụ và các
cạnh là mối quan hệ phụ thuộc.
Đồ thị giúp xác định thứ tự thực hiện các nhiệm vụ, tính toán thời gian hoàn thành dự án,...
Học máy: Học máy sử dụng đồ thị để biểu diễn dữ liệu và mô hình học. Ví dụ, đồ thị
Bayes được sử dụng để phân loại dữ liệu, mạng neuron được sử dụng để học tập và dự đoán.
Khoa học máy tính: Sử dụng đồ thị để biểu diễn và giải quyết các bài toán như: Tìm
kiếm và sắp xếp; Tối ưu hoá; Xác định chu trình; Phân tích mạng; Mô hình hoá mối quan hệ giữa các bản ghi dữ liệu trong cơ sở dữ liệu quan hệ hoặc cơ sở dữ liệu đồ thị; Mô phỏng quá trình ra quyết định và giải các bài toán lôgic phức tạp trong Trí tuệ nhân tạo,...
Sinh học và chăm sóc sức khoẻ: Sử dụng đồ thị để biểu diễn cấu trúc protein, mạng
tương tác protein,... Đồ thị giúp nghiên cứu các tương tác giữa các protein và dự đoán chức năng của protein, mô hình hoá và dự đoán sự lây lan của dịch bệnh trong dân số.
7. Hoá học: Sử dụng đồ thị để biểu diễn cấu trúc phân tử và mạng phản ứng hoá học,
giúp nghiên cứu các phản ứng hoá học và thiết kế các phân tử mới.
8. Khoa học xã hội: Sử dụng để nghiên cứu mối quan hệ và tương tác giữa các cá nhân
trong một mạng xã hội, như Facebook hoặc Twitter,... Đồ thị được sử dụng để biểu diễn mối quan hệ xã hội, giúp nghiên cứu về cấu trúc xã hội và các nhóm xã hội.
Kinh tế và quản lí: Mô hình hoá và phân tích các mạng lưới kinh tế, như mạng lưới
ngân hàng hoặc thị trường tài chính. Sử dụng đồ thị để tối ưu hoá chuỗi cung ứng và quản lí dòng chảy của hàng hoá và dịch vụ.
10. Giao thông: Mô hình hoá và tối ưu hoá mạng lưới giao thông, từ mạng đường bộ
đến mạng hàng không và đường sắt.

Bài 12. Biểu diễn đồ thị A MỤC TIÊU, YÊU CẦU ĐỐI VỚI HỌC SINH 1. Kiến thức – Các dạng tệp dữ liệu đồ thị. – Biểu diễn đồ thị bằng ma trận kề. – Biểu diễn đồ thị

Tổ chức hoạt động: GV chia nhóm HS và cho các nhóm lần lượt nhận biết, sau đó mô tả chi tiết 3 dạng dữ liệu đầu vào của đồ thị. Chú ý các tệp dữ liệu này đều có thể là dữ liệu của đồ thị vô hướng và có hướng. Ba dạng tệp dữ liệu của đồ thị bao gồm:
Tệp dữ liệu danh sách các cạnh.
Tệp dữ liệu ma trận kề. - Tệp dữ liệu danh sách kề.
Hoạt động củng cố kiến thức
Đồ thị có dạng như Hình 12.1.
Có. Vì tệp dữ liệu danh sách các cạnh không quy định thứ
tự các cạnh, nên hai tệp khác nhau vẫn biểu diễn cùng một đồ thị. Hình 12.1
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ề
Mục đích: 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ề.
Tổ chức hoạt động: GV tổ chức lớp để tiếp nhận, thử nghiệm và hiểu các chương trình thiết lập dữ liệu đã có trong SCĐ. Cụ thể như sau:
a) Dữ liệu đầu vào là tệp ma trận kề. Khi đó chương trình tương ứng sẽ áp dụng chung cho cả đồ thị vô hướng và có hướng. Input: Tệp ma trận kề. Output: V, A.
b) Dữ liệu đầu vào là tệp danh sách kề. Khi đó chương trình tương ứng sẽ áp dụng chung cho cả đồ thị vô hướng và có hướng. Input: Tệp danh sách kề. Output: V, Adj.
Hoạt động củng cố kiến thức
Khẳng định đúng: Adj[i] bằng số lượng các phần tử 1 của hàng thứ i của ma trận kề A.
Ma trận kề A gồm toàn số 0 nếu đồ thị không có bất kì cạnh nào, tức là số cạnh bằng 0. 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
Mục đích: 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.
Tổ chức hoạt động: GV tổ chức lớp để tiếp nhận, thử nghiệm và hiểu các chương trình thiết lập dữ liệu đã có trong SCĐ. Cụ thể như sau:
a) Trường hợp đồ thị vô hướng. Sẽ có hai chương trình:
Input: Danh sách các cạnh. Output: V, A.

Input: Danh sách các cạnh. Output: V, Adj. b) Trường hợp đồ thị có hướng. Sẽ có hai chương trình: Input: Danh sách các cạnh. Output: V, A. Input: Danh sách các

5 for j in range(i+1,n):
6 if A[i][j] == 1:
7 E.append({i,j})
8 return E
2. Xét hai trường hợp khác nhau, đồ thị vô hướng và có hướng.
a) Đồ thị vô hướng, hàm GraphEdge(Adj) được thiết lập như sau:
1 def GraphEdge(Adj):
2 n = len(Adj)
3 E = []
4 for i in range(n):
5 for j in Adj[i]:
6 if {i,j} not in E:
7 E.append({i,j})
8 return E
b) Đồ thị có hướng, hàm GraphEdge(Adj) được thiết lập như sau:
1 def GraphEdge(Adj):
2 n = len(Adj)
3 E = []
4 for i in range(n):
5 for j in Adj[i]:
6 E.append((i,j))
7 return E
D THÔNG TIN BỔ SUNG
Để giúp HS hiểu rõ và vận dụng tốt hơn về cách biểu diễn dữ liệu của đồ thị thông qua ma trận kề, danh sách cạnh và danh sách kề, GV có thể cung cấp thêm thông tin về các ứng dụng cụ thể của mỗi cách biểu diễn. Dưới đây là một vài gợi ý:
1. Ma trận kề
Mạng lưới điện: Ma trận kề có thể được sử dụng để biểu diễn mạng lưới điện, với các đỉnh đại diện cho các trạm biến áp và các cạnh đại diện cho các đường dây điện. Ma trận kề sẽ cho biết có đường dây điện nối giữa các trạm biến áp hay không.
Ma trận liên thông: Ma trận liên thông có thể được sử dụng để biểu diễn mối quan hệ liên thông giữa các thành phố trong một quốc gia. Ma trận liên thông sẽ cho biết có đường bộ hoặc đường sắt nối giữa các thành phố hay không.
Bảng xếp hạng: Ma trận kề có thể được sử dụng để biểu diễn bảng xếp hạng trong các cuộc thi đấu. Ma trận kề sẽ cho biết hai đội đã thi đấu với nhau hay chưa.
2. Danh sách cạnh
Mạng xã hội: Danh sách bạn bè của mỗi người dùng trong mạng xã hội có thể được biểu diễn bằng danh sách cạnh. Mỗi cạnh đại diện cho mối quan hệ kết bạn giữa hai người dùng.

– Bản đồ giao thông: Danh sách các tuyến đường nối giữa các giao lộ có thể được biểu diễn bằng danh sách cạnh. Mỗi cạnh đại diện cho một tuyến đường và có thể bao gồm thông tin về chiều dài, thời gian di chuyển,...
– Lịch trình học tập: Danh sách các môn học được học trong một học kì có thể được biểu diễn bằng danh sách cạnh. Mỗi cạnh đại diện cho mối quan hệ phụ thuộc giữa hai môn học, ví dụ như môn học A phải được học trước môn học B.
Danh sách kề
– Danh sách liên lạc: Danh sách liên lạc trong điện thoại có thể được biểu diễn bằng danh sách kề. Mỗi đỉnh đại diện cho một người liên lạc và danh sách kề sẽ liệt kê tất cả các số điện thoại của người liên lạc đó.
– Cấu trúc phân tử: Cấu trúc phân tử có thể được biểu diễn bằng danh sách kề. Mỗi đỉnh đại diện cho một nguyên tử và danh sách kề sẽ liệt kê tất cả các nguyên tử liên kết với nguyên tử đó.
– Mạng máy tính: Danh sách kề có thể được sử dụng để biểu diễn mạng máy tính, với các đỉnh đại diện cho các máy tính và các cạnh đại diện cho các đường cáp nối giữa các máy tính.
Lưu ý: Một đồ thị có thể có nhiều cách biểu diễn khác nhau. Việc lựa chọn cách biểu diễn đồ thị phù hợp sẽ phụ thuộc vào nhiều yếu tố, một trong các yếu tố quan trọng nhất đó là thuật toán được sử dụng để xử lí đồ thị trong từng bài toán cụ thể.
Thực hành thiết lập đồ thị.
A MỤC TIÊU, YÊU CẦU ĐỐI VỚI HỌC SINH
1. Kiến thức
Biểu diễn đồ thị bằng ma trận kề và danh sách kề.
2. Năng lực
Thực hành thiết lập đồ thị theo các bộ dữ liệu khác nhau.
3. Phẩm chất
Hình thành ý thức trách nhiệm, tính cẩn thận khi làm việc nhóm, phẩm chất làm việc chăm chỉ, chuyên cần để hoàn thành một nhiệm vụ.
B YÊU CẦU CHUẨN BỊ
Với những bài mô tả thiết kế thuật toán, GV có thể sử dụng hình ảnh, sơ đồ minh hoạ cho các bước thực hiện trên một mẫu dữ liệu đơn giản. GV có thể sử dụng các phần mềm mô phỏng thuật toán để minh hoạ thêm trong quá trình giảng dạy.

C GỢI Ý CÁC HOẠT ĐỘNG DẠY HỌC CHÍNH
Nhiệm vụ 1, Nhiệm vụ 2
Viết chương trình hiển thị danh sách kề., Viết chương trình hiển thị ma trận kề, danh sách kề và bậc của đồ thị.
Hoạt động khởi động
Phần khởi động GV sẽ cùng HS ôn lại các kiến thức đã biết từ hai bài học trước. HS cùng trao đổi và trả lời các câu hỏi của GV đưa ra.
Ví dụ các câu trả lời có thể như sau, không yêu cầu HS trả lời chính xác:
Nếu đồ thị là vô hướng thì ma trận kề có đặc điểm gì? 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ó Aij = Aji.
Phân biệt sự giống nhau và khác nhau giữa ma trận kề và danh sách kề. Trả lời: HS có thể nêu sự khác biệt giữa ma trận kề A và danh sách kề Adj: Sự khác nhau: - Khác nhau bởi định nghĩa. - Khác nhau về khuôn dạng thể hiện của hai đối tượng này. Sự 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 có gì khác nhau trong trường hợp đồ thị là vô hướng, có hướng? Trả lời: Với đồ thị vô hướng thì bậc ra = bậc vào của các đỉnh, còn với đồ thị có hướng thì bậc vào và bậc ra có thể khác nhau.
Hoạt động thực hành: Nhiệm vụ 1: Viết chương trình hiển thị danh sách kề
Mục đích: Th iết lập được chương trình tính danh sách kề từ dữ liệu đầu vào là ma trận kề. Tổ chức hoạt động: GV tổ chức cho các nhóm trình bày yêu cầu, trình bày ý tưởng giải, thuật toán và chương trình giải chi tiết.
Hoạt động thực hành: 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ị
Mục đích: Th iế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ị.
Tổ chức hoạt động: GV tổ chức cho các nhóm trình bày yêu cầu, trình bày ý tưởng giải, thuật toán và chương trình giải chi tiết.

Hoạt động luyện tập Hàm In_danh_sach_dinh_ke() có thể viết lại với dữ liệu đầu vào Adj như sau: def In_danh_sach_dinh_ke(Adj): n = len(A) for i in range(n): pri

14 Adj[j].append(i) 15 E.append({i,j}) 16 f.close() 17 return V,E,A,Adj b) Trường hợp đồ thị có hướng 1 def BuildGraph(fname): 2 f = open(fname) 3 n = int(f.rea

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 \times 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.
Bài 14. Kĩ thuật duyệt đồ thị theo chiều sâu
A MỤC TIÊU, YÊU CẦU ĐỐI VỚI HỌC SINH
1. Kiến thức
– Bài toán duyệt đồ thị.
– Thuật toán duyệt đồ thị theo chiều sâu.
– Mô phỏng thuật toán duyệt đồ thị theo chiều sâu.
2. Năng lực
– Trình bày được ý tưởng của duyệt đồ thị theo chiều sâu.
– Mô phỏng được thuật toán duyệt theo chiều sâu.
3. Phẩm chất
Hình thành ý thức trách nhiệm, tính cẩn thận khi làm việc nhóm, phẩm chất làm việc chăm chỉ, chuyên cần để hoàn thành một nhiệm vụ.
B YÊU CẦU CHUẨN BỊ
Với những bài mô tả thiết kế thuật toán, GV có thể sử dụng hình ảnh, sơ đồ minh hoạ cho các bước thực hiện trên một mẫu dữ liệu đơn giản. GV có thể sử dụng các phần mềm mô phỏng thuật toán để minh hoạ thêm trong quá trình giảng dạy.

C GỢI Ý CÁC HOẠT ĐỘNG DẠY HỌC CHÍNH Hoạt động 1, Hoạt động 2, Hoạt động 3 Tìm hiểu ý tưởng của thuật toán duyệt đồ thị theo chiều sâu., Tìm hiểu thuật toán duyệ

Hoạt động 2: Tìm hiểu thuật toán duyệt DFS
Mục đích: HS biết và nắm được kĩ thuật cài đặt cụ thể thuật toán duyệt đồ thị theo chiều sâu DFS bằng đệ quy.
Tổ chức hoạt động: GV chia lớp thành các nhóm để đọc, trao đổi, thảo luận cách cài đặt ý tưởng thuật toán DFS trên ngôn ngữ Python.
Các bước mô tả cách cài đặt cụ thể thuật toán như sau: Bước 1: Th iết lập hàm duyệt DFS bắt đầu từ một đỉnh cụ thể, sử dụng mảng mark[] để đánh dấu, hay duyệt từng đỉnh của đồ thị, bắt đầu từ đỉnh s.
Bước 2: Th iết lập hàm hay chương trình mô tả thuật toán DFS trên toàn bộ đồ thị G. Bước 3: Phân tích độ phức tạp thời gian của thuật toán trên.
Hoạt động củng cố kiến thức
Nếu đồ thị G chỉ bao gồm các đỉnh biệt lập thì tất cả các lệnh DFS(v) sẽ chỉ đánh dấu
đúng một đỉnh v. Do vậy thuật toán duyệt theo chiều sâu DFSTraversal(G) sẽ đánh dấu từng đỉnh của G bằng lời gọi hàm DFS(v), mỗi lệnh như vậy đánh dấu đúng một đỉnh.
Nếu kiểm tra thì sẽ thấy kết quả dãy các đỉnh đã được duyệt trùng khớp với kết quả
duyệt thủ công trong Hoạt động 1.
Hoạt động 3: Tìm hiểu thuật toán duyệt không đệ quy DFS
Mục đích: HS biết và cài đặt được thuật toán duyệt theo chiều sâu không đệ quy sử dụng ngăn xếp.
Tổ chức hoạt động: GV chia nhóm HS và tổ chức cho các nhóm trao đổi, thảo luận và viết chương trình cho thuật toán DFS mới sử dụng ngăn xếp.
Th uật toán mới này chỉ khác biệt ở hàm duyệt DFS(s) bắt đầu từ đỉnh s cụ thể. Cuối cùng GV chốt kiến thức. Lưu ý: Độ phức tạp thời gian của thuật toán DFS không đệ quy giống như thuật toán DFS đệ quy.
Hoạt động củng cố kiến thức
Th ứ tự các đỉnh được duyệt theo thuật toán DFS đệ quy là: 0 5 1 6 7 2 3 4, còn nếu
thực hiện theo DFS không đệ quy thì thứ tự duyệt là: 0 5 7 2 3 6 1 4.
8 8
0 5 0 0 0 0 0 1 0 0
1 0 0 0 0 0 0 0 0
2 3 0 0 0 1 0 0 0 0
3 6 0 0 0 0 0 0 1 0
4 3 5 0 0 0 1 0 1 0 0
5 1 6 7 0 1 0 0 0 0 1 1
6 1 7 0 0 0 0 0 0 0 1
7 2 0 0 1 0 0 0 0 0
Danh sách kề Ma trận kề

Thứ tự các đỉnh được duyệt theo thuật toán DFS đệ quy là: 0 1 2 4 5 3 6 7 8, còn nếu thực hiện theo DFS không đệ quy thì thứ tự duyệt là: 0 3 8 7 6 2 5 4 1. 9 0

27 print(v,end = " ") 28 for u in Adj[v]: 29 push(S,u) 30 else: 31 print("not found",end = "") 32 print() 33 34 # Chương trình chính 35 V,Adj = BuildGraph(fname

a) Chương trình chính trong trường hợp này cần viết lại như sau: 1 V,Adj = BuildGraph(fname) 2 n = len(V) 3 mark = [False]*n 4 for s in V: 5 DFS(s) b) Thứ tự cá

4 for v in Adj[s]: 5 if not mark[v]: 6 DFS(v) – Hàm chính của thuật toán duyệt DFS() không đệ quy như sau, có in ra các đỉnh đã duyệt: 1 def DFS(s): # DFS không

7 mark[v] = True
8 for j in range(len(A)):
9 if A[v][j] == 1:
10 if not mark[j]
11 push(S, j)
Mệnh đề: “Thuật toán DFS(s) sẽ duyệt qua đỉnh t khi và chỉ khi tồn tại đường đi từ s đến t” có thể chứng minh bằng quy nạp theo số các cạnh của đường đi từ s đến t.
– Nếu số cạnh = 0, tức là t = s thì hiển nhiên DFS(s) sẽ đánh dấu s đầu tiên, tức là đánh dấu t.
– Giả sử mệnh đề đã được chứng minh cho tất cả các đỉnh có đường đi độ dài nhỏ hơn k tính từ s. Xét đỉnh t với điều kiện có đường đi độ dài k tính từ s. Giả sử p là một đường đi như vậy.
$$p = v_0 = s, v_1, v_2,..., v_{k-1}, v_k = t.$$
Đặt $u = v_{k-1}$. Theo giả thiết quy nạp thì hàm DFS(s) sẽ đánh dấu u tại một thời điểm nào đó. Theo cách thiết lập DFS() thì sau khi đánh dấu u, DFS sẽ gọi đến tất cả các đỉnh nằm trong Adj(u), nhưng theo giả thiết thì t là đỉnh kề với u, do vậy t nằm trong Adj[u], do đó DFS(s) sẽ đánh dấu đỉnh t, đó là điều phải chứng minh.
D THÔNG TIN BỔ SUNG
Toàn bộ phần mô tả thuật toán duyệt đồ thị theo chiều sâu trong SCD là mô tả theo bộ dữ liệu V, Adj. Hoàn toàn tương tự, có thể mô tả thuật toán này nếu đồ thị được biểu diễn bằng ma trận kề A. Bài tập vận dụng 2 đã mô tả cách cài đặt DFS theo ma trận kề A. Chú ý hai cách mô tả này hoàn toàn tương tự nhau nhưng độ phức tạp thời gian thực hiện có sự khác biệt và được mô tả trong bảng sau:
Thuật toán, Đồ thị vô hướng, Đồ thị có hướng
DFS sử dụng danh sách kề Adj, O(V + 2E), O(V + E)
DFS sử dụng ma trận kề A, O($V^2$), O($V^2$)
Thuật toán duyệt đồ thị theo chiều sâu DFS trên đồ thị, phương án đệ quy, chính là kĩ thuật duyệt quay lui mà HS đã được học trong sách Chuyên đề học tập Tin học 11 – Định hướng Khoa học máy tính. Khi dạy đến phần này, GV có thể gợi ý và nhắc lại thuật toán duyệt vét cạn quay lui đã học để HS có thể so sánh và tìm ra được sự tương tự giữa hai thuật toán này.

Thực hành duyệt đồ thị theo chiều sâu A MỤC TIÊU, YÊU CẦU ĐỐI VỚI HỌC SINH 1. Kiến thức – Khái niệm chu trình. – Kiểm tra đồ thị cho trước có tồn tại chu trình

Hoạt động luyện tập 1. Không đúng. Hàm kiểm tra trên chỉ áp dụng cho đồ thị có hướng. Với đồ thị vô hướng cần chỉnh sửa để có thể áp dụng. Hàm DFS_acyclic(Adj,s

11 return False 12 status[s] = 2 # Đã duyệt xong 13 return True Bổ sung hàm in dãy các chuyên đề có mâu thuẫn, nếu có: 1 def printpath(t): 2 s = t 3 q = [] 4 q.

8 for line in f: 9 edge = [int(ch) for ch in line.split()] 10 i,j = edge[0],edge[1] 11 Adj[i].append(j) 12 f.close() 13 return V,Adj 14 15 def DFS_cycle(s): 16

48 49 # Chương trình chính 50 fi = "graph-1.inp" 51 V,Adj = BuildGraph(fi) 52 n = len(V) 53 status = [0]*n 54 prev = [None]*n 55 S = Stack() 56 if isCyclic(): 5

2. Năng lực
Trình bày được ý tưởng của duyệt đồ thị theo chiều rộng. - Mô phỏng được thuật toán duyệt theo chiều rộng.
3. Phẩ m chấ t
Hình thành ý thức trách nhiệm, tính cẩn thận khi làm việc nhóm, phẩm chất làm việc chăm chỉ, chuyên cần để hoàn thành một nhiệm vụ.
B YÊU CẦU CHUẨN BỊ
Với những bài mô tả thiết kế thuật toán, GV có thể sử dụng hình ảnh, sơ đồ minh hoạ cho các bước thực hiện trên một mẫu dữ liệu đơn giản. GV có thể sử dụng các phần mềm mô phỏng thuật toán để minh hoạ thêm trong quá trình giảng dạy.
C GỢI Ý CÁC HOẠT ĐỘNG DẠY HỌC CHÍNH
Hoạ t độ ng 1, Hoạ t độ ng 2
Làm quen ý tưởng của thuật toán duyệt đồ thị theo chiều rộng., Tìm hiểu thuật toán duyệt đồ thị theo chiều rộng.
Hoạt động khởi động
Mục đích: HS làm quen với ý tưởng của thuật toán duyệt theo chiều rộng và dự đoán cách thực hiện của thuật toán duyệt đồ thị này.
GV trình bày ý tưởng ban đầu của thuật toán duyệt đồ thị theo chiều sâu và cho các nhóm trao đổi, phát biểu và thử tìm lời giải trên đồ thị của Hình 16.1 SCĐ.
Hoạt động 1: Làm quen ý tưởng của thuật toán duyệt đồ thị theo chiều rộng
Mục đích: HS biết và nắm được ý tưởng của cách duyệt đồ thị theo chiều rộng và thực hiện được việc duyệt đồ thị thủ công.
Tổ chức hoạt động: GV chia lớp thành các nhóm, tìm thêm một số ví dụ đồ thị và biểu diễn các đồ thị này bằng hình ảnh. GV trình bày nhanh ý tưởng của duyệt theo chiều rộng, sau đó cho các nhóm thực hiện duyệt thủ công và so sánh kết quả.
GV đánh giá từng nhóm đúng hay sai. Cuối cùng GV chốt kiến thức.
Hoạt động củng cố kiến thức
Mệnh đề này đúng. Cách chứng minh hoàn toàn tương tự Vận dụng 3 của Bài 14.
a) Các đỉnh kề với đỉnh a là b, c.

b) Khoảng cách từ a đến e là 3 (đi qua các đỉnh c, h, e). c) Th ứ tự duyệt các đỉnh từ a sẽ là: a, b, c, d, f, h, e, g. Hoạt động 2: Tìm hiểu thuật toán duyệt đ

26 def BFS(s): 27 stt = 0 28 Q = Queue() 29 enqueue(Q,s) 30 while not isEmptyQueue(Q): 31 stt = stt + 1 32 print(stt,":"," "(3-len(str(stt))),sep = "",end = "")

7: [7, 8, 0, 3, 0, 4, 0], 7, 7 8: [8, 0, 3, 0, 4, 0, 1], 8, 8 9: [0, 3, 0, 4, 0, 1, 1], 0, -- 10: [3, 0, 4, 0, 1, 1], 3, 3 11: [0, 4, 0, 1, 1, 2, 4], 0, -- 12:

Ý tưởng của thuật toán phát hiện chu trình như sau: Giả s sử chúng ta chạy thuật toán BFS(s), bắt đầu từ s. Trong quá trình duyệt, các đỉnh được duyệt sẽ được đ

4 n = len(V) 5 mark = [False]*n 6 prev = [None]*n 7 if isCycle(): 8 print("Đồ thị có chu trình") 9 else: 10 print("Đồ thị không có chu trình") 2. Giả sử, không

26 enqueue(Q,u) 27 28 def printpath(s,t): 29 print(prev) 30 if prev[t] == None: 31 print("Không tồn tại đường đi từ đỉnh",s,"đến đỉnh",t) 32 else: 33 q = [] 34

Xác định cấu trúc của đồ thị – Kiểm tra tính liên thông của đồ thị. – Tìm số lượng thành phần liên thông trong đồ thị. So với duyệt đồ thị theo chiều sâu, duyệt

Hoạt động khởi động Mục đích: HS được gợi ý tìm hiểu các ứng dụng của thuật toán duyệt đồ thị theo chiều rộng. GV cùng ôn tập, trao đổi với HS về một số ứng dụn

def Check(): kq = True for s in range(n): 4 5 6 7 8 9 10 11 12 13 14 15, for t in range(n): mark[ : ] = [False]*n prev[ : ] = [None]*n BFS(s) if s != t and prev

1. Bài toán tìm đường đi Cho trước hai đỉnh s, t. Kiểm tra xem có đường đi từ đỉnh s đến t thông qua các cạnh của G hay không? Nếu có thì chỉ ra một cách đi như

Nhà xuất bản Giáo dục Việt Nam xin trân trọng cảm ơn các tác giả có tác phẩm, tư liệu được sử dụng, trích dẫn trong cuốn sách này. Chịu trách nhiệm xuất bản: Ch

Báo lỗi

Giao bài

Đang tải dữ liệu câu hỏi