Xem mẫu
Mô phỏng một số thuật toán đồ thị
Báo cáo nghiên cứu khoa học
MỤC LỤC
Mục lục
1. Lý do chọn đề tài …………………………………………………………….3
2. Những kiến thức cơ sở ………………………………………………………3
2.1. Khái niệm thuật toán ……………………………………………….3
2.2. Các đặc trưng của thuật toán ……………………………………….4
2.3. Độ phức tạp thuật toán ……………………………………………..4
3. Tổng quan về mô phỏng thuật toán ………………………………………….4
3.1. Khái niệm mô phỏng thuật toán ……………………………………4
3.2. Lịch sử mô phỏng thuật toán ……………………………………….5
3.3. Tác dụng của mô phỏng thuật toán trong dạy học………………….6
3.4. Một số yêu cầu đối với mô phỏng thuật toán ………………………8
4. Tổng quan về đồ thị ………………………………………………………….8
4.1. Định nghĩa đồ thị …………………………………………………...9
4.2. Phân loại đồ thị ……………………………………………………..9
4.3. Cây khung và cây khung nhỏ nhất …………………………………10
4.4. Các phương pháp biểu diễn đồ thị ………………………………....10
5. Phân tích và thiết kế hệ thống mô phỏng thuật toán trên đồ thị …………….11
5.1. Phân tích hệ thống mô phỏng thuật toán đồ thị…………………….11
5.1.1. Mục đích……………………………………………………..11
5.1.2. Đặc điểm …………………………………………………….11
5.1.3. Kết quả phân tích…………………………………………….12
5.2. Thiết kế hệ thống mô phỏng thuật toán đồ thị……………………...14
5.2.1. Màn hình nền hệ thống mô phỏng…………………………...14
5.2.2. Giao diện chính và chức năng trình mô phỏng ……………..14
6. Cài đặt mô phỏng thuật toán đồ thị …………………………………………15
6.1. Công cụ lập trình …………………………………………………..15
6.2. Cài đặt thuật toán Prim …………………………………………….16
6.2.1. Bài toán ……………………………………………………..16
6.2.2. Ý tưởng thuật giải …………………………………………..16
6.3. Cài đặt các lớp trong chương trình…………………………………17
6.3.1. Lớp cơ sở …………………………………………………..17
Bùi Thị Thuỷ - AK54.CNTT.ĐHSPHN
1
Báo cáo nghiên cứu khoa học
Mô phỏng một số thuật toán đồ thị
6.3.2. Lớp Prim ……………………………………………………18
6.3.3. Lớp Main …………………………………………………...18
7. Kết luận ……………………………………………………………………18
8. Hướng phát triển …………………………………………………………..18
Tài liệu tham khảo
Bùi Thị Thuỷ - AK54.CNTT.ĐHSPHN
2
Báo cáo nghiên cứu khoa học
Mô phỏng một số thuật toán đồ thị
1. Lý do chọn đề tài
Lý thuyết đồ thị là một vấn đề hết sức phức tạp, hơn nữa nó chiếm một vị trí
quan trọng trong khối kiến thức cơ sở của ngành công nghệ thông tin. Để hiểu được lý
thuyết về đồ thị cũng như hiểu được hoạt động của các thuật toán trên đồ thị cần phải có
thời gian tìm hiểu lâu dài. Việc dạy và học về đồ thị trong nhà trường cũng gặp nhiều
khó khăn. Các thuật toán khiến cho người học khó hiểu, khó hình dung nhất là với
những người mới bắt đầu học Tin ví dụ như thuật toán Dijkstra và nếu chỉ với các dòng
lệnh của thuật toán, người dạy đôi khi cũng rất khó truyền đạt cho người học ý tưởng,
hoạt động của thuật toán như thế nào. Sử dụng việc mô phỏng các thuật toán trên đồ thị
sẽ giải quyết được vấn đề này. Bởi vì việc mô phỏng với giao diện đồ hoạ, rất trực quan,
có chú giải từng bước, đồng thời với giao diện đồ họa trực quan như vậy, người sử dụng
có thể tương tác với hệ thống mô phỏng. Mô phỏng sẽ giúp cho người học nhanh chóng
hiểu được bản chất, hiểu được từng câu lệnh trong thuật toán hoạt động như thế nào,
đồng thời đánh giá được tính đúng đắn của thuật toán. Còn đối với người dạy, mô
phỏng sẽ giúp cho người dạy dễ dàng truyền đạt ý tưởng của thuật toán, giúp cho quá
trình giảng dạy thuận lợi hơn. Hơn nữa, mô phỏng làm cho người học cảm thấy hứng
thú hơn khi tiếp xúc với các thuật toán trên đồ thị. Mô phỏng cũng là một công cụ giảng
dạy hiệu quả cho người dạy và cũng là một tư liệu học tập tốt.
Như vậy mô phỏng thuật toán nói chung và mô phỏng các thuật toán đồ thị
nói riêng mang lại nhiều lợi ích trong việc dạy và học về lý thuyết đồ thị. Đồng thời nó
cũng góp phần quan trọng vào việc ứng dụng công nghệ thông tin vào việc giảng dạy
trong nhà trường. Thuật toán về đồ thị chiếm một số lượng khá lớn, tuy nhiên số lượng
thuật toán được mô phỏng và đưa vào áp dụng để giảng dạy thì còn hạn chế. Cũng có
nhiều trang Web về mô phỏng thuật toán đồ thị nhưng hầu hết chưa có hệ thống. Cao
học K15 cũng có một luận văn mô phỏng thuật toán đồ thị như thuật toán Dijkstra, thuật
toán Kruskal. Vì vậy trong khuôn khổ nghiên cứu của mình, em xin tiếp tục nghiên cứu
việc mô phỏng một số thuật toán đồ thị như thuật toán Prim, các thuật toán tìm kiếm
theo chiều rộng, chiều sâu trên đồ thị.
2. Những kiến thức cơ sở
2.1. Khái niệm thuật toán
Bùi Thị Thuỷ - AK54.CNTT.ĐHSPHN
3
Báo cáo nghiên cứu khoa học
Mô phỏng một số thuật toán đồ thị
Thuật toán là một hệ thống chặt chẽ và rõ ràng các quy tắc nhằm xác định một
dãy các thao tác trên cấu trúc dữ liệu sao cho: với một bộ dữ liệu vào, sau một số hữu
hạn bước thực hiện các thao tác đã chỉ ra, ta đạt được mục tiêu đã định.
2.2. Các đặc trưng của thuật toán
- Tính đơn định: Ở mỗi bước của thuật toán, các thao tác phải hết sức rõ ràng,
không gây nên sự nhập nhằng, lộn xộn, đa nghĩa. Thực hiện đúng các bước của thuật
toán thì với một bộ dữ liệu vào chỉ cho duy nhất một kết quả ra.
- Tính dừng: Thuật toán không được rơi vào quá trình vô hạn, phải dừng
lại và cho kết quả sau một số hữu hạn bước.
- Tính đúng: Sau khi thực hiện tất cả các bước của thuật toán theo đúng
quá trình đã định, ta phải đạt được kết quả mong muốn với mọi bộ dữ liệu đầu vào. Kết
quả đó được kiểm chứng bằng yêu cầu bài toán.
- Tính phổ dụng: Thuật toán phải dễ sửa đổi để thích ứng được với bất kì
bài toán nào trong một lớp các bài toán và có thể làm việc trên các dữ liệu khác nhau.
- Tính khả thi: Kích thước dữ liệu phải đủ nhỏ, thuật toán phải được máy tính
thực hiện trong thời gian cho phép, thuật toán phải dễ hiểu và dễ cài đặt.
2.3. Độ phức tạp thuật toán
Cho f và g là hai hàm xác định dương với mọi n. Hàm f(n) được
gọi là O(g(n)) nếu tồn tại một hằng số c > 0 và một giá trị n0 sao cho:
f(n) ≤ c.g(n) với mọi n ≥ n0
Nghĩa là nếu xét những giá trị n ≥ n0 thì hàm f(n) sẽ bị chặn trên bởi một
hằng số nhân với g(n). Khi đó, nếu f(n) là thời gian thực hiện của một giải thuật
thì ta nói giải thuật đó có cấp là g(n) (hay độ phức tạp tính toán là O(g(n))).
3. Tổng quan về mô phỏng thuật toán
3.1. Khái niệm mô phỏng thuật toán
Mô phỏng thuật toán (Algorithm Animation) là quá trình tách dữ liệu, thao
tác, ngữ nghĩa và tạo mô phỏng đồ họa cho quá trình trên [Stasko 1990]. Mô
phỏng thuật toán được thiết kế để giúp người dùng có thể hiểu thuật toán, đánh
giá chương trình và sửa lỗi chương trình.
Một chương trình máy tính chứa các cấu trúc dữ liệu của thuật toán mà nó thực
thi. Trong quá trình thực thi chương trình, các giá trị trong cơ sở dữ liệu được thay đổi.
Bùi Thị Thuỷ - AK54.CNTT.ĐHSPHN
4
Báo cáo nghiên cứu khoa học
Mô phỏng một số thuật toán đồ thị
Mô phỏng thuật toán sử dụng biểu diễn đồ họa để biểu diễn cấu trúc dữ liệu và chỉ ra sự
thay đổi giá trị trong cơ sở dữ liệu trong mỗi trạng thái. Thông qua đó, người sử dụng
có thể xem được từng bước thực thi chương trình và nhờ vậy có thể hiểu chi tiết được
thuật toán.
Mô phỏng thuật toán cũng được dùng để đánh giá một chương trình đã có bằng
cách cung cấp các mô phỏng cho các thành phần của hệ thống, nhờ đó có thể kiểm tra
được hiệu năng của hệ thống.
Bên cạnh việc giúp người sử dụng hiểu hơn về hệ thống, mô phỏng thuật toán
còn được dùng để giúp thực hiện quá trình dò lỗi dễ dàng hơn. Để sử dụng mô phỏng
thuật toán trong quá trình dò lỗi của một chương trình, người sử dụng chú thích vào các
trạng thái của chương trình để tạo ra các lệnh mô phỏng, sau đó chúng sẽ được đưa vào
hệ thống mô phỏng thuật toán để tạo mô phỏng. Người sử dụng có thể xem chương
trình của họ đã thực hiện như thế nào, các giá trị dữ liệu ở mỗi bước và một bước sẽ ảnh
hưởng tới các bước sau như thế nào. Nó sẽ giúp người sử dụng tìm ra tất cả các lỗi có
thể xảy ra trong chương trình.
3.2. Lịch sử mô phỏng thuật toán
Mô phỏng thuật toán đã được xây dựng từ hai thập kỷ gần đây. Nhưng chương
trình mô phỏng thuật toán đầu tiên là của Ken Knowlton ở Bell Telephone Laboratories
khi mô phỏng ngôn ngữ liên kết danh sách vào năm 1966. Mô phỏng thuật toán phát
triển mạnh vào đầu những năm 80 của thế kỷ 20.
Vào năm 1981, video (sorting out sorting) được xây dựng bởi Ronald Baecker ở
đại học Toronto được coi là khởi điểm của lĩnh vực mô phỏng thuật toán. Từ đó các nhà
giáo dục đã sử dụng mô phỏng thuật toán để trợ giúp quá trình dạy học. Giữa những
năm 80 và đầu những năm 90, hai hệ thống có ảnh hưởng mạnh đến về sau được phát
triển và có ý nghĩa lớn trên tất cả những hệ thống sau này. Hai hệ thống này là BALSAI (Brown ALgorithm Simulator and Animator) [Brown 1984] và TANGO (Transitionbased Animation GeneratiOn) [Stasko 1990].
Từ khi hai hệ thống của BALSA và TANGO được phát triển, các hệ thống đi sau
của hai hệ thống đáng chú ý này cũng được phát triển. Với việc phát triển của công
nghệ mới, tính phổ dụng của mạng toàn cầu và sự tiến hóa của ngôn ngữ lập trình Java,
Bùi Thị Thuỷ - AK54.CNTT.ĐHSPHN
5
nguon tai.lieu . vn
Báo cáo nghiên cứu khoa học
MỤC LỤC
Mục lục
1. Lý do chọn đề tài …………………………………………………………….3
2. Những kiến thức cơ sở ………………………………………………………3
2.1. Khái niệm thuật toán ……………………………………………….3
2.2. Các đặc trưng của thuật toán ……………………………………….4
2.3. Độ phức tạp thuật toán ……………………………………………..4
3. Tổng quan về mô phỏng thuật toán ………………………………………….4
3.1. Khái niệm mô phỏng thuật toán ……………………………………4
3.2. Lịch sử mô phỏng thuật toán ……………………………………….5
3.3. Tác dụng của mô phỏng thuật toán trong dạy học………………….6
3.4. Một số yêu cầu đối với mô phỏng thuật toán ………………………8
4. Tổng quan về đồ thị ………………………………………………………….8
4.1. Định nghĩa đồ thị …………………………………………………...9
4.2. Phân loại đồ thị ……………………………………………………..9
4.3. Cây khung và cây khung nhỏ nhất …………………………………10
4.4. Các phương pháp biểu diễn đồ thị ………………………………....10
5. Phân tích và thiết kế hệ thống mô phỏng thuật toán trên đồ thị …………….11
5.1. Phân tích hệ thống mô phỏng thuật toán đồ thị…………………….11
5.1.1. Mục đích……………………………………………………..11
5.1.2. Đặc điểm …………………………………………………….11
5.1.3. Kết quả phân tích…………………………………………….12
5.2. Thiết kế hệ thống mô phỏng thuật toán đồ thị……………………...14
5.2.1. Màn hình nền hệ thống mô phỏng…………………………...14
5.2.2. Giao diện chính và chức năng trình mô phỏng ……………..14
6. Cài đặt mô phỏng thuật toán đồ thị …………………………………………15
6.1. Công cụ lập trình …………………………………………………..15
6.2. Cài đặt thuật toán Prim …………………………………………….16
6.2.1. Bài toán ……………………………………………………..16
6.2.2. Ý tưởng thuật giải …………………………………………..16
6.3. Cài đặt các lớp trong chương trình…………………………………17
6.3.1. Lớp cơ sở …………………………………………………..17
Bùi Thị Thuỷ - AK54.CNTT.ĐHSPHN
1
Báo cáo nghiên cứu khoa học
Mô phỏng một số thuật toán đồ thị
6.3.2. Lớp Prim ……………………………………………………18
6.3.3. Lớp Main …………………………………………………...18
7. Kết luận ……………………………………………………………………18
8. Hướng phát triển …………………………………………………………..18
Tài liệu tham khảo
Bùi Thị Thuỷ - AK54.CNTT.ĐHSPHN
2
Báo cáo nghiên cứu khoa học
Mô phỏng một số thuật toán đồ thị
1. Lý do chọn đề tài
Lý thuyết đồ thị là một vấn đề hết sức phức tạp, hơn nữa nó chiếm một vị trí
quan trọng trong khối kiến thức cơ sở của ngành công nghệ thông tin. Để hiểu được lý
thuyết về đồ thị cũng như hiểu được hoạt động của các thuật toán trên đồ thị cần phải có
thời gian tìm hiểu lâu dài. Việc dạy và học về đồ thị trong nhà trường cũng gặp nhiều
khó khăn. Các thuật toán khiến cho người học khó hiểu, khó hình dung nhất là với
những người mới bắt đầu học Tin ví dụ như thuật toán Dijkstra và nếu chỉ với các dòng
lệnh của thuật toán, người dạy đôi khi cũng rất khó truyền đạt cho người học ý tưởng,
hoạt động của thuật toán như thế nào. Sử dụng việc mô phỏng các thuật toán trên đồ thị
sẽ giải quyết được vấn đề này. Bởi vì việc mô phỏng với giao diện đồ hoạ, rất trực quan,
có chú giải từng bước, đồng thời với giao diện đồ họa trực quan như vậy, người sử dụng
có thể tương tác với hệ thống mô phỏng. Mô phỏng sẽ giúp cho người học nhanh chóng
hiểu được bản chất, hiểu được từng câu lệnh trong thuật toán hoạt động như thế nào,
đồng thời đánh giá được tính đúng đắn của thuật toán. Còn đối với người dạy, mô
phỏng sẽ giúp cho người dạy dễ dàng truyền đạt ý tưởng của thuật toán, giúp cho quá
trình giảng dạy thuận lợi hơn. Hơn nữa, mô phỏng làm cho người học cảm thấy hứng
thú hơn khi tiếp xúc với các thuật toán trên đồ thị. Mô phỏng cũng là một công cụ giảng
dạy hiệu quả cho người dạy và cũng là một tư liệu học tập tốt.
Như vậy mô phỏng thuật toán nói chung và mô phỏng các thuật toán đồ thị
nói riêng mang lại nhiều lợi ích trong việc dạy và học về lý thuyết đồ thị. Đồng thời nó
cũng góp phần quan trọng vào việc ứng dụng công nghệ thông tin vào việc giảng dạy
trong nhà trường. Thuật toán về đồ thị chiếm một số lượng khá lớn, tuy nhiên số lượng
thuật toán được mô phỏng và đưa vào áp dụng để giảng dạy thì còn hạn chế. Cũng có
nhiều trang Web về mô phỏng thuật toán đồ thị nhưng hầu hết chưa có hệ thống. Cao
học K15 cũng có một luận văn mô phỏng thuật toán đồ thị như thuật toán Dijkstra, thuật
toán Kruskal. Vì vậy trong khuôn khổ nghiên cứu của mình, em xin tiếp tục nghiên cứu
việc mô phỏng một số thuật toán đồ thị như thuật toán Prim, các thuật toán tìm kiếm
theo chiều rộng, chiều sâu trên đồ thị.
2. Những kiến thức cơ sở
2.1. Khái niệm thuật toán
Bùi Thị Thuỷ - AK54.CNTT.ĐHSPHN
3
Báo cáo nghiên cứu khoa học
Mô phỏng một số thuật toán đồ thị
Thuật toán là một hệ thống chặt chẽ và rõ ràng các quy tắc nhằm xác định một
dãy các thao tác trên cấu trúc dữ liệu sao cho: với một bộ dữ liệu vào, sau một số hữu
hạn bước thực hiện các thao tác đã chỉ ra, ta đạt được mục tiêu đã định.
2.2. Các đặc trưng của thuật toán
- Tính đơn định: Ở mỗi bước của thuật toán, các thao tác phải hết sức rõ ràng,
không gây nên sự nhập nhằng, lộn xộn, đa nghĩa. Thực hiện đúng các bước của thuật
toán thì với một bộ dữ liệu vào chỉ cho duy nhất một kết quả ra.
- Tính dừng: Thuật toán không được rơi vào quá trình vô hạn, phải dừng
lại và cho kết quả sau một số hữu hạn bước.
- Tính đúng: Sau khi thực hiện tất cả các bước của thuật toán theo đúng
quá trình đã định, ta phải đạt được kết quả mong muốn với mọi bộ dữ liệu đầu vào. Kết
quả đó được kiểm chứng bằng yêu cầu bài toán.
- Tính phổ dụng: Thuật toán phải dễ sửa đổi để thích ứng được với bất kì
bài toán nào trong một lớp các bài toán và có thể làm việc trên các dữ liệu khác nhau.
- Tính khả thi: Kích thước dữ liệu phải đủ nhỏ, thuật toán phải được máy tính
thực hiện trong thời gian cho phép, thuật toán phải dễ hiểu và dễ cài đặt.
2.3. Độ phức tạp thuật toán
Cho f và g là hai hàm xác định dương với mọi n. Hàm f(n) được
gọi là O(g(n)) nếu tồn tại một hằng số c > 0 và một giá trị n0 sao cho:
f(n) ≤ c.g(n) với mọi n ≥ n0
Nghĩa là nếu xét những giá trị n ≥ n0 thì hàm f(n) sẽ bị chặn trên bởi một
hằng số nhân với g(n). Khi đó, nếu f(n) là thời gian thực hiện của một giải thuật
thì ta nói giải thuật đó có cấp là g(n) (hay độ phức tạp tính toán là O(g(n))).
3. Tổng quan về mô phỏng thuật toán
3.1. Khái niệm mô phỏng thuật toán
Mô phỏng thuật toán (Algorithm Animation) là quá trình tách dữ liệu, thao
tác, ngữ nghĩa và tạo mô phỏng đồ họa cho quá trình trên [Stasko 1990]. Mô
phỏng thuật toán được thiết kế để giúp người dùng có thể hiểu thuật toán, đánh
giá chương trình và sửa lỗi chương trình.
Một chương trình máy tính chứa các cấu trúc dữ liệu của thuật toán mà nó thực
thi. Trong quá trình thực thi chương trình, các giá trị trong cơ sở dữ liệu được thay đổi.
Bùi Thị Thuỷ - AK54.CNTT.ĐHSPHN
4
Báo cáo nghiên cứu khoa học
Mô phỏng một số thuật toán đồ thị
Mô phỏng thuật toán sử dụng biểu diễn đồ họa để biểu diễn cấu trúc dữ liệu và chỉ ra sự
thay đổi giá trị trong cơ sở dữ liệu trong mỗi trạng thái. Thông qua đó, người sử dụng
có thể xem được từng bước thực thi chương trình và nhờ vậy có thể hiểu chi tiết được
thuật toán.
Mô phỏng thuật toán cũng được dùng để đánh giá một chương trình đã có bằng
cách cung cấp các mô phỏng cho các thành phần của hệ thống, nhờ đó có thể kiểm tra
được hiệu năng của hệ thống.
Bên cạnh việc giúp người sử dụng hiểu hơn về hệ thống, mô phỏng thuật toán
còn được dùng để giúp thực hiện quá trình dò lỗi dễ dàng hơn. Để sử dụng mô phỏng
thuật toán trong quá trình dò lỗi của một chương trình, người sử dụng chú thích vào các
trạng thái của chương trình để tạo ra các lệnh mô phỏng, sau đó chúng sẽ được đưa vào
hệ thống mô phỏng thuật toán để tạo mô phỏng. Người sử dụng có thể xem chương
trình của họ đã thực hiện như thế nào, các giá trị dữ liệu ở mỗi bước và một bước sẽ ảnh
hưởng tới các bước sau như thế nào. Nó sẽ giúp người sử dụng tìm ra tất cả các lỗi có
thể xảy ra trong chương trình.
3.2. Lịch sử mô phỏng thuật toán
Mô phỏng thuật toán đã được xây dựng từ hai thập kỷ gần đây. Nhưng chương
trình mô phỏng thuật toán đầu tiên là của Ken Knowlton ở Bell Telephone Laboratories
khi mô phỏng ngôn ngữ liên kết danh sách vào năm 1966. Mô phỏng thuật toán phát
triển mạnh vào đầu những năm 80 của thế kỷ 20.
Vào năm 1981, video (sorting out sorting) được xây dựng bởi Ronald Baecker ở
đại học Toronto được coi là khởi điểm của lĩnh vực mô phỏng thuật toán. Từ đó các nhà
giáo dục đã sử dụng mô phỏng thuật toán để trợ giúp quá trình dạy học. Giữa những
năm 80 và đầu những năm 90, hai hệ thống có ảnh hưởng mạnh đến về sau được phát
triển và có ý nghĩa lớn trên tất cả những hệ thống sau này. Hai hệ thống này là BALSAI (Brown ALgorithm Simulator and Animator) [Brown 1984] và TANGO (Transitionbased Animation GeneratiOn) [Stasko 1990].
Từ khi hai hệ thống của BALSA và TANGO được phát triển, các hệ thống đi sau
của hai hệ thống đáng chú ý này cũng được phát triển. Với việc phát triển của công
nghệ mới, tính phổ dụng của mạng toàn cầu và sự tiến hóa của ngôn ngữ lập trình Java,
Bùi Thị Thuỷ - AK54.CNTT.ĐHSPHN
5