Thuật toán Brute Force ppsx

I. Mở đầu

1. Giới thiệu chung

Dữ liệu trong máy tính được lưu trữ dưới rất nhiều dạng khác

nhau, nhưng sử dụng chuỗi vẫn là một trong những cách rất phổ

biến. Trên chuỗi các đơn vị dữ liệu không có ý nghĩa quan trọng

bằng cách sắp xếp của chúng. Ta có thể thấy các dạng khác nhau

của chuỗi như ở các file dữ liệu, trên biểu diễn của các gen, hay

chính văn bản chúng ta đang đọc.

Chuỗi ký tự là một dãy gồm các ký tự hoặc một mảng các ký tự

được kết thúc bằng ký tự '\0' (còn được gọi là ký tự NULL trong

bảng mã Ascii).

Các hằng chuỗi ký tự được đặt trong cặp dấu nháy kép “ ”

2. Đặt vấn đề

Trong thực tế chúng ta thường gặp phải một số vấn đề đơn giản

như: tìm kiếm một chuỗi con nhỏ trong một đoạn văn bản lớn hơn.

Đặc biệt trong microsoft word, việc tìm kiếm một chuỗi con nhằm để

thay thế (replace) hoặc xóa đi (delete) rất phổ biến. Tuy nhiên, do

yêu cầu về kích thước, chúng ta thường không thể tự làm điều này

bằng tay được. do đó sẽ có một số công cụ hổ trợ được cài đặt sẵn

trong máy tính (hoặc đính kèm trong các chương trình có liên quan).

Xuất phát từ yêu cầu trên, nhiều thuật toán tìm kiếm chuỗi đã ra

đời và nâng cao về tính ưa việt :

 Brute force

 Knuth-Morris-Pratt

 Deterministic Finite Automaton (máy automat hữu hạn)

 Boyer-Moore

 Karp-Rabin

v.v…..

ta có thể phát biểu thành bài toán như sau: