Xem bản đẹp trên 123doc.vn

Mô phỏng một số thuật toán đồ thị.doc

Báo cáo nghiên cứu khoa học Mô phỏng một số thuật toán đồ thị
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ị n
0
sao cho:
f(n) ≤ c.g(n) với mọi n ≥ n
0
Nghĩa là nếu xét những giá trị n ≥ n
0
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à BALSA-I (Brown
ALgorithm Simulator and Animator) [Brown 1984] và TANGO (Transition-based
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, những
Bùi Thị Thuỷ - AK54.CNTT.ĐHSPHN
5
Báo cáo nghiên cứu khoa học Mô phỏng một số thuật toán đồ thị
người phát triển đã xây dựng những hệ thống mô phỏng thuật toán trực tuyến, có lợi thế
của những hệ thống mở dễ tiếp cận hơn.Một số nhà phát triển cũng hợp nhất việc sử dụng
đa phương tiện trong các hệ thống của họ. Việc sử dụng các hệ thống mô phỏng thuật
toán không còn bị bó hẹp trong các lớp học truyền thống hoặc phòng thí nghiệm giảng
dạy nữa mà đã được mở rộng để dạy từ xa.
Trong khoảng hai thập niên gần đây, một số rất lớn các hệ thống mô phỏng thuật
toán đã ra đời và phát triển mạnh mẽ. Phần lớn các hệ thống mô phỏng thuật toán đã đề
cập trong mục này đều phổ biến hơn và phức tạp hơn các hệ thống đang được sử dụng
trong thực tế. Chúng đã được phát triển và sử dụng bởi những nhà chuyên môn, với mục
đích giáo dục hoặc nghiên cứu thực nghiệm của họ. Một trong số các hệ thống này có
một kiến trúc phức tạp và cần những công nghệ đặc biệt để chạy nó. Chúng ta không có
bất kỳ tiện ích nào của các hệ thống này để xây dựng hệ thống mô phỏng các thuật toán
đồ thị; thay vào đó, chúng ta đã ước lượng được các hệ thống mô phỏng hiện hữu khác
mà kích thước nhỏ hơn và có những kiến trúc đơn giản hơn.
3.3. Tác dụng của mô phỏng thuật toán trong dạy học
Các hệ thống mô phỏng thuật toán được sử dụng rộng rãi như công cụ hỗ trợ
giảng dạy trong ngành giáo dục khoa học máy tính. Một số nghiên cứu thực nghiệm đã
ước lượng hiệu quả của chúng trong giáo dục và kết quả nhận được có thay đổi. Những
tác dụng của việc áp dụng mô phỏng thuật toán trong dạy học được ghi nhận lại như sau:
Việc sử dụng các hoạt cảnh mô phỏng thuật toán gây hứng thú cho người học, làm
tăng tính sáng tạo của người học. Sử dụng mô phỏng kết hợp với phương pháp thuyết
trình truyền thống làm tăng tốc độ hiểu biết cho người học. Ngoài ra mô phỏng giúp cho
người học dễ hiểu thuật toán hơn thông qua các bước mô phỏng trực quan kết hợp với mã
nguồn chương trình.
Tuy nhiên việc sử dụng mô phỏng thuật toán không phải lúc nào cũng đem lại
hiệu quả. Các nghiên cứu thực nghiệm của Stasko (1993) và Bynre (1996) đã cho kết quả
là giữa nhóm sinh viên sử dụng mô phỏng và nhóm không sử dụng mô phỏng thì hiệu quả
đạt được không có sự chênh lệch là mấy. Những kết quả thí nghiệm bất lợi này gợi ý
những yếu tố quan trọng khác trong việc sử dụng mô phỏng thuật toán. Các kết quả đã
thông báo rằng để đạt được hiệu quả mô phỏng thuật toán đầy đủ thì điều quan trọng là
Bùi Thị Thuỷ - AK54.CNTT.ĐHSPHN
6
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 được sử dụng phối hợp với những yếu tố khác. Phải để sinh viên tự mình sử
dụng, điều khiển quá trình mô phỏng và phải để họ tự tạo những bộ dữ liệu của riêng
mình. Để mô phỏng thuật toán mang lại hiệu quả cao nhất, nó phải thoả mãn những yêu
cầu sau đây :
Thứ nhất, sử dụng mô phỏng thuật toán phải song song với những chỉ dẫn, có hệ
thống trợ giúp sử dụng, phải có mô phỏng từng bước để người học hiểu từng bước của
giải thuật, có khả năng quay lui để ngườu học có thể quay lại những bước quan trọng,
đồng thời lấy ý kiến phản hồi từ sinh viên để cải thiện chương trình mô phỏng thuật toán
tốt hơn.
Hai là phải biết xây dựng mô phỏng hiệu quả : mô phỏng cái gì, mô phỏng như thế
nào, hình ảnh ra sao,...
Một chương trình mô phỏng thuật toán hiệu quả phải đáp ứng được các yêu cầu :
• Truy cập mở (Open access): Người dùng có thể truy cập hệ thống mô
phỏng mở. Hơn nữa, nếu có cài đặt hệ thống mô phỏng trong trường học, thì họ có thể
truy cập tới hệ thống này từ nhà hoặc từ bất cứ nơi nào khác.
• Mô phỏng một cách có điều khiển (Control animation): Người dùng có
thể tự tạo tập dữ liệu của chính mình khi sử dụng hệ thống mô phỏng. Trong khi các tập
dữ liệu được cài đặt sẵn cũng có thể giúp đỡ sinh viên có những sự hiểu biết ban đầu, hệ
thống nên có cả 2 tùy chọn này.
• Tương tác (Ineractivity): Hệ thống mô phỏng phải cung cấp được sự
Tương tác giữa người dùng và hệ thống. Sự tương tác bao gồm: người dùng xem theo
từng bước, hủy, chạy nhanh tới một bước mong muốn, hay xem lại từ đầu, ...
• Lịch sử (History): Hệ thống mô phỏng cho phép người dùng xem lại các
bước trước trong quá trình thực hiện.
• Phản hồi (Feedback): Phải tiếp thu phản hồi của sinh viên về việc sử dụng
hệ thống mô phỏng để ước lượng hiệu quả của hệ thống cũng như để cải thiện hệ thống.
3.4. Một số yêu cầu đối với mô phỏng thuật toán
Bùi Thị Thuỷ - AK54.CNTT.ĐHSPHN
7
Báo cáo nghiên cứu khoa học Mô phỏng một số thuật toán đồ thị
- Phản ánh đúng nội dung thuật toán : Thuật toán được đưa ra mô phỏng phải
chính xác, các bước thực hiện thuật toán phải trực quan và phản ánh đúng theo nội dung
thuật toán đã đưa ra để đảm bảo tính đúng đắn của thuật toán.
- Hệ thống mô phỏng phải được thực hiện theo từng bước : thuật toán
thường là trừu tượng, nếu để chương trình chạy tự động thì người dùng sẽ khó hiểu. Vì
vậy, cần phải có chế độ thực hiện mô phỏng thuật toán theo từng bước, để người học có
thể quan sát, theo dõi sự thay đổi giá trị của từng biến. Nhờ đó, sẽ giúp cho người học
hiểu thuật toán rõ hơn và nhanh hơn.
- Mô tả thuật toán phải có tính động: để mô tả trực quan hóa quá trình
thực hiện của thuật toán ta nên đưa vào hình ảnh động (có thể có âm thanh) để thể hiện sự
thay đổi của dữ liệu trong quá trình thực thi. Ví dụ như, trong thuật toán tìm cây khung
nhỏ nhất - thuật toán Prim, ta đưa vào các đối tượng đồ họa là đỉnh, cạnh. Trong quá trình
thực thi thuật toán thì các đỉnh/cạnh được chọn sẽ sáng nhấp nháy và đổi màu, sau khi
được chọn thì các đỉnh/cạnh sẽ được tô màu khác với màu ban đầu. Tương ứng với quan
sát sự thay đổi trên đồ thị, ta có thể đưa vào đoạn thuật toán thể hiện tương ứng và song
song với quá trình duyệt trên đồ thị. Nhờ đó mà thuật toán được thể hiện một cách rõ nét,
sinh động, trực quan. giúp người đọc dễ theo dõi, dễ hiểu thuật toán hơn.
- Thuật toán được thử nghiệm trong mọi trường hợp để đảm bảo thời gian
thực hiện tốt nhất : một thuật toán được mô phỏng phải đảm bảo là thuật toán tốt, dễ hiểu
và đúng đắn. Muốn vậy ta phải thử nghiệm trong các trường hợp dữ liệu ngẫu nhiên, tốt
nhất, xấu nhất. Nếu thuật toán vẫn chạy tốt và trong một thời gian cho phép thì thuật toán
mới hiệu quả. Ta không thể chấp nhận một thuật toán đúng mà thời gian chạy quá lớn.
- Tạo ra các mức độ khác nhau cho người dùng: Đối tượng học thuật toán
thường là các sinh viên. Họ có trình độ tiếp thu khác nhau, nên ta phải đưa ra nhiều chế
độ thao tác khác nhau để người học được phép lựa chọn.
4. Tổng quan về đồ thị
4.1. Định nghĩa đồ thị
Một đồ thị được hiểu là một bộ hai tập hợp hữu hạn: Tập hợp đỉnh và tập hợp
cạnh nối các đỉnh này với nhau. Một đồ thị được mô tả hình thức như sau:
Bùi Thị Thuỷ - AK54.CNTT.ĐHSPHN
8