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

拡張されたチューリングマシンモデルを用いた各種のアルゴリズムの研究

使用扩展图灵机模型研究各种算法

基本信息

批准号：
10780203
负责人：
上原隆平
金额：
$ 1.22万
依托单位：
Komazawa University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Encouragement of Young Scientists (A)
财政年份：
1998
资助国家：
日本
起止时间：
1998 至 1999
项目状态：
已结题

项目摘要

本研究の目的は、従来の計算量の理論の分野で手に負えないとされてきた問題に対して、妥当な拡張を行った計算モデルを使い、ある程度条件を緩めた解を求めることであった。具体的には以下のようなアプローチを行い、それぞれの結果を得た。1.確率的なアルゴリズムを中心にすえるアプローチ:グラフ上の極大パス集合を求める、並列アルゴリズムを構成し、その応用について示した。また、部分的に故障した回路の故障個所を特定する問題を考えた。そして代表的なケースについて、理論的な下界を求め、それらに近い振る舞いを示す実際のアルゴリズムを構成して、上界を示した。2.手に負えない、とされてきた問題に対して、解の大きさを限定するなど、もっと粒度の細かい尺度を用いて、現実的な解決をめざしたアプローチ:グラフ上のいくつかの問題に対して、その解の候補の大きさを制限した場合についての結果を得た。3.問題の並列性の評価を考察するアプローチ:並列計算において手に負えない、とされてきた問題に対して、どのような場合ならば手に負えるか、考察を行った。具体的には、与えられたグラフの辞書式順序最小の極大独立点を求める問題をとりあげた。そして、最長有向パス長というパラメータを使えば、この問題の並列性をある程度評価できることを示した。また一方でこのパラメータが他の問題では限界があることや、Random Graphと呼ばれるグラフではあまりうまく機能しないことも示した。

The purpose of this study is to calculate the theoretical differences between the two methods. The following are the results of the survey: 1. The accuracy of the system is determined by the maximum set of parameters, the composition of the system, and the use of the system. Some of the faults in the loop are specific problems. The lower bound of the theory, the upper bound of the theory 2. The problem is solved by hand, and the problem is solved by hand. The problem is solved by hand, and the problem is solved by hand. The problem is solved by hand. 3. The evaluation of the parallelism of the problem: parallel calculation, negative calculation The specific problem of the dictionary is the smallest independent point. The longest direction is to make the problem parallel. The problem is that the function of a Random Graph is not the same as that of a random graph.