Luận văn Thạc sĩ Khoa học máy tính: Bài toán đối sánh mẫu sử dụng giải thuật di truyền

Đề tài “Bài toán đối sánh mẫu sử dụng giải thuật di truyền” nhằm mục đích nghiên cứu bài toán đối sánh mẫu, giải thuật di truyền và ứng dụng của giải thuật di truyền trong đối sánh mẫu và tìm kiếm văn bản. Để hiểu rõ hơn mời các bạn cùng tham khảo nội dung chi tiết của luận văn này.
Nội dung trích xuất từ tài liệu:
Luận văn Thạc sĩ Khoa học máy tính: Bài toán đối sánh mẫu sử dụng giải thuật di truyền ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC CNTT VÀ TRUYỀN THÔNG NGÂN HOÀNG MỸ LINH BÀI TOÁN ĐỐI SÁNH MẪU SỬ DỤNG GIẢI THUẬT DI TRUYỀN LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH THÁI NGUYÊN - 2015Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC CNTT VÀ TRUYỀN THÔNG NGÂN HOÀNG MỸ LINH BÀI TOÁN ĐỐI SÁNH MẪU SỬ DỤNG GIẢI THUẬT DI TRUYỀN Chuyên ngành: KHOA HỌC MÁY TÍNH Mã số: 60 48 01 01 LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH Người hướng dẫn khoa học: TS. VŨ MẠNH XUÂN THÁI NGUYÊN - 2015Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn i LỜI CAM ĐOAN Tôi xin cam đoan luận văn này của tự bản thân tôi tìm hiểu, nghiên cứu dướisự hướng dẫn của TS Vũ Mạnh Xuân. Các chương trình thực nghiệm do chính bảnthân tôi lập trình, các kết quả là hoàn toàn trung thực. Các tài liệu tham khảo đượctrích dẫn và chú thích đầy đủ. TÁC GIẢ LUẬN VĂN Ngân Hoàng Mỹ LinhSố hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn ii LỜI CẢM ƠN Tôi xin bày tỏ lời cảm ơn chân thành tới tập thể các thầy cô giáo Viện côngnghệ thông tin – Viện Hàn lâm Khoa học và Công nghệ Việt Nam, các thầy cô giáoTrường Đại học Công nghệ thông tin và truyền thông - Đại học Thái Nguyên đã dạydỗ chúng tôi trong suốt quá trình học tập chương trình cao học tại trường. Đặc biệt tôi xin bày tỏ lòng biết ơn sâu sắc tới thầy giáo TS Vũ Mạnh Xuânđã quan tâm, định hướng và đưa ra những góp ý, gợi ý, chỉnh sửa quý báu cho tôitrong quá trình làm luận văn tốt nghiệp. Cuối cùng, tôi xin chân thành cảm ơn các bạn bè đồng nghiệp, gia đình vàngười thân đã quan tâm, giúp đỡ và chia sẻ với tôi trong suốt quá trình làm luận văntốt nghiệp. Thái Nguyên, tháng 08 năm 2015 Ngân Hoàng Mỹ LinhSố hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn iii MỤC LỤCMỞ ĐẦU .....................................................................................................................1CHƢƠNG 1 MỘT SỐ THUẬT TOÁN ĐỐI SÁNH MẪU .......................................31.1. Giới thiệu về bài toán đối sánh mẫu.....................................................................31.2. Phát biểu bài toán .................................................................................................31.3. Một số thuật toán đối sánh mẫu cơ bản................................................................41.3.1. Thuật toán Brute Force......................................................................................41.3.2. Thuật toán Knuth-Morris-Pratt .........................................................................41.3.3. Thuật toán Automat hữu hạn.............................................................................51.3.4. Thuật toán Boyer-Moore ...................................................................................71.3.5. Thuật toán Karp-Rabin ....................................................................................101.3.6. Một số thuật toán khác ....................................................................................11CHƢƠNG 2 GIỚI THIỆU VỀ GIẢI THUẬT DI TRUYỀN ...................................132.1. Tổng quan chung về giải thuật di truyền (GA) ..................................................132.1.1. Giới thiệu .........................................................................................................132.1.2. Các vấn đề cơ bản của GA ..............................................................................152.1.3. Sự khác biệt của GA với các giải thuật khác ..................................................182.2. Giải thuật di truyền kinh điển.............................................................................202.2.1. Giới thiệu .........................................................................................................202.2.2. Các toán tử di truyền .......................................................................................212.2.3. Các bước quan trọng trong việc áp dụng giải thuật di truyền kinh điển. ........262.2.4. Ví dụ ................................................................................................................27CHƢƠNG 3 BÀI TOÁN ĐỐI SÁNH MẪU SỬ DỤNG GIẢI THUẬT DITRUYỀN ...................................................................................................................303.1. Bài toán đối sánh mẫu trên một file văn bản......................................................303.1.1. Phân tích thuật toán .........................................................................................313.1.2. Các quá trình hoạt động của chương trình ......................................................363.1.3. Kết quả và đánh giá .........................................................................................403.2. Bài toán đối sánh mẫu trên nhiều file văn bản ...................................................55Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu. ...