Báo cáo nghiên cứu khoa học: Mô phỏng một số thuật toán đồ thị

Đề tài nghiên cứu khoa học "Mô phỏng một số thuật toán đồ thị" trình bày nội dung lý thuyết về thuật toán, mô phỏng thuật toán và đồ thị; phân tích và thiết kế hệ thống mô phỏng thuật toán trên đồ thị; cài đặt mô phỏng thuật toán đồ thị. Mời các bạn cùng tham khảo.
Nội dung trích xuất từ tài liệu:
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ịBáo cáo nghiên cứu khoa họcMỤC LỤCMục lục1. Lý do chọn đề tài …………………………………………………………….32. Những kiến thức cơ sở ………………………………………………………32.1. Khái niệm thuật toán ……………………………………………….32.2. Các đặc trưng của thuật toán ……………………………………….42.3. Độ phức tạp thuật toán ……………………………………………..43. Tổng quan về mô phỏng thuật toán ………………………………………….43.1. Khái niệm mô phỏng thuật toán ……………………………………43.2. Lịch sử mô phỏng thuật toán ……………………………………….53.3. Tác dụng của mô phỏng thuật toán trong dạy học………………….63.4. Một số yêu cầu đối với mô phỏng thuật toán ………………………84. Tổng quan về đồ thị ………………………………………………………….84.1. Định nghĩa đồ thị …………………………………………………...94.2. Phân loại đồ thị ……………………………………………………..94.3. Cây khung và cây khung nhỏ nhất …………………………………104.4. Các phương pháp biểu diễn đồ thị ………………………………....105. Phân tích và thiết kế hệ thống mô phỏng thuật toán trên đồ thị …………….115.1. Phân tích hệ thống mô phỏng thuật toán đồ thị…………………….115.1.1. Mục đích……………………………………………………..115.1.2. Đặc điểm …………………………………………………….115.1.3. Kết quả phân tích…………………………………………….125.2. Thiết kế hệ thống mô phỏng thuật toán đồ thị……………………...145.2.1. Màn hình nền hệ thống mô phỏng…………………………...145.2.2. Giao diện chính và chức năng trình mô phỏng ……………..146. Cài đặt mô phỏng thuật toán đồ thị …………………………………………156.1. Công cụ lập trình …………………………………………………..156.2. Cài đặt thuật toán Prim …………………………………………….166.2.1. Bài toán ……………………………………………………..166.2.2. Ý tưởng thuật giải …………………………………………..166.3. Cài đặt các lớp trong chương trình…………………………………176.3.1. Lớp cơ sở …………………………………………………..17Bùi Thị Thuỷ - AK54.CNTT.ĐHSPHN1Báo cáo nghiên cứu khoa họcMô phỏng một số thuật toán đồ thị6.3.2. Lớp Prim ……………………………………………………186.3.3. Lớp Main …………………………………………………...187. Kết luận ……………………………………………………………………188. Hướng phát triển …………………………………………………………..18Tài liệu tham khảoBùi Thị Thuỷ - AK54.CNTT.ĐHSPHN2Báo cáo nghiên cứu khoa họcMô phỏng một số thuật toán đồ thị1. Lý do chọn đề tàiLý 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ềukhó 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ớinhữ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ònglệ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ụngcó 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ónghiể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ứngthú 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ảngdạ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ạytrong nhà trường. Thuật toán về đồ thị chiếm một số lượng khá lớn, tuy nhiên số lượngthuậ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. Caohọ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ậttoá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ứuviệ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ếmtheo 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ánBùi Thị Thuỷ - AK54.CNTT.ĐHSPHN3Báo cáo nghiên cứu khoa họcMô 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ộtdã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ữuhạ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ậttoán thì với một bộ dữ liệu vào chỉ cho duy nhất một kết quả ra.- Tí ...