Bài thuyết trình: Thuật toán Karp-Rabin

Chia sẻ: Pham Thanh | Ngày: | Loại File: PPTX | Số trang:11

Thêm vào BST

Báo xấu

327
lượt xem 19
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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;... là những nội dung chính mà "Bài thuyết trình: Thuật toán Karp-Rabin" hướng đến trình bày.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài thuyết trình: Thuật toán Karp-Rabin

TRÍ TUỆ NHÂN TẠO Thuật toán Karp-Rabin 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 KarpRabin Ý tưởng thuật toán KarpRabin 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…m1]) = h = (w[0]*2m1 + w[1]*2m2 +… 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*2m1)*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 nm+1 5. if hs = hsub 6. if T[i..i+m1] = 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 (nm+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 !!!