tailieunhanh - Phương pháp lắc balô và thuật toán xấp xỉ dây con chung dài nhất.

Phương pháp lắc balô và thuật toán xấp xỉ dây con chung dài nhất. Như vậy, Điều khiển học trở thành một thành phần căn bản của khoa học về các hệ thống (Systems Sciences), là tập hợp nhiều lĩnh vực nghiên cứu nhằm khảo sát các thuộc tính chung của sự phức tạp, sự phát triển của các hệ thống. Những thuộc tính ấy biểu lộ trong những hệ tiến hóa, hệ thích nghi phức tạp và sự sống nhân tạo | Tạp chí Tin học và Điều khiền học T. 19 s. 1 2003 5--16 PHƯƠNG PHÁP LẮC BA LÔ VÀ THUẬT TOÁN TÌM KIẾM XẤP XÍ DÃY CON CHUNG DÀI NHAT NGUYỄN QUÝ KHANG Khoa Toán trường -Đại Học Sư phạm Hà nội 2 Abstract. In a paper entitled Fuzzy Automata and it s applications for finding the longest common subsequence and - The 6-th Vietnam Conference of Mathematics Hue-7-10 9 2002 using a weakly ordered structure we have introduced Knapsack Shaking Method as fundamentals of application of fuzzy automata for finding the exactly longest common subsequence of two text sequences. In this paper received results will be extended to solve approximate LCS problems using the Knapsack Shaking method. Some new algorithms with their complexities are presented. Tóm tắt. Trong báo cáo Ôtômát mờ và ứng dụng trong bài toán tìm dãy con chung dài nhất và Hội nghị Toán học Toàn quốc lần 6 Huế 7-10 9 2002 chúng tôi đã dề xuất phương pháp lắc ba lô nhờ việc xây dựng một cấu trúc thứ tự yếu làm cơ sở cho việc áp dụng ôtômát mờ để giải bài toán tìm chính xác dãy con chung dài nhất của hai xâu text. Bài báo này mở rộng các kết quả toán học đó và trình bày một số thuật toán ứng dụng phương pháp lắc ba lô vào việc giải bài toán tìm kiếm xấp xỉ dãy con chung dài nhất của hai xâu và xem xét độ phức tạp tính toán của chúng. 1. MỞ ĐẦU Bài toán so mẫu kiểu xâu ký tự xuất hiện trong nhiều lĩnh vực nghiên cứu chẳng hạn việc tìm kiếm thông tin tĩnh hoặc động trên mạng. Mọi hệ soạn thảo văn bản ha y đa số bộ soạn thảo của ngôn ngữ lập trình không the thiếu lệnh tìm kiếm trong sinh học nghiên cứu các bản đồ gene đe phát hiện những thuộc tính cần quan tâm đối với cây trồng hoặc cơ the sống. Tìm kiếm so mẫu cũng cần thiết trong viln thám. Hiện nay việc xây dựng thuật toán mới hoặc cải tiến các thuật toán so mẫu chính xác hay xấp xỉ đang là một vấn đề sôi động. Các thuật toán so đơn và đa mẫu chính xác hay xấp xỉ đã đươc trình bày trong các công trình 1 3 4 5 9 Trong các dạng của bài .