Tải miễn phí Mô phỏng một số thuật toán trên đồ thị
MỤC LỤC
LỜI CẢM ƠN................................................................................................... 6
LỜI NÓI ĐẦU................................................................................................. 10
Chương 1 MỘT SỐ KIẾN THỨC CƠ BẢN VỀ THUẬT TOÁN .................... 12
1. Khái niệm bài toán Tin học ....................................................................... 12
2. Khái niệm thuật toán................................................................................. 12
3. Các tính chất của thuật toán ...................................................................... 13
4. Độ phức tạp và xác định độ phức tạp của thuật toán.................................. 14
5. Chi phí thực hiện thuật toán ...................................................................... 18
6. Ba bài toán trên mô hình đồ thị được đưa vào giảng dạy trong trường Trung
học Phổ thông Chuyên.................................................................................. 18
6.1. Một số khái niệm cơ bản về đồ thị ...................................................... 18
6.1.1. Khái niệm đồ thị (Graph).............................................................. 18
6.1.2. Các khái niệm cơ bản ................................................................... 19
6.2. Bài toán tìm kiếm trên đồ thị .............................................................. 21
6.2.1. Phát biểu bài toán ......................................................................... 21
6.2.2. Giới thiệu thuật toán tìm kiếm DFS và BFS ................................. 22
6.2.3. Độ phức tạp tính toán của thuật toán DFS và BFS........................ 24
6.3. Bài toán tìm đường đi ngắn nhất trên đồ thị có trọng số...................... 24
6.3.1. Phát biểu bài toán ......................................................................... 24
6.3.2. Giới thiệu thuật toán Ford - Bellman ............................................ 25
6.2.3. Giới thiệu thuật toán thuật toán Dijkstra ....................................... 26
6.3.4. Độ phức tạp.................................................................................. 28
6.4. Các thuật toán tìm kiếm trên cây khung.............................................. 28
6.4.1. Bài toán cây khung ....................................................................... 28
6.4.2. Giới thiệu thuật toán Prim ............................................................ 29
6.4.3. Giới thiệu thuật toán Kruskal........................................................ 30
6.4.5. Độ phức tạp ................................................................................. 31
6.5. Bài toán tìm chu trình Hamilton qua tất cả các đỉnh của đồ thị ........... 32
6.5.1. Phát biểu bài toán ......................................................................... 32
6.5.2. Giới thiệu thuật toán tìm chu trình Hamilton: ............................... 33
Chương 2 MÔ PHỎNG THUẬT TOÁN.......................................................... 34
1. Khái niệm và chức năng của mô phỏng..................................................... 34
2. Lịch sử của mô phỏng thuật toán............................................................... 35
3. Hiệu quả của mô phỏng thuật toán trong giảng dạy................................... 37
4. Một số yêu cầu đối với mô phỏng thuật toán............................................. 41
4.1. Mô phỏng đúng theo thuật toán .......................................................... 41
4.2. Cho phép thực hiện theo từng bước .................................................... 41
4.3. Mô phỏng thuật toán phải có tính động............................................... 41
4.4. Có thể thực thi với mọi bộ dữ liệu đầu vào ......................................... 43
4.5. Có sự phân cấp người học................................................................... 43
5. Quy trình mô phỏng thuật toán.................................................................. 43
5.1. Nghiên cứu và phân tích giải thuật...................................................... 43
5.2. Mô phỏng dữ liệu vào và kết quả đầu ra ............................................. 44
5.3. Chia thuật toán thành nhiều bước nhỏ rồi mô phỏng theo từng bước .. 45
5.4. Tổng hợp mô phỏng theo các bước ..................................................... 47
5.5. Sơ đồ cấu trúc chung của hệ thống mô phỏng ..................................... 47
6. Đề xuất lựa chọn công cụ để phát triển chương trình mô phỏng thuật toán 48
6.1. Một số hệ thống mô phỏng thuật toán chung ...................................... 49
6.2. Sử dụng công cụ mô phỏng thuật toán riêng biệt ................................ 52
6.3. Xây dựng hệ thống từ đầu................................................................... 53
Chương 3 PHÂN TÍCH THIẾT KẾ HỆ THỐNG MÔ PHỎNG MỘT SỐ
THUẬT TOÁN TRÊN ĐỒ THỊ....................................................................... 54
1. Mục đích................................................................................................... 54
2. Những yêu cầu thực tế .............................................................................. 54
3. Đề xuất cho hệ thống mới ......................................................................... 55
4. Thiết kế hệ thống mô phỏng một số thuật toán trên đồ thị ......................... 56
4.1. Lựa chọn công cụ lập trình ................................................................. 57
4.2. Chức năng mô phỏng của các thuật toán được cài đặt ......................... 59
4.2.1 Mô phỏng thuật toán tìm kiếm....................................................... 59
4.2.2. Mô phỏng thuật toán Dijkstra ....................................................... 61
4.2.3. Mô phỏng thuật toán Ford – Bellman ........................................... 63
4.2.4. Mô phỏng thuật toán Prim............................................................ 63
4.2.5. Mô phỏng thuật toán Kruskal ....................................................... 65
4.2.6. Thuật toán tìm chu trình Hamilton................................................ 66
5. Giới thiệu chương trình............................................................................. 66
5.1. Tổng quan về hệ thống........................................................................ 66
5.1.1. Các đối tượng xây dựng cấu trúc đồ thị ........................................ 67
5.1.2. Công cụ vẽ hình ảnh để mô phỏng................................................ 70
5.1.3.Chức năng chi tiết của các công cụ hỗ trợ cho quá trình mô phỏng 70
5.2. Giới thiệu các công cụ hỗ trợ mô phỏng do người dùng cài đặt .......... 71
Chương 4 KẾT LUẬN..................................................................................... 80
1. Những kết quả đạt được ............................................................................ 80
2. Hướng phát triển....................................................................................... 81
DANH MỤC TÀI LIỆU THAM KHẢO.......................................................... 82
PHỤ LỤC ........................................................................................................ 84
Link download miễn phí cho ae:
MỤC LỤC
LỜI CẢM ƠN................................................................................................... 6
LỜI NÓI ĐẦU................................................................................................. 10
Chương 1 MỘT SỐ KIẾN THỨC CƠ BẢN VỀ THUẬT TOÁN .................... 12
1. Khái niệm bài toán Tin học ....................................................................... 12
2. Khái niệm thuật toán................................................................................. 12
3. Các tính chất của thuật toán ...................................................................... 13
4. Độ phức tạp và xác định độ phức tạp của thuật toán.................................. 14
5. Chi phí thực hiện thuật toán ...................................................................... 18
6. Ba bài toán trên mô hình đồ thị được đưa vào giảng dạy trong trường Trung
học Phổ thông Chuyên.................................................................................. 18
6.1. Một số khái niệm cơ bản về đồ thị ...................................................... 18
6.1.1. Khái niệm đồ thị (Graph).............................................................. 18
6.1.2. Các khái niệm cơ bản ................................................................... 19
6.2. Bài toán tìm kiếm trên đồ thị .............................................................. 21
6.2.1. Phát biểu bài toán ......................................................................... 21
6.2.2. Giới thiệu thuật toán tìm kiếm DFS và BFS ................................. 22
6.2.3. Độ phức tạp tính toán của thuật toán DFS và BFS........................ 24
6.3. Bài toán tìm đường đi ngắn nhất trên đồ thị có trọng số...................... 24
6.3.1. Phát biểu bài toán ......................................................................... 24
6.3.2. Giới thiệu thuật toán Ford - Bellman ............................................ 25
6.2.3. Giới thiệu thuật toán thuật toán Dijkstra ....................................... 26
6.3.4. Độ phức tạp.................................................................................. 28
6.4. Các thuật toán tìm kiếm trên cây khung.............................................. 28
6.4.1. Bài toán cây khung ....................................................................... 28
6.4.2. Giới thiệu thuật toán Prim ............................................................ 29
6.4.3. Giới thiệu thuật toán Kruskal........................................................ 30
6.4.5. Độ phức tạp ................................................................................. 31
6.5. Bài toán tìm chu trình Hamilton qua tất cả các đỉnh của đồ thị ........... 32
6.5.1. Phát biểu bài toán ......................................................................... 32
6.5.2. Giới thiệu thuật toán tìm chu trình Hamilton: ............................... 33
Chương 2 MÔ PHỎNG THUẬT TOÁN.......................................................... 34
1. Khái niệm và chức năng của mô phỏng..................................................... 34
2. Lịch sử của mô phỏng thuật toán............................................................... 35
3. Hiệu quả của mô phỏng thuật toán trong giảng dạy................................... 37
4. Một số yêu cầu đối với mô phỏng thuật toán............................................. 41
4.1. Mô phỏng đúng theo thuật toán .......................................................... 41
4.2. Cho phép thực hiện theo từng bước .................................................... 41
4.3. Mô phỏng thuật toán phải có tính động............................................... 41
4.4. Có thể thực thi với mọi bộ dữ liệu đầu vào ......................................... 43
4.5. Có sự phân cấp người học................................................................... 43
5. Quy trình mô phỏng thuật toán.................................................................. 43
5.1. Nghiên cứu và phân tích giải thuật...................................................... 43
5.2. Mô phỏng dữ liệu vào và kết quả đầu ra ............................................. 44
5.3. Chia thuật toán thành nhiều bước nhỏ rồi mô phỏng theo từng bước .. 45
5.4. Tổng hợp mô phỏng theo các bước ..................................................... 47
5.5. Sơ đồ cấu trúc chung của hệ thống mô phỏng ..................................... 47
6. Đề xuất lựa chọn công cụ để phát triển chương trình mô phỏng thuật toán 48
6.1. Một số hệ thống mô phỏng thuật toán chung ...................................... 49
6.2. Sử dụng công cụ mô phỏng thuật toán riêng biệt ................................ 52
6.3. Xây dựng hệ thống từ đầu................................................................... 53
Chương 3 PHÂN TÍCH THIẾT KẾ HỆ THỐNG MÔ PHỎNG MỘT SỐ
THUẬT TOÁN TRÊN ĐỒ THỊ....................................................................... 54
1. Mục đích................................................................................................... 54
2. Những yêu cầu thực tế .............................................................................. 54
3. Đề xuất cho hệ thống mới ......................................................................... 55
4. Thiết kế hệ thống mô phỏng một số thuật toán trên đồ thị ......................... 56
4.1. Lựa chọn công cụ lập trình ................................................................. 57
4.2. Chức năng mô phỏng của các thuật toán được cài đặt ......................... 59
4.2.1 Mô phỏng thuật toán tìm kiếm....................................................... 59
4.2.2. Mô phỏng thuật toán Dijkstra ....................................................... 61
4.2.3. Mô phỏng thuật toán Ford – Bellman ........................................... 63
4.2.4. Mô phỏng thuật toán Prim............................................................ 63
4.2.5. Mô phỏng thuật toán Kruskal ....................................................... 65
4.2.6. Thuật toán tìm chu trình Hamilton................................................ 66
5. Giới thiệu chương trình............................................................................. 66
5.1. Tổng quan về hệ thống........................................................................ 66
5.1.1. Các đối tượng xây dựng cấu trúc đồ thị ........................................ 67
5.1.2. Công cụ vẽ hình ảnh để mô phỏng................................................ 70
5.1.3.Chức năng chi tiết của các công cụ hỗ trợ cho quá trình mô phỏng 70
5.2. Giới thiệu các công cụ hỗ trợ mô phỏng do người dùng cài đặt .......... 71
Chương 4 KẾT LUẬN..................................................................................... 80
1. Những kết quả đạt được ............................................................................ 80
2. Hướng phát triển....................................................................................... 81
DANH MỤC TÀI LIỆU THAM KHẢO.......................................................... 82
PHỤ LỤC ........................................................................................................ 84
Link download miễn phí cho ae:
You must be registered for see links