Trong khoa học máy tính, hàm băm (hash function) là một thuật toán nhận
Trong khoa học máy tính, hàm băm (hash function) là một thuật toán nhận dữ liệu đầu vào có độ dài bất kỳ và trả về một chuỗi kết quả có độ dài cố định. Một hệ thống lưu trữ đám mây sử dụng một hàm băm để quản lý vị trí của các tệp tin. Hàm băm này sẽ chuyển mỗi tệp tin vào một trong \(N = 1024{\rm{\;}}\) khe lưu trữ có sẵn. Giả sử hàm băm chuyển các tệp tin vào 1024 khe một cách ngẫu nhiên và đồng đều. Một vụ "đụng độ" xảy ra nếu hàm băm chuyển hai hoặc nhiều tệp tin khác nhau vào cùng một khe lưu trữ. Để đảm bảo hiệu suất, quản trị viên hệ thống muốn xác suất xảy ra đụng độ không vượt quá 1%. Tìm số lượng tệp tin tối đa mà hệ thống có thể lưu trữ để thỏa mãn yêu cầu này.
Đáp án đúng là:
Quảng cáo
Có \(N = 1024\) là số khe lưu trữ.
Gọi \(m\) là số tệp tin cần lưu, \(m \ge 1.\)
Mỗi tệp được đưa ngẫu nhiên vào một trong \(N = 1024\) khe với xác suất như nhau.
Ta cần tính giá trị lớn nhất của m để P (đụng độ) \( \le 0,01.\)
Gọi A là biến cố “Có ít nhất một vụ đụng độ khi lưu trữ m tệp tin”.
Suy ra biến cố \(\bar A\): “Không có vụ đụng độ nào”, hay \(m\) tệp tin được lưu vào \(m\) khe lưu trữ khác nhau.
Số cách xếp \(m\) tệp vào 1024 khe là \({1024^m}\).
Số cách xếp \(m\) tệp vào \(m\) khe khác nhau trong 1024 khe là \(A_{1024}^m\).
Suy ra \(P\left( {\overline A } \right) = \dfrac{{A_{1024}^m}}{{{{1024}^m}}}\)\( \Rightarrow P(A) = 1 - \frac{{A_{1024}^m}}{{{{1024}^m}}}\).
Xác suất xảy ra đụng độ không vượt quá 1%, tức là \(P(A) = 1 - \dfrac{{A_{1024}^m}}{{{{1024}^m}}} \le 0,01\)
Hay \(P\left( {\overline A } \right) = \dfrac{{A_{1024}^m}}{{{{1024}^m}}} \ge 0,99\).
Ta có bảng sau:
Nhận thấy với \(m \ge 6\) thì \(P\left( {\overline A } \right) < 0,99\).
Vậy giá trị lớn nhất của m là 5 thì xác suất xảy ra đụng độ không vượt quá 1%.
Đáp án cần điền là: 5
Tham Gia Group Dành Cho 2K9 Chia Sẻ, Trao Đổi Tài Liệu Miễn Phí
>> Học trực tuyến Lớp 10 cùng thầy cô giáo giỏi tại Tuyensinh247.com, (Xem ngay) Cam kết giúp học sinh học tốt, bứt phá điểm 9,10 chỉ sau 3 tháng, làm quen kiến thức, định hướng luyện thi TN THPT, ĐGNL, ĐGTD ngay từ lớp 10
 |
 |
 |
 |
 |
 |
 |
 |
Hỗ trợ - Hướng dẫn
-
024.7300.7989
-
1800.6947
(Thời gian hỗ trợ từ 7h đến 22h)
Email: lienhe@tuyensinh247.com
