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

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. | 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 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. ví dụ xâu “hello” được gán với giá trị 5 chẳng hạn, và hai xâu được gọi là bằng nhau nếu giá trị băm của nó bằng nhau. Như vậy thay vì việc phải đối sánh các xâu con của T với mẫu P, ta chỉ cần so sánh giá trị hàm băm của chúng và đưa ra kết luận 3 Ý 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[1n], string P[1m]) 2. hsub := hash(P[1m]) // giá trị băm của xâu P 3. hs := hash(T[1m]) // 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[ii+m-1] = P 7. return i 8. hs := hash(T[i+1i+m]) // giá trị băm của xâu T[i+1i+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+1i+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 !!!

• Thủ thuật máy tính
• Bài thuyết trình
• Thuật toán Karp Rabin
• Tìm hiể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
• Kỹ năng thuyết trình
• Thuyết trình trước công chúng
• Hướng dẫn thuyết trình trước đám đông
• Tham khảo kỹ năng thuyết trình
• Học cách thuyết trình
• Tìm hiểu kỹ năng thuyết trình
• Cấu trúc bài thuyết trình
• Kinh nghiệm làm bài thuyết trình
• Phương pháp thuyết trình
• Bài thuyết trình ấn tượng
• Các bước xây dựng bài thuyết trình
• Kỹ năng thuyết trình và thuyết phục
• Bài giảng Kỹ năng thuyết trình
• Giao tiếp phi ngôn từ
• Mục tiêu thuyết trình
• Bài thuyết trình pháp luật đại cương
• Bài thuyết trình vi phạm pháp luật
• Bài thuyết trình trách nhiệm pháp lý
• Thuyết trình vi phạm hành chính
• Thuyết trình vi phạm hình sự
• Thuyết trình dân sự
• Bài thuyết trình mẫu
• Cách thuyết trình
• Thuyết trình là gì
• Kỹ năng phản biện
• Cách làm bài thuyết trình
• Bí quyết thuyết trình
• Bài giảng Thuyết trình
• Nghệ thuật thuyết trình
• Yếu tố cơ bản của bài thuyết trình
• Phương tiện hỗ trợ thuyết trình
• Nghệ thuật thuyết trình hiệu quả
• Cách lựa chọn chủ đề bài thuyết trình
• Cấu trúc nội dung bài thuyết trình
• Mô hình phần thân bài thuyết trình
• Đề tài nghiên cứu vật lý
• Luận văn vật lý
• Lý thuyết tương đối
• Bài thuyết trình điện động lực học
• Bài thuyết trình vật lý lý thuyết
• Bài thuyết trình lý thuyết tương đối
• kinh nghiệm thuyết trình
• nghệ thuật thuyết trình thành công
• bí quyết thuyết trình hiệu quả
• cách thuyết trình trước đám đông
• Chuẩn bị cho bài thuyết trình
• tạo bài thuyết trình
• Thuyết trình hiệu quả với PowerPoint
• Thuyết trình với Power Point
• mẹo vặt trong thuyết trình
• thủ thuật thuyết trình
• kĩ năng thuyết trình hiệu quả
• Bài diễn thuyết
• Cách tổ chức bài diễn thuyết
• Chuẩn bị thuyết trình hiệu quả
• Kỹ thuật soạn slide thuyết trình
• Kết thúc thuyết trình ấn tượng
• Bài thuyết trình Kỹ năng mềm
• Phần mềm Prezi
• Phần mềm thuyết trình Powerpoint
• Công cụ thuyết trình
• Đề tài Phương tiện thuyết trình
• Kỹ thuật thuyết trình
• Sai lầm khi thuyết trình
• Soạn nội dung thuyết trình
• Cách thực hiện bài thuyết trình
• Bài thuyết trình hiệu quả
• Lý thuyết chất rắn và bán dẫn
• Bài thuyết trình lý thuyết chất rắn
• Đề tài lý thuyết chất rắn
• cách trình bày thuyết trình
• hướng dẫn thuyết trình
• thực hành thuyết trình
• cách tạo slide thuyết trình
• tạo slide thuyết trình ấn tượng
• Đặc điểm bài thuyết trình
• Phương tiện thuyết trình
• Thuyết trình bằng Overhead Projector
• Kỹ năng mềm
• Bài giảng Giao tiếp kinh doanh và thuyết trình
• Giao tiếp kinh doanh và thuyết trình
• Thuyết trình kinh doanh
• Hình thức thuyết trình trong kinh doanh
• Phân tích người thuyết trình
• bí quyết khi thuyết trình
• khái quát về thuyết trình
• xây dựng bài thuyết trình
• kỹ năng thuyết phục
• Thuyết trình thành công
• Thuyết trình trước đám đông
• Kỹ năng thuyết trình hiệu quả
• Khả năng thuyết trình
• Bí quyết thành công khi thuyết trình
• Thuyết trình hiệu quả