.c om du on g th an co ng Phần 3: Cấu trúc dữ liệu và Giải thuật cu u Chương 13: Các giải thuật tìm kiếm Chương 12: Các Giải thuật Tìm Kiếm 1 om Các nội dung chính cu u du on g th an co ng .c 1. Giới thiệu 2. Các giải thuật tìm kiếm phần tử 3. Các giải thuật tìm kiếm chuỗi con Chương 12: Các Giải thuật Tìm Kiếm 2 om 1. Giới thiệu ng .c Bài học này sẽ trình bầy một số giải thuật tìm kiếm cho hai bài toán tìm kiếm cơ bản: cu u du on g th an co Thứ nhất, là bài toán tìm một phần tử trong một dãy phần tử cho trước theo một khoá tìm kiếm Thứ hai, là tìm sự xuất hiện của một chuỗi con trong một chuỗi cho trước Chương 12: Các Giải thuật Tìm Kiếm 3 om 1. Giới thiệu cu u du on g th an co ng .c Với bài toán thứ nhất, có hai chiến lược tìm kiếm là tìm kiếm bằng cách so sánh hay tìm kiếm trực tiếp dựa vào giá trị khoá cần tìm Với bài toán thứ hai cũng có nhiều giải thuật khác nhau, từ giải thuật tìm kiếm đơn giản (còn gọi là tìm kiếm thô), cho đến các giải thuật khá phức tạp như của Knuth-Morris-Pratt và của Boyer-Moore Chương 12: Các Giải thuật Tìm Kiếm 4 om 2. Các giải thuật tìm kiếm phần tử .c Đặt bài toán: du on g th an co ng Để đơn giản cho việc trình bầy ý tưởng các giải thuật, ta sẽ chọn bài toán ở dạng đơn giản nhất như sau: Cho một dãy N số A = (a0, a1,…, aN-1) và giá trị cần tìm K (khoá tìm kiếm). Yêu cầu tìm vị trí một phần tử có giá trị bằng K. cu u Có 2 chiến lược tìm kiếm: Tìm kiếm bằng cách so sánh: Tìm kiếm dựa trực tiếp vào giá trị khóa: Chương 12: Các Giải thuật Tìm Kiếm