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

- Mô phỏng một số thuật toán trên đồ thị.
- Abstract: Những kiến thức cơ bản về thuật toán: nêu khái niệm về bài toán và thuật toán, các tính chất của thuật toán, xác định độ phức tạp của thuật toán,… và giới thiệu ba thuật toán quan trọng trên đồ thị mà học sinh Trung học phổ thông (THPT) sẽ được học.
- Mô phỏng thuật toán:.
- trình bày khái niệm mô phỏng, các chức năng của mô phỏng và các vấn đề liên quan như lịch sử mô phỏng, nghiên cứu về hiệu quả của nó trong giảng dạy và một số yêu cầu đối với việc mô phỏng thuật toán nói chung.
- Phân tích thiết kế hệ thống mô phỏng một số thuật toán trên đồ thị:.
- trình bày về quá trình phân tích, thiết kế và xây dựng hệ thống mô phỏng trên ba thuật toán: thuật toán tìm kiếm (tìm kiếm theo chiều sâu và tìm kiếm theo chiều rộng), thuật toán tìm đường đi ngắn nhất (thuật toán Dijsktra) và thuật toán tìm cây khung cực tiểu trên đồ thị vô hướng có trọng số (thuật toán Prim)….
- Thuật toán.
- Đồ thị.
- Mô phỏng thuật toán..
- Cách đây gần ba thập kỉ (khoảng những năm 80 của thế kỉ XX), ở nhiều nước trên thế giới mô phỏng thuật toán đã được sử dụng trong việc giảng dạy các môn Khoa học máy tính như một công cụ hữu hiệu để mô tả thuật toán một cách trực quan, khoa học.
- Không những vậy nó còn cho người học biết chi tiết từng bước hoạt động của thuật toán cùng với cấu trúc dữ liệu đi kèm thông qua việc mô tả bằng đồ họa..
- tươ ̣ng: stack, queue, cây, cây nhi ̣ phân, cây nhi ̣ phân tìm kiếm, các chiến lược thiết kế thuật toán:.
- Hiện nay, việc truyền đạt các thuật toán trên đồ thị cho học sinh chuyên Tin gặp rất nhiều khó khăn.
- Có nhiều rất nhiều lý do: Các thuật toán đó khó hình dung, việc tổ chức dữ liệu cho nó cũng phức tạp, thời gian giảng dạy trên lớp có hạn, tài liệu tham khảo có thể tự đọc, tự học vẫn còn ít…..
- Trong khuôn khổ đề tài này, chúng tôi xây dựng một chương trình nhằm mô phỏng hoạt động của ba thuật toán giải ba bài toán cơ bản trên đồ thị theo phân phối chương trình của Bộ Giáo dục với hai mục đích: để học sinh có thể dễ dàng nắm bắt tư tưởng cũng như từng bước hoạt động cụ thể của các thuật toán, để giáo viên có thể làm cho bài giảng về các thuật toán này trở nên dễ hiểu, dễ tiếp thu hơn..
- Những kiến thức cơ bản về thuật toán..
- Ở chương này, chúng tôi trích nêu khái niệm về bài toán và thuật toán.
- Các tính chất của thuật toán, xác định độ phức tạp của thuật toán…Cuối cùng, chúng tôi giới thiệu ba thuật toán quan trọng trên đồ thị mà học sinh THPT sẽ được học..
- Chương này chúng tôi trình bày khái niệm mô phỏng, các chức năng của mô phỏng và các vấn đề liên quan như: lịch sử mô phỏng, nghiên cứu về hiệu quả của nó trong giảng dạy và một số yêu cầu đối với việc mô phỏng thuật toán nói chung..
- Phân tích thiết kế hệ thống mô phỏng một số thuật toán trên đồ thị..
- Ở chương 3, chúng tôi trình bày về quá trình phân tích, thiết kế và xây dựng hệ thống mô phỏng trên ba thuật toán: thuật toán tìm kiếm (tìm kiếm theo chiều sâu và tìm kiếm theo chiều rộng), thuật toán tìm đường đi ngắn nhất (thuật toán Dijsktra) và thuật toán tìm cây khung cực tiểu trên đồ thị vô hướng có trọng số (thuật toán Prim)….
- Leiserson Ronald Rivest – Giáo trình thuật toán - Nhà xuất bản thống kê.