Electronics and Computer Engineering
School of Electronics and Telecommunications
Hanoi University of Science and Technology
1 Dai Co Viet - Hanoi - Vietnam
Data structure and Algorithms
Searching – Giải thuật tìm kiếm
Data structure and Algorithms
Searching – Giải thuật tìm kiếm
Thanh-Hai Tran
2020 2
Nội dung bài học
Giới thiệu chung về các thuật toán tìm kiếm
Các giải thuật tìm kiếm phần tử
Tìm kiếm dựa vào so sánh (gián tiếp)
Tìm kiếm dựa vào giá trị khóa (trực tiếp)
Các giải thuật tìm kiếm chuỗi con
Giải thuật tìm kiếm thô (brute-force)
Giải thuật Knuth-Morris-Pratt (KMP)
Bài tập
Tài liệu tham khảo
2020 3
Nội dung bài học
Giới thiệu chung về các thuật toán tìm kiếm
Các giải thuật tìm kiếm phần tử
Tìm kiếm dựa vào so sánh (gián tiếp)
Tìm kiếm dựa vào giá trị khóa (trực tiếp)
Các giải thuật tìm kiếm chuỗi con
Giải thuật tìm kiếm thô (brute-force)
Giải thuật Knuth-Morris-Pratt (KMP)
Bài tập
Tài liệu tham khảo
2020 4
Giới thiệu chung
Tìm kiếm: là thuật toán tìm 1 phần tử có giá trị cho
trước trong một tập các phần tử
Khóa tìm kiếm: Một bộ phận của các phần tử trong
tập mà giá trị của nó được sử dụng để so sánh và
tìm kiếm
2020 5
Giới thiệu chung
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:
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
Tìm kiếm bằng cách so sánh
Tìm kiếm trực tiếp dựa vào giá trị khoá
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
Giải thuật tìm kiếm đơn giản (còn gọi là tìm kiếm thô)
Các giải thuật khá phức tạp như của Knuth-Morris-
Pratt và của Boyer-Moore