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