Xem mẫu
TRÍ TUỆ NHÂN TẠO
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-
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)
...
- tailieumienphi.vn
nguon tai.lieu . vn