LUẬN VĂN: MÔ PHỎNG MỘT SỐ THUẬT TOÁN TRÊN ĐỒ THỊ

Nội dung luận văn được chia thành 3 chương:Chương I. 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.
Nội dung trích xuất từ tài liệu:
LUẬN VĂN:MÔ PHỎNG MỘT SỐ THUẬT TOÁN TRÊN ĐỒ THỊ ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ NGUYỄN THỊ CHINHMÔ PHỎNG MỘT SỐ THUẬT TOÁN TRÊN ĐỒ THỊ LUẬN VĂN THẠC SĨ Hà Nội - 2011 Trang 3 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ NGUYỄN THỊ CHINHMÔ PHỎNG MỘT SỐ THUẬT TOÁN TRÊN ĐỒ THỊ Ngành: Công nghệ thông tin Chuyên ngành: Hệ thống thông tin Mã số: 60 48 05 LUẬN VĂN THẠC SĨ NGƯỜI HƯỚNG DẪN KHOA HỌC: TS. HỒ CẨM HÀ Hà Nội - 2011 Trang 4 LỜI CAM ĐOAN Tôi xin cam đoan, kết quả luận văn hoàn toàn là kết quả của tự bản thântôi tìm hiểu, nghiên cứu dưới sự hướng dẫn của TS. Hồ Cẩm Hà. Các tài liệu tham khảo được trích dẫn và chú thích đầy đủ. Học viên Nguyễn Thị Chinh Trang 5 LỜI CẢM ƠN Trước hết, tôi muốn gửi lời cảm đến các Thầy, Cô trong khoa Công nghệthông tin- Trường Đại học Công nghệ - Đại học Quốc gia Hà nội đã truyền đạtcác kiến thức quý báu cho tôi trong suốt thời gian học tập tại trường. Đặc biệt,tôi xin gửi lời cảm ơn sâu sắc tới cô giáo hướng dẫn TS Hồ Cẩm Hà, người đãtận tình chỉ bảo và hướng dẫn về mặt chuyên môn cho tôi trong suốt quá trìnhthực hiện luận văn này. Cũng qua đây, tôi xin gửi lời cảm ơn đến Ban Giám hiệu trường THPTChuyên Đại học Sư phạm Hà Nội, nơi tôi đang công tác đã tạo mọi điều kiệnthuận lợi cho tôi trong thời gian học tập cũng như trong suốt quá trình thựchiện luận văn tốt nghiệp. Cuối cùng, tôi xin cảm ơn gia đình, bạn bè, đồng nghiệp đã luôn ủng hộ,động viên tôi rất nhiều để tôi yên tâm nghiên cứu và hoàn thành luận văn. Trongsuốt quá trình làm luận văn, bản thân tôi đã cố gắng tập trung tìm hiểu, nghiêncứu và tham khảo thêm nhiều tài liệu liên quan. Tuy nhiên, do thời gian hạn chếvà bản thân còn chưa có nhiều kinh nghiệm trong nghiên cứu khoa học, chắcchắn bản luận văn vẫn còn nhiều thiếu sót. Tôi rất mong được nhận sự chỉ bảocủa các Thầy Cô giáo và các góp ý của bạn bè, đồng nghiệp để luận văn đượchoàn thiện hơn. Hà Nội, ngày 12 tháng 06 năm 2011 Nguyễn Thị Chinh Trang 6MỤC LỤCLỜI CẢM ƠN ................................................................................................... 6LỜI NÓI ĐẦU ................................................................................................. 10Chươ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 ...