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

代教的および確率的手法による離散構造の限界の究明

使用算术和概率方法研究离散结构的极限

基本信息

批准号：
16092205
负责人：
伊東利哉
金额：
$ 8.83万
依托单位：
Tokyo Institute of Technology
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research on Priority Areas
财政年份：
2004
资助国家：
日本
起止时间：
2004 至 2007
项目状态：
已结题

项目摘要

本研究では、代数的手法および確率的手法を用いて、置換族の構成、電子商取引、 VLSI計算、可逆計算、および耐故障計算などに関する離散構造の限界を解明した、置換族の構成に関しては、電子文書間の高速な類似性ツールとして応用が知られているκ限定ε近似的最小値独立置換族Fに対して、一般分布上で定義される置換族Fを行列Uにより定式化し、その行列Uの階数を評価することにより置換族Fのサイズの良好な下界を導出した。電子商取引に関しては、最適選好マッチング問題において、顧客集合が複数の重み付きグループに分割されているとき、顧客数n商品数mの比に関して、乱択化最適選好マッチングが存在するためのほほ合致する上界と下界を導出した(これは、既に知られている顧客集合が1つグループである場合の乱択化最適選好マッチングが存在するための顧客数nと商品数mの比に関する上界・下界の拡張である)。まだ、商品価格設定問題に関しては、正価格モデルおよび無損失割引モデルにおいて見積価格が制限された場合に対して、確率的手法を用いることで,グラフ価格設定問題・線状高速道路問題・環状高速道路問題の良好な近似アルゴリズムを提案した。VLSI計算に関しては、3次元チャネル配線問題がNP困難であることを明らかにした。可逆計算に関しては、可逆回路の縮退故障に対する最小完全テスト集合生成問題がNP困難であることを示した。耐故障計算に関しては、様々なネットワークに対して効率的な確率的耐故障ネットワークを構成する統一的な手法を提案した。

In this study, algebraic methods and accuracy methods are used in the construction of permutation families, electronic quotient extraction, VLSI calculation, reversible calculation, and fault-tolerant calculation. The discrete structure bound is solved. The construction of permutation families is related to the high speed similarity between electronic documents. A good lower bound of the permutation family F is derived by evaluating the order of the permutation family F. Electronic business acquisition is related to the optimal selection of the customer set, the division of the customer set, the ratio of the number of customers n to the number of goods m, the optimization of the customer set, the existence of the customer set, the upper bound and the lower bound of the customer set are derived.(For example, the ratio between the number of customers n and the number of products m is the upper bound and the lower bound of the ratio between the number of customers n and the number of products m.) The problem of commodity grid setting is related to the problem of linear expressway and the problem of circular expressway. VLSI calculation is related to the problem of three-dimensional routing. Reversible computation is related to the problem of minimum complete set generation for reversible loops with regression faults. A unified approach to fault tolerance calculation is proposed.