TAILIEUCHUNG - Bài giảng Cấu trúc dữ liệu và giải thuật: Bảng băm - Bùi Tiến Lên

Bài giảng Cấu trúc dữ liệu và giải thuật: Bảng băm cung cấp cho người học các kiến thức: Khái niệm các lý thuyết đồng dư, áp dụng lý thuyết đồng dư, bảng băm, chuyển kiểu cho khóa, các loại hàm băm | Bài giảng Cấu trúc dữ liệu và giải thuật: Bảng băm - Bùi Tiến Lên BẢNG BĂM Bùi Tiến Lên 01/01/2017 LÝ THUYẾT ĐỒNG DƯ Các khái niệm Định nghĩa 1 Cho số nguyên dương n ∈ N, hai số nguyên a, b ∈ Z được gọi là đồng dư theo mô-đun n nếu cả hai có cùng số dư khi chia cho n. Được ký hiệu a ≡ b (modn) Ví dụ 1 Ta có I 11 ≡ 8 (mod3) (vì 11 và 8 chia cho 3 đều có số dư là 2) I −2 ≡ 5 (mod7) (vì -2 và 5 chia cho 7 đều có số dư là 5) Spring 2017 Data structure & Algorithm 3 Một số tính chất Tính chất Quan hệ đồng dư là một quan hệ tương đương I Tính phản xạ a ≡ a (modn) I Tính đối xứng a ≡ b (modn) ⇒ b ≡ a (modn) I Tính bắc cầu a ≡ b (modn) và b ≡ c (modn) ⇒ a ≡ c (modn) Spring 2017 Data structure & Algorithm 4 Một số tính chất (cont.) Tính chất Nếu a1 ≡ b1 (modn) a2 ≡ b2 (modn) Thì I a1 + a2 ≡ b1 + b2 (modn) I a1 − a2 ≡ b1 − b2 (modn) I a1 a2 ≡ b1 b2 (modn) I a1k ≡ b1k (modn) Spring 2017 Data structure & Algorithm 5 Áp dụng Ví dụ 2 Tìm phần dư của phép chia 332 cho 17 Lời giải tính trực tiếp I Ta có 332 = 1853020188851841 I Và 1853020188851841 mod 17 = 1 I Vậy, phần dư của phép chia 332 cho 17 là 1 Spring 2017 Data structure & Algorithm 6 Áp dụng (cont.) Lời giải đồng dư Ta có 2 22 32 22 3 ≡3 (mod17) 2 22 ≡ 92 (mod17) 22 22 ≡ 812 (mod17) ≡ 152 (mod17) 2 2 ≡ 2252 (mod17) ≡ 42 (mod17) ≡ 162 (mod17) ≡ 256 (mod17) ≡ 1 (mod17) Spring 2017 Data structure & Algorithm 7 Áp dụng (cont.) Ví dụ 3 Tìm hai chữ số cuối cùng của số 716 Lời giải Hai

• Cơ sở dữ liệu
• Cấu trúc dữ liệu
• Bài giảng Cấu trúc dữ liệu
• Cấu trúc dữ liệu và giải thuật
• Hàm băm
• Phân loại hàm băm
• Lý thuyết đồng dư
• cấu trúc dữ liệu và giải thuât
• bài giảng cấu trúc dữ liệu và giải thuât
• tài liệu cấu trúc dữ liệu và giải thuât
• giáo trình cấu trúc dữ liệu và giải thuât
• bài tập cấu trúc dữ liệu và giải thuât
• Cấu trúc dữ liệu cây AVL
• Cấu trúc dữ liệu cây
• Thuật toán DSW
• Cây nhị phân tìm kiếm
• Cấu trúc dữ liệu cây đỏ đen
• Cấu trúc dữ liệu cho nút cây đỏ đen
• Phép biến đổi cây đỏ đen cân bằng
• giáo trình cấu trúc dữ liệu
• bài tập cấu trúc dữ liệu
• đề cương cấu trúc dữ liệu
• lập trình dữ liệu
• Vị trí cấu trúc dữ liệu
• Áp dụng tin học
• Cơ sở dữ liệu
• Quan hệ giải thuật
• Cấu trúc dữ liệu cơ bản
• Đánh giá cấu trúc dữ liệu
• Định nghĩa kiểu dữ liệu
• Kiểu dữ liệu có cấu trúc
• Đánh giá thuật toán
• Thiết kế cấu trúc dữ liệu
• Bài giảng Cấu trúc dữ liệu và giải thuật
• Kiểu dữ liệu trừu tượng
• Kiểu dữ liệu cây
• Phân loại cây
• Cấu trúc dữ liệu giải thuật
• Bài giảng Cấu trúc dữ liệu giải thuật
• Ngôn ngữ lập trình
• Cấu trúc chương trình
• Cấu trúc điều khiển
• Tài liệu Cấu trúc dữ liệu
• Cấu trúc dữ liệu căn bản
• Khái niệm cấu trúc dữ liệu
• Độ phức tạp thuật toán
• tiếp cận lập trình
• thuật toán
• thuật toán trong cấu trúc dữ liệu
• cấu trúc dữ liệu động
• kỹ thuật sắp xếp