权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

情報科学における確率的組合せ論及び極値集合論を通した離散構造の考究

信息科学中随机组合学和极值集合论的离散结构研究

基本信息

批准号：
22KJ0344
负责人：
角田有
金额：
$ 2.33万
依托单位：
University of Tsukuba
依托单位国家：
日本
项目类别：
Grant-in-Aid for JSPS Fellows
财政年份：
2023
资助国家：
日本
起止时间：
2023-03-08 至 2024-03-31
项目状态：
已结题

来源：
https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-22KJ0344/
关键词：
情報理論符号理論 DSS 確率的組合せ論

项目摘要

本研究では、離散数学の一分野である確率的組合せ論を、情報科学における符号理論分野において活躍させ、効率的な構成法やより精度の高い理論限界の導出をすることを目指している。本研究課題2年目である本年度は、まず、昨年度得られた weak superimposed code の研究成果を類似の組合せ構造に応用することから着手した。本年度の研究において、特殊なグループテストに応用される、generalized cover-free family と呼ばれる構造について、既知の限界式を改良することができた。この結果は、weak superimposed code に関する研究成果とともに、現在論文にまとめている段階である。また、上述の研究成果は確率集中不等式を使った確率的手法を用いて得られたが、同様の手法にランダムシャッフルを応用することで、 difference system of sets（DSS）と呼ばれる組合せ構造に関する限界式を導出した。DSS を用いると、信号同期のために用いられる q 元の self-syncoronizing code を構成することができると知られており、DSS の redundancy というパラメータが小さいほどより多くの情報を格納でき、relative index と呼ばれるパラメータが大きいほどノイズに強くなる。本研究で得られた結果は、DSS の redundancy の必要条件である Levenshtein bound を漸近的に達成するという意味で漸近的に最適な DSS を任意の q と任意の relative index に対して構成できたというものである。さらにその証明は効率的な構成アルゴリズムを与えるものである。

This study is aimed at the combination theory of accurate probability in discrete mathematics, the theory of active probability in information science, and the derivation of theoretical limits with high precision. The research results of this research project in the past two years are similar to those of the previous year. This year's research is focused on the use of special classes, generalized cover-free families, and the improvement of known bound formulas. The results of this study are as follows: The above research results are used to determine the concentration inequality of accuracy. The same method is used to determine the difference system of sets (DSS). DSS is used in the same period, the signal is used in the same period, the q element self-synchronizing code is constructed, the DSS redundancy is used in the same period, and the DSS redundancy is used in the same period. The results of this study show that the necessary conditions for the redundancy of DSS are: Levenshtein bound; asymptotic; optimal DSS; arbitrary; relative index; and optimal DSS. The proof of this is that the composition of the film is not the same as that of the film