Luận văn Thạc sĩ Công nghệ thông tin: Tìm hiểu một số giải thuật tìm kiếm chuỗi con và ứng dụng

Nội dung nghiên cứu của đề tài bao gồm 3 chương sau: Chương 1: Tổng quan về tìm kiếm chuỗi con: Nghiên cứu tổng quan về tìm kiếm chuỗi con và ứng dụng của tìm kiếm chuỗi con trong thực tế. Chương 2: Các thuật toán tìm kiếm chuỗi con : Nghiên cứu các thuật toán tìm kiếm chuỗi con kèm theo đánh giá, so sánh giữa các thuật toán tìm kiếm chuỗi con. Chương 3: Kết quả thực nghiệm và ứng dụng tìm kiếm chuỗi con trong xâu gói tin và cài đặt thử nghiệm: Sử dụng các thuật toán tìm kiếm chuỗi con. Từ đó cài đặt thử nghiệm và đánh giá kết quả thuật toán.
Nội dung trích xuất từ tài liệu:
Luận văn Thạc sĩ Công nghệ thông tin: Tìm hiểu một số giải thuật tìm kiếm chuỗi con và ứng dụng ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC CÔNG NGHỆ ĐÀO THỊ DUNGTÌM HIỂU MỘT SỐ GIẢI THUẬT TÌM KIẾM CHUỖI CON VÀ ỨNG DỤNG LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN Hà Nội – 2016 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC CÔNG NGHỆ ĐÀO THỊ DUNG TÌM HIỂU MỘT SỐ GIẢI THUẬT TÌM KIẾM CHUỖI CON VÀ ỨNG DỤNG Ngành: Công nghệ thông tin Chuyên ngành: Hệ thống thông tin Mã số: 60480104 LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TINNGƢỜI HƢỚNG DẪN KHOA HỌC: PGS.TS. NGUYỄN TRÍ THÀNH Hà Nội – 2016 LỜI CẢM ƠN Sau thời gian nghiên cứu, làm việc khẩn trương và được sự hướng dẫn tận tìnhgiúp đỡ của thầy giáo PGS.TS Nguyễn Trí Thành, luận văn với đề tài “ Tìm hiểumột số giải thuật tìm kiếm chuỗi con và ứng dụng” đã được hoàn thành. Tác giả xin bày tỏ lòng biết ơn sâu sắc tới: Thầy giáo hướng dẫn PGS.TS Nguyễn Trí Thành đã tận tình chỉ dẫn, giúp đỡtác giả hoàn thành luận văn. Các thầy cô giáo Trường Đại học công nghệ và một số đồng nghiệp, đã quan tâmđộng viên, giúp đỡ tác giả trong suốt quá trình học tập để hoàn thành luận văn này. Mặc dù đã cố gắng hết sức, song do điều kiện thời gian và kinh nghiệm thực tế củabản thân còn ít, cho nên đề tài không thể tránh khỏi thiếu sót. Vì vậy, tác giả mong nhậnđược sự đóng góp ý kiến của các thầy giáo, cô giáo và các bạn bè đồng nghiệp. Tôi xin chân thành cảm ơn! Hà Nội, ngày 10 tháng 03 năm 2016 Tác giả Đào Thị Dung 1 LỜI CAM ĐOAN Tên tôi là: Đào Thị Dung Sinh ngày 30 tháng 12 năm 1989 Học viên lớp cao học khoá 20 HTTT - Trường đại học công nghệ - ĐHQGHN Hiện đang công tác tại : Trường THPT DTNT Tỉnh Vĩnh Phúc Xin cam đoan luận văn “ Tìm hiểu một số giải thuật tìm kiếm chuỗi con vàứng dụng” do thầy giáo PGS.TS Nguyễn Trí Thành hướng dẫn là công trình nghiêncứu của riêng tôi. Tất cả các tài liệu tham khảo đều có nguồn gốc, xuất xứ rõ ràng. Tác giả xin cam đoan tất cả những nội dung trong luận văn đúng như nội dungtrong đề cương và yêu cầu của thầy giáo hướng dẫn. Nếu có vấn đề gì trong nội dungcủa luận văn tác giả xin hoàn toàn chịu trách nhiệm với lời cam đoan của mình. Hà Nội, ngày 10 tháng 03 năm 2016 Học viên Đào Thị Dung 2 MỤC LỤCLỜI CẢM ƠN ..................................................................................................................1LỜI CAM ĐOAN ............................................................................................................2MỤC LỤC .......................................................................................................................3Danh mục các ký hiệu và chữ viết tắt ..............................................................................5Danh mục các bảng..........................................................................................................6Danh mục hình ảnh ..........................................................................................................7MỞ ĐẦU .........................................................................................................................8CHƢƠNG 1. TỔNG QUAN VỀ TÌM KIẾM CHUỖI CON ........................................13 1.1. Lịch sử về tìm kiếm chuỗi con ......................................................................... 13 1.1.1. Thuật toán trước những năm 2000 ...............................................................13 1.1.2. Thuật toán sau năm 2000 ..............................................................................14 1.2. Tìm kiếm chuỗi con ......................................................................................... 15 1.2.1. Khái niệm về tìm kiếm chuỗi con .................................................................15 1.2.2. Các cách tiếp cận: .........................................................................................16 1.2.3. Các dạng tìm kiếm chuỗi ..............................................................................16 1.2.4. Ứng dụng của tìm kiếm chuỗi ......................................................................20 1.3. ...