Bài thuyết trình Trí tuệ nhân tạo - Chủ đề: Thuật toán Karp-Rabin - Trần Thị Hạnh
Giảng viên hướng dẫn : TS. Từ Minh Phương
Lớp: Hệ thống thông tin
Nhóm 3:
Trần Thị Hạnh
Mẫn Hồng Dương
Dương Văn Đoàn
Nội dung
Giới thiệu thuật toán Karp-Rabin
Ý tưởng thuật toán Karp-Rabin
Giải thuật thuật toán
Mã hóa thuật toán
Độ phức tạp của thuật toán
Kiểm nghiệm thuật toán
Giới thiệu thuật toán Karp-Rabin
Thuật toán mang tên hai nhà khoa học phát minh ra nó
Michael O. Rabin (sinh năm 1931, người Đức) and
Richard M. Karp (sinh năm 1931, người Mỹ), đều được
giải Turing Award, giải thưởng uy tín nhất trong nghành
khoa học máy tính và công nghệ thông tin.
Ý tưởng thuật toán
Hàm băm:
hash(w[0…m-1]) = h = (w[0]*2m-1 + w[1]*2m-2 +… w[m-1]*20)
mod q
Việc tính lại hàm băm như sau:
Rehash(a,b,h)=h = ((h – a*2m-1)*2 + b)mod q
Hàm băm tốt:
các thao tác cơ bản được thực hiện hiệu quả
khi băm hai xâu con khác nhau có cùng độ dài mm, xác suất
hai giá trị băm giống nhau là nhỏ.
Giải thuật thuật toán(1)
Giải thuật thuật toán(2)
1. function Rabin_Karp(string T[1..n], string P[1..m])
2. hsub := hash(P[1..m]) // giá trị băm của xâu P
3. hs := hash(T[1..m]) // giá trị băm của xâu T
4. for i from 1 to n-m+1
5. if hs = hsub
6. if T[i..i+m-1] = P
7. return i
8. hs := hash(T[i+1..i+m]) // giá trị băm của xâu T[i+1..i+m]
9. return not found
Mã hóa thuật toán
Độ phức tạp thuật toán Karp-Rabin
Độ phức tạp về thời gian trong giai đoạn tiền xử lý là
O(M)
Khi tính giá trị băm cho T[i+1..i+m] ta mất thời gian là
O(m), do công việc này được thực hiện trong (n-m+1)
lần.
Độ phức tạp trong giai đoạn tìm mẫu là O(M*N)
Kiểm nghiệm thuật toán(1)
Kiểm nghiệm thuật toán(2)
CẢM ƠN THẦY VÀ
CÁC BẠN ĐÃ THEO
DÕI !!!
11 trang
13/04/2022
6360
Bạn đang xem tài liệu "Bài thuyết trình Trí tuệ nhân tạo - Chủ đề: Thuật toán Karp-Rabin - Trần Thị Hạnh", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- bai_thuyet_trinh_tri_tue_nhan_tao_chu_de_thuat_toan_karp_rab.pptx
