Tiểu luận: PHƯƠNG PHÁP BƯỚC ĐI NGẪU NHIÊN TRONG GIẢI QUYẾT CÁC BÀI TOÁN TIN HỌC

Ngày nay, sức mạnh máy tính đã có những bước phát triển vượt trội giúp con người đạt được nhiều thành tựu trong các lĩnh vực của cuộc sống. Sức mạnh tính toán của máy tính được phát triển dựa trên những thành tựu của khoa học – kỹ thuật để ngày càng thu nhỏ hơn và tích hợp nhiều hơn những bóng bán dẫn trên cùng một bộ vi xử lý để tăng khả năng xử lý.
Nội dung trích xuất từ tài liệu:
Tiểu luận:PHƯƠNG PHÁP BƯỚC ĐI NGẪU NHIÊN TRONG GIẢI QUYẾT CÁC BÀI TOÁN TIN HỌC ĐẠI HỌC QUỐC GIA TP. HỒ CHÍ MINH TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN -----------------------------------------------------PHƯƠNG PHÁP NGHIÊN CỨU KHOA HỌC TRONG TIN HỌC PHƯƠNG PHÁP BƯỚC ĐI NGẪU NHIÊN TRONG GIẢI QUYẾT CÁC BÀI TOÁN TIN HỌC Trang 1 Mục lục trang1. Đặt vấn đề ............................................................................................................... 22. Các thuật toán dựa trên phương pháp “bước đi ngẫu nhiên” ............................. 3 2.1 Thuật giải áp dụng trên đồ thị ............................................................................ 3 2.1.1 Thuật giải gom cụm Markov Cluster.............................................................. 3 2.1.2 Thuật giải đánh giá liên kết HITS .................................................................. 7 2.2 Thuật giải tối ưu hóa mô phỏng hành vi đàn kiến ............................................. 103. Áp dụng thực tiễn từ các thuật giải ..................................................................... 124. Kết luận ................................................................................................................ 14Tài liệu tham khảo.............................................................................................. 15Phụ lục..................................................................................................................... 16Chương trình minh họa................................................................................................ 16 Trang 2 1. Đặt vấn đề Ngày nay, sức mạnh máy tính đã có những bước phát triển vượt trội giúp con ngườiđạt được nhiều thành tựu trong các lĩnh vực của cuộc sống. Sức mạnh tính toán của máytính được phát triển dựa trên những thành tựu của khoa học – kỹ thuật để ngày càng thunhỏ hơn và tích hợp nhiều hơn những bóng bán dẫn trên cùng một bộ vi xử lý để tăng khảnăng xử lý. Nhiều năm qua, tốc độ phát triển tính toán của máy tính đều tuân theo địnhluật Moore với nội dung là sau mỗi 2 năm tốc độ tính toán máy tính lại tăng gấp đôi. Tuytốc độ tính toán đã những bước phát triển vượt bậc nhưng những công việc của máy tínhthực hiện về tác vụ chính chỉ ràng buộc trong một số thao tác cơ bản như lưu trữ, tìmkiếm và cập nhật thông tin. Và để giải quyết một vấn đề nào đó trong cuộc sống, máytính vẫn phải dựa trên các phương pháp giải quyết của con người, để nhằm được cungcấp cho máy tính những phương thức và quá trình giải quyết vấn đề đó. Quá trình giải quyết các vấn đề trong cuộc sống của con người ít bị thay đổi theo thờigian. Nó là một sự mở rộng và hoàn thiện các phương pháp nhưng tất cả đều tựu chungtheo một phương pháp tổng quan nhất: - Quan sát và tập hợp các sự kiện ở trong quá khứ và hiện tại. - Bổ sung, kết hợp và biến đổi những sự kiện trước đó. - Kiểm tra và đánh giá những kết quả đạt được. - Ghi nhận, xử lý các kết quả (kết quả đúng và sai) và đưa ra hướng giải quyết mới. - Quay lại bước quan sát – tập hợp và lặp lại quá trình giải quyết như vậy. Quá trình như vậy được lặp lại cho đến khi đạt được kết quả mong muốn. Kết quảmong muốn ở đây có thể là một kết quả không cần đúng hoàn toàn, chỉ cần kết quả đúngmột phần trong một giới hạn cho phép. Ví dụ các lý thuyết trong vật lý và kinh tế, nóđược dẫn giải và giải thích đúng một số hiện tượng nhưng các lý thuyết đó vẫn chưa thểđược chứng minh đúng hoàn toàn như thuyết tương đối, thuyết thị trường hiệu quả…Riêng đối tin học, các giải pháp đưa ra cho một vấn đề đôi khi không thể giải quyết đểthỏa mãn cùng lúc tất cả các yêu cầu của vấn đề. Đôi khi, phải sử dụng các phương phápgián tiếp với kết quả trả về được chấp nhận theo các điều kiện nào đó. Ví dụ: tìm kiếmtrên Google không dựa trên ngữ nghĩa mà dựa trên tìm kiếm theo từ khóa và đánh giá nộidung theo các link các trang web bên trong nhưng vẫn cung cấp được các kết quả tìmkiếm tương đối chính xác với nội dung tìm kiếm của người dùng. Trang 3 Như vậy, việc kết hợp sức mạnh của máy tính về tính toán, lưu trữ với phương phápgiải quyết các vấn đề một cách tổng quan của con người có thể được áp dụng cho nhiềulĩnh vực khác nhau trong cuộc sống với hiệu quả cao hơn, giải quyết được nhiều vấn đềhơn. Hiện nay, khi các giải pháp tin học đã được áp dụng rộng rã ...