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

Bài toán đối sánh mẫu sử dụng giải thuật di truyền

Tác giả: Ngân Hoàng Mỹ Linh

Lĩnh vực: Khoa học máy tính

Nội dung tài liệu:
Luận văn này tập trung nghiên cứu bài toán đối sánh mẫu, một vấn đề quan trọng trong xử lý văn bản và tìm kiếm thông tin. Bài toán này liên quan đến việc tìm kiếm sự xuất hiện của một mẫu (chuỗi ký tự) trong một văn bản lớn hơn. Nghiên cứu cũng đi sâu vào giới thiệu về giải thuật di truyền (GA), một kỹ thuật tối ưu hóa lấy cảm hứng từ quá trình tiến hóa sinh học. Luận văn khám phá cách áp dụng giải thuật di truyền để giải quyết bài toán đối sánh mẫu, bao gồm cả trường hợp xử lý trên một hoặc nhiều file văn bản. Các phương pháp nghiên cứu được áp dụng bao gồm tổng hợp tài liệu lý thuyết, hệ thống hóa kiến thức và lập trình thử nghiệm bằng Visual Studio C# 2012.

Mục lục chi tiết:

MỞ ĐẦU

CHƯƠNG 1 MỘT SỐ THUẬT TOÁN ĐỐI SÁNH MẪU

1.1. Giới thiệu về bài toán đối sánh mẫu

1.2. Phát biểu bài toán

1.3. Một số thuật toán đối sánh mẫu cơ bản

1.3.1. Thuật toán Brute Force

1.3.2. Thuật toán Knuth-Morris-Pratt

1.3.3. Thuật toán Automat hữu hạn

1.3.4. Thuật toán Boyer-Moore

1.3.5. Thuật toán Karp-Rabin

1.3.6. Một số thuật toán khác

CHƯƠNG 2 GIỚI THIỆU VỀ GIẢI THUẬT DI TRUYỀN

2.1. Tổng quan chung về giải thuật di truyền (GA)

2.1.1. Giới thiệu

2.1.2. Các vấn đề cơ bản của GA

2.1.3. Sự khác biệt của GA với các giải thuật khác

2.2. Giải thuật di truyền kinh điển

2.2.1. Giới thiệu

2.2.2. Các toán tử di truyền

2.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

2.2.4. Ví dụ

CHƯƠNG 3 BÀI TOÁN ĐỐI SÁNH MẪU SỬ DỤNG GIẢI THUẬT DI TRUYỀN

3.1. Bài toán đối sánh mẫu trên một file văn bản

3.1.1. Phân tích thuật toán

3.1.2. Các quá trình hoạt động của chương trình

3.1.3. Kết quả và đánh giá

3.2. Bài toán đối sánh mẫu trên nhiều file văn bản

3.2.1. Phát biểu bài toán

3.2.2. Kết quả thử nghiệm

KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN

*) Kết luận

*) Hướng nghiên cứu phát triển

TÀI LIỆU THAM KHẢO

DANH MỤC THUẬT NGỮ, TỪ VIẾT TẮT, KÍ HIỆU

DANH MỤC CÁC HÌNH VẼ

DANH MỤC BẢNG BIỂU