Trí tuệ nhân tạo - Thuật toán Karp-Rabin

Tài liệu Trí tuệ nhân tạo - Thuật toán Karp-Rabin: TRÍ TUỆ NHÂN TẠO Thuật toán Karp-RabinGiảng viên hướng dẫn : TS. Từ Minh PhươngLớp: Hệ thống thông tin Nhóm 3: Trần Thị HạnhMẫn Hồng DươngDương Văn ĐoànNội dungGiới thiệu thuật toán Karp-RabinÝ tưởng thuật toán Karp-RabinGiải thuật thuật toánMã hóa thuật toánĐộ phức tạp của thuật toánKiểm nghiệm thuật toánGiới thiệu thuật toán Karp-RabinThuậ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ánHàm băm: hash(w[0m-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 qHà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.....

pptx11 trang | Chia sẻ: honghanh66 | Ngày: 19/03/2018 | Lượt xem: 240 | Lượt tải: 0download
Bạn đang xem nội dung tài liệu Trí tuệ nhân tạo - Thuật toán Karp-Rabin, để tải tài liệu về máy bạn click vào nút DOWNLOAD ở trên
TRÍ TUỆ NHÂN TẠO Thuật toán Karp-RabinGiảng viên hướng dẫn : TS. Từ Minh PhươngLớp: Hệ thống thông tin Nhóm 3: Trần Thị HạnhMẫn Hồng DươngDương Văn ĐoànNội dungGiới thiệu thuật toán Karp-RabinÝ tưởng thuật toán Karp-RabinGiải thuật thuật toánMã hóa thuật toánĐộ phức tạp của thuật toánKiểm nghiệm thuật toánGiới thiệu thuật toán Karp-RabinThuậ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ánHàm băm: hash(w[0m-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 qHà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 foundMã 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 !!!

Các file đính kèm theo tài liệu này:

  • pptxtrituenhantao_nhom3_8524.pptx
Tài liệu liên quan