確率的組合せ論のＸ符号及び類似の離散構造への応用

点击翻译按钮获取中文摘要

本研究では、数学の一分野である確率的組合せ論を用いて、X符号をはじめとする種々の組合せ構造について理論的に明らかにすることを目的としている。本年度は、前年度までの研究で、X符号の圧縮比に関する限界式の導出や構成アルゴリズムを考案する際に用いた確率的証明や確率的証明の脱乱択化の手法を、グラフ理論における概支配集合や無線通信のスペクトラム拡散における周波数ホッピング系列に応用し、次の研究成果を得た。まず、グラフの概支配集合とは、支配集合という無線通信ネットワークやセンサーネットワークなど様々な応用先のあるグラフの頂点集合を一般化した集合であるが、他の条件が同じであればその集合の大きさは、小さいことが望ましい。本研究では、概支配集合の大きさをどこまで小さくできるのかの解析のため、その要素数に関する限界式を確率的証明によって新たに導出した。また、導出した限界式を満たす概支配集合の構成アルゴリズムを考案した。このアルゴリズムは、入力として対象のグラフを必要としないという驚くべき特徴を持ち、この特徴により、この構成アルゴリズムはネットワークのトポロジーが刻一刻と変化するセンサーネットワークへの適用性に優れている。次に、周波数ホッピング系列については、既存の研究では代数学的視点による抽象化が自然であるため、代数学的手法に大きく偏っており、代数学が特に有効であるような、限られた状況のみが考察されている場合が多いのだが、本研究において、周波数ホッピング系列に対しても確率的組合せ論を用いて、既知の限界式を改良することができている。X符号に関する研究結果が概支配集合や周波数ホッピング系列に関する研究に発展したように、本研究による理論的考察とその結果の影響は他分野にも広く波及すると期待される。