1
PHÁT TRIỂN NĂNG LỰC HỌC SINH THÔNG QUA THUẬT TOÁN TÌM KIẾM
THEO CHIỀU SÂU (DFS) VÀ TÌM KIẾM THEO CHIỀU RỘNG (BFS)
A. MỞ ĐẦU
1. Lý do chọn đề tài.
Đổi mới phương pháp dạy học là một nhiệm vụ quan trọng của ngành giáo dục
nhằm nâng cao chất lượng đào tạo, góp phần thực hiện công nghiệp hoá hiện đại
hóa đất nước.
Lý thuyết đồ thị (trong Tin học) là một chuyên ngành quan trọng đã được ứng
dụng vào nhiều ngành khoa học, kỹ thuật khác nhau vì lý thuyết đồ thị là phương
pháp khoa học có tính khái quát cao, có tính ổn định vững chắc để mã hóa các mối
quan hệ của các đối tượng được nghiên cứu.
Vận dụng lý thuyết đồ thị trong dạy học sinh để mô hình hóa các mối quan hệ
chuyển thành phương pháp dạy học đặc thù sẽ nâng cao được hiệu quả dạy học
thúc đẩy quá trình tự học tự nghiên cứu của học sinh theo hướng tối ưu hóa đặc
biệt nhằm rèn luyện năng lực hệ thống hóa kiến thức và năng lực sáng tạo của học
sinh. Việc cung cấp thêm một phương pháp giải bài tập cho học sinh Tin học 11
tham gia học lập trình là một nhu cầu cần thiết. Xuất phát từ những lý do trên tôi
lựa chọn đề tài: “Phát triển năng lực học sinh thông qua thuật toán tìm kiếm
theo chiều sâu (DFS) và tìm kiếm theo chiều rộng (BFS)”.
2. Mục tiêu, nhiệm vụ của đề tài.
- Mục tiêu của đề tài: Chỉ ra hướng vận dụng DFS và BFS trong lý thuyết đồ thị
vào giải các bài toán và tìm ra các biện pháp để giúp học sinh trung học phổ thông
hình thành và phát triển năng lực vận dụng lý thuyết đồ thị vào giải bài tập lập
trình.
- Nhiệm vụ của đề tài:
- Tìm hiểu những nội dung cơ bản của lý thuyết đồ thị được trang bị cho học
sinh Tin học.
- Chỉ ra hệ thống bài tập có thể vận dụng lý thuyết đồ thị để giải.
- Chỉ ra được những dấu hiệu cụ thể để nhận dạng “Bài toán” có thể khai thác lý
thuyết đồ thị trong quá trình giải bài toán.
- Chỉ ra các phương án vận dụng lý thuyết đồ thị vào giải toán.
2
+ Tiếp cận chương trình mới môn Tin học 2018 phần đồ thị có trong mạch kiến
thức CS
3. Giả thuyết khoa học.
Nếu ta có các phương pháp giúp học sinh Tin học 11 vận dụng kiến thức về lý
thuyết đồ thị vào giải các bài toán thì sẽ giúp học sinh giải quyết được một số lớp
bài toán góp phần nâng cao chất lượng dạy học cũng như phát triển được năng lực
của học sinh.
4. Phương pháp nghiên cứu.
a. Nghiên cứu lý luận.
- Nghiên cứu các văn bản, tài liệu chỉ đạo của Bộ GD & ĐT liên quan đến đổi mới
phương pháp dạy học, đổi mới ra đề kiểm tra, danh mục thiết bị dạy học Tin học.
- SGK, phân phối chương trình, sách giáo viên, chuẩn của bộ môn Tin ở trung học
phổ thông, sách nâng cao, sách chuyên đề.
- Các tài liệu về lý thuyết đồ thị và những ứng dụng của nó trong thực tiễn cuộc
sống và trong dạy học.
- Các công trình nghiên cứu các vấn đề liên quan trực tiếp đến phương pháp đồ thị.
b. Thực nghiệm sư phạm.
- Chỉ ra cho học sinh các dấu hiệu "nhận dạng" và cách thức vận dụng lý thuyết đồ
thị vào giải bài tập.
- Biên soạn hệ thống bài tập luyện tập cho học sinh và một số đề bài kiểm tra để
đánh giá khả năng vận dụng lý thuyết đồ thị vào giải các bài toán.
- Tiến hành thực nghiệm và đánh giá kết quả thực nghiệm.
3
B. NỘI DUNG
I. CƠ SỞ LÝ LUẬN CỦA VẤN ĐỀ.
1. Đồ thị và tầm quan trọng.
Lý thuyết đồ thị là một lĩnh vực nghiên cứu đã có từ lâu và có nhiều ứng dụng
hiện đại. Các bài toán đặt ra nếu được đưa về lý thuyết đồ thị để giải sẽ tiết kiệm
được rất nhiều thời gian, ý tưởng thuật toán sẽ rõ ràng, chương trình ngắn gọn và
dễ hiểu. Nếu hiểu và biết vận dụng tốt lý thuyết đồ thị sẽ giúp chúng ta giải quyết
được rất nhiều bài toán đặt ra trong thực tế (xem ở phần giải quyết vấn đề). Khoa
học và kỹ thuật phát triển làm xuất hiện hàng loạt bài toán trong thực tiển được quy
về mô hình đồ thị.
1.1. Định nghĩa đồ thị: Cho tập hợp X khác rỗng, E là tập hợp các cặp phần tử
của X được sắp xếp thứ tự hoặc không sắp thứ tự. Cặp (X, E) được gọi là một đồ
thị. Kí hiệu đồ thị là G = (X, E) hoặc đôi khi nếu không gây nhầm lẫn kí hiệu tắt là
G.
1.2. Một số khái nhiệm.
- Các phần tử thuộc tập X gọi là đỉnh của đồ thị G.
- Cho 2 đỉnh x1, x2X, nếu e = (x1,x2)E là cặp sắp thứ tự thì e được gọi là một
cung của đồ thị, hoặc nếu e là cặp không sắp thứ tự thì e được gọi là một cạnh của
đồ thị.
- e = (x1,x2) là cung thì x1 là đỉnh đầu của cung, x2 là đỉnh cuối của cung e.
- e = (x1,x2) là cạnh thì x1 và x2 là 2 đỉnh kề của cạnh e hoặc 2 đỉnh thuộc cạnh e.
- Hai đỉnh x1 và x2 (x1 ≠ x2) của đồ thị được gọi là 2 đỉnh kề nhau nếu chúng là 2
đầu của một cạnh hoặc một cung.
- Hai cạnh a, b (hoặc 2 cung a, b) gọi là 2 cạnh kề nhau (hoặc 2 cung kề nhau)
nếu chúng có một đỉnh chung.
- Khuyên là cạnh (hoặc cung) có 2 đầu trùng nhau.
- Đỉnh treo là đỉnh thuộc duy nhất một cạnh hoặc cung.
- Đỉnh cô lập là đỉnh không thuộc cạnh hoặc cung nào.
4
1.3. Phân loại đồ thị.
Cho đồ thị G = (X, E), nếu E chỉ gồm các cạnh thì G là đồ thị vô hương. Nếu E
chỉ gồm các cung thì đồ thị G là đồ thị có hướng. Nếu E gồm cả cạnh và cung thì
G là đồ thị hỗn hợp.
Đa đồ thị: Đồ thị G = (X,E) vô hướng (hoặc có hướng) là đa đồ thị khi và chỉ khi
nó là đồ thị không khuyên và có ít nhất một cặp đỉnh được nối với nhau bằng ít
nhất 2 cạnh (hoặc 2 cung nối theo thứ tự của cặp đỉnh).
Đơn đồ thị: Đồ thị G = (X,E) vô hướng (hoặc có hướng) là đơn đồ thị khi và chỉ
khi nó là đồ thị không khuyên và mỗi cặp đỉnh được nối với nhau không quá một
cạnh (hoặc cung).
2. Biểu diễn đồ thị.
Biểu diễn đồ thị trên máy tính theo cấu trúc nào thì sẽ có giải thuật theo cấu trúc
đó. Với học sinh Tin học 11, biểu diễn bằng ma trận (mảng 2 chiều) là dễ hiểu và
phù hợp nhất. Cách khai thác trên mảng 2 chiều đã được học sinh làm nhiều ở
SGK Tin học 11.
Các cách biểu diễn đồ thị:
2.1. Biểu diễn bằng hình học.
Minh họa cách biểu diễn
`
Huế
Hà Tây
Thanh Hoá
Nam Định
TP. HCM
Đ.Nai
Khánh Hoà
Long An
An Giang
Hà Nội
Hình 1: Đơn đồ thị, vô hướng
5
`
2.2. Biểu diễn đồ thị bằng ma trận liên thuộc (Ma trận kề).
Giả sử đồ thị G = (X, E) có tập đỉnh X = (x1,x2, x3,…,xn), tập cạnh (hoặc cung)
là E. Ta xây dựng ma trận vuông A cấp n sao cho i,j, 1i,jn có:
Ma trận A là ma trận liên thuộc (ma trận kề)
Nhận xét : Nếu G là độ thị vô hướng thì
Ma trận A sẽ đối xứng qua đường chéo chính,
Aij = Aji i,j, 1i,jn.
2.3. Biểu diễn bằng ma trận trọng số.
Trong nhiều bài toán về đồ thị, mỗi cạnh (hoặc cung) e = (xi, xj) của đồ thị
thường được gắn với một số c (e) gọi là trọng số của cạnh (hoặc cung) e. Khi đó
thường xây dựng ma trận vuông cấp n là ma trận C có mỗi phần tử C[i,j] = c(e) nếu
tồn tại cạnh (hoặc cung) e = (xi, xj), ngược lại khi không có cạnh nối xi với xj thì
C[i,j] = (kí hiệu là giá trị không xác định). Trong nhiều trường hợp, ngậm
định C[i,i] = 0 với mọi đỉnh i trong đồ thị không khuyên.
3. Tìm kiếm trên đồ thị và tìm thành phần liên thông trên đồ thị.
Hiểu được bản chất của các phép tìm kiếm và tìm thành phần liên thông trên đồ
thị chúng ta có thể giải quyết được rất nhiều các dạng bài toán đặt ra (thể hiện ở
1
2
3
5
4
Hình 4: Đồ thị và ma trận kề
1
2
3
4
5
6
1
2
3
4
5
Hình 3: Đa đồ thị, có hướng