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 một số thuật toán đồ thị<br /> <br /> Báo cáo nghiên cứu khoa học<br /> MỤC LỤC<br /> Mục lục<br /> <br /> 1. Lý do chọn đề tài …………………………………………………………….3<br /> 2. Những kiến thức cơ sở ………………………………………………………3<br /> 2.1. Khái niệm thuật toán ……………………………………………….3<br /> 2.2. Các đặc trưng của thuật toán ……………………………………….4<br /> 2.3. Độ phức tạp thuật toán ……………………………………………..4<br /> 3. Tổng quan về mô phỏng thuật toán ………………………………………….4<br /> 3.1. Khái niệm mô phỏng thuật toán ……………………………………4<br /> 3.2. Lịch sử mô phỏng thuật toán ……………………………………….5<br /> 3.3. Tác dụng của mô phỏng thuật toán trong dạy học………………….6<br /> 3.4. Một số yêu cầu đối với mô phỏng thuật toán ………………………8<br /> 4. Tổng quan về đồ thị ………………………………………………………….8<br /> 4.1. Định nghĩa đồ thị …………………………………………………...9<br /> 4.2. Phân loại đồ thị ……………………………………………………..9<br /> 4.3. Cây khung và cây khung nhỏ nhất …………………………………10<br /> 4.4. Các phương pháp biểu diễn đồ thị ………………………………....10<br /> 5. Phân tích và thiết kế hệ thống mô phỏng thuật toán trên đồ thị …………….11<br /> 5.1. Phân tích hệ thống mô phỏng thuật toán đồ thị…………………….11<br /> 5.1.1. Mục đích……………………………………………………..11<br /> 5.1.2. Đặc điểm …………………………………………………….11<br /> 5.1.3. Kết quả phân tích…………………………………………….12<br /> 5.2. Thiết kế hệ thống mô phỏng thuật toán đồ thị……………………...14<br /> 5.2.1. Màn hình nền hệ thống mô phỏng…………………………...14<br /> 5.2.2. Giao diện chính và chức năng trình mô phỏng ……………..14<br /> 6. Cài đặt mô phỏng thuật toán đồ thị …………………………………………15<br /> 6.1. Công cụ lập trình …………………………………………………..15<br /> 6.2. Cài đặt thuật toán Prim …………………………………………….16<br /> 6.2.1. Bài toán ……………………………………………………..16<br /> 6.2.2. Ý tưởng thuật giải …………………………………………..16<br /> 6.3. Cài đặt các lớp trong chương trình…………………………………17<br /> 6.3.1. Lớp cơ sở …………………………………………………..17<br /> Bùi Thị Thuỷ - AK54.CNTT.ĐHSPHN<br /> <br /> 1<br /> <br /> Báo cáo nghiên cứu khoa học<br /> <br /> Mô phỏng một số thuật toán đồ thị<br /> <br /> 6.3.2. Lớp Prim ……………………………………………………18<br /> 6.3.3. Lớp Main …………………………………………………...18<br /> 7. Kết luận ……………………………………………………………………18<br /> 8. Hướng phát triển …………………………………………………………..18<br /> Tài liệu tham khảo<br /> <br /> Bùi Thị Thuỷ - AK54.CNTT.ĐHSPHN<br /> <br /> 2<br /> <br /> Báo cáo nghiên cứu khoa học<br /> <br /> Mô phỏng một số thuật toán đồ thị<br /> <br /> 1. Lý do chọn đề tài<br /> 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í<br /> 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ý<br /> 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ó<br /> 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<br /> 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<br /> 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<br /> 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,<br /> 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ị<br /> 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,<br /> 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<br /> 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<br /> 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,<br /> đồ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ô<br /> 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á<br /> 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<br /> 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<br /> 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.<br /> Như vậy mô phỏng thuật toán nói chung và mô phỏng các thuật toán đồ thị<br /> 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ó<br /> 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<br /> 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<br /> 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ó<br /> 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<br /> 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<br /> 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<br /> 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<br /> theo chiều rộng, chiều sâu trên đồ thị.<br /> 2. Những kiến thức cơ sở<br /> 2.1. Khái niệm thuật toán<br /> <br /> Bùi Thị Thuỷ - AK54.CNTT.ĐHSPHN<br /> <br /> 3<br /> <br /> Báo cáo nghiên cứu khoa học<br /> <br /> Mô phỏng một số thuật toán đồ thị<br /> <br /> 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<br /> 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<br /> hạn bước thực hiện các thao tác đã chỉ ra, ta đạt được mục tiêu đã định.<br /> 2.2. Các đặc trưng của thuật toán<br /> - 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,<br /> 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<br /> toán thì với một bộ dữ liệu vào chỉ cho duy nhất một kết quả ra.<br /> - 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<br /> lại và cho kết quả sau một số hữu hạn bước.<br /> - Tính đúng: Sau khi thực hiện tất cả các bước của thuật toán theo đúng<br /> 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<br /> quả đó được kiểm chứng bằng yêu cầu bài toán.<br /> - Tính phổ dụng: Thuật toán phải dễ sửa đổi để thích ứng được với bất kì<br /> 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.<br /> - 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<br /> 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.<br /> 2.3. Độ phức tạp thuật toán<br /> Cho f và g là hai hàm xác định dương với mọi n. Hàm f(n) được<br /> 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:<br /> f(n) ≤ c.g(n) với mọi n ≥ n0<br /> 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<br /> 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<br /> 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))).<br /> 3. Tổng quan về mô phỏng thuật toán<br /> 3.1. Khái niệm mô phỏng thuật toán<br /> Mô phỏng thuật toán (Algorithm Animation) là quá trình tách dữ liệu, thao<br /> tác, ngữ nghĩa và tạo mô phỏng đồ họa cho quá trình trên [Stasko 1990]. Mô<br /> 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<br /> giá chương trình và sửa lỗi chương trình.<br /> 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<br /> 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.<br /> <br /> Bùi Thị Thuỷ - AK54.CNTT.ĐHSPHN<br /> <br /> 4<br /> <br /> Báo cáo nghiên cứu khoa học<br /> <br /> Mô phỏng một số thuật toán đồ thị<br /> <br /> 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ự<br /> 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<br /> 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<br /> thuật toán.<br /> Mô phỏng thuật toán cũng được dùng để đánh giá một chương trình đã có bằng<br /> 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<br /> được hiệu năng của hệ thống.<br /> 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<br /> 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<br /> 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<br /> 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<br /> 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<br /> 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<br /> 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ó<br /> thể xảy ra trong chương trình.<br /> 3.2. Lịch sử mô phỏng thuật toán<br /> Mô phỏng thuật toán đã được xây dựng từ hai thập kỷ gần đây. Nhưng chương<br /> trình mô phỏng thuật toán đầu tiên là của Ken Knowlton ở Bell Telephone Laboratories<br /> 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<br /> triển mạnh vào đầu những năm 80 của thế kỷ 20.<br /> Vào năm 1981, video (sorting out sorting) được xây dựng bởi Ronald Baecker ở<br /> đạ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à<br /> 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<br /> 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<br /> 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].<br /> Từ khi hai hệ thống của BALSA và TANGO được phát triển, các hệ thống đi sau<br /> 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<br /> 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,<br /> Bùi Thị Thuỷ - AK54.CNTT.ĐHSPHN<br /> <br /> 5<br /> <br />