CƠ SỞ NHỎ NHẤT CỦA CÁC TẬP CON k-SETS

Tóm tắt

Trong các lĩnh vực về lí thuyết thông tin nhưdựng mô hình lưu trữ, chia sẻ riêng tư, mã hóa... đôi khi ta muốn phân tán một mẫu dữ liệu cho trước thành nhiều phần nhỏ, mỗi phần được lưu giữ bởi một party mà khi một số lượng đủ nhiều các party phối hợp với nhau thì sẽ có cách khôi phục lại được thông tin gốc. Hướng tới mục tiêu đó, bài viết này mô tả việc xuất phát từ một tập hợp hữu hạn,xây dựng một họ các tập con cùng số phần tử sao cho tồn tại duy nhất một hoán vị là ánh xạ 1-1 vào mỗi tập con. Tất nhiên, tính tối ưu sẽ được xét thông qua kích cỡ nhỏ nhất của họ các tập con đó. Bằng cách đánh giá số lượt xuất hiện của mỗi phần tử trong các tập con, ta có thể thiết lập được thành công chặn dưới cho số tập con, đồng thời xây dựng được bằng mô hình graph đơn vô hướng. Bước xây dựng chỉ thành công với những dữ liệu thích hợp và trường hợp tổng quát đang được nghiên cứu thêm.