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

Lê Phúc Lữ, Nguyễn Đình Song Ân

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.

 


Từ khóa


tập cơ sở; điểm bất động; đồ thị; khôi phục hoán vị

Toàn văn:

PDF (English)

Trích dẫn


Bui, D. K., Nguyen, D. T., & Hoang, H. D. (2004). Giao trinh ma hoa thong tin – Li thuyet va ung dung [Course book of cryptography – Theory and Application]. Labour and Social publisher company limited, 90-100.

Diatonics, P., Fulman, J., & Guralnick, R. (2008). On fixed points of permutations. J. Algebraic Combi., 28(1), 189-218.

Jung, J., Mummert, C., Niese, E., & Schroeder, M. (2018). On erasure combinatorial batch codes. Designs, Codes and Cryptography, 12(1), 49.

Ishai, Y., Kushilevitz, E., & Ostrovsky, R. (2004). Batch codes and their applications. Proceedings of STOC 2004, ACM Press, 262-271.

Paterson, M. B., Stinson, D. R., & Wei, R. (2009). Cominatorial Batch Codes. Communications in Advanced Mathematical, 3(1), 13.

Smith, R. (2006). Permutation Reconstruction. The Electronic journal of combinatorics, 13(11).

Sean, E., Kevin, F., & Ben, G. (2016). Permutations fixing a k-set. International Mathematics Research Notices, 2016(21), 6713-6731.




DOI: https://doi.org/10.54607/hcmue.js.18.9.3027(2021)

DOI (PDF (English)): https://doi.org/10.54607/hcmue.js.18.9.3027.2945(2021)

Tình trạng

  • Danh sách trống