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

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

基本信息

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

项目摘要

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

这项研究的目的是使用具有合理扩展到问题的计算模型，这些问题在传统的计算复杂性理论领域被认为是无法控制的，以找到具有一定程度放松的解决方案。具体而言，采用以下方法来获得每个方法的结果。 1。一种关注概率算法的方法：我们已经构造了一种并行算法，该算法在图上找到了最大路径，并介绍了其应用程序。我们还考虑了确定部分故障电路位置故障的问题。对于典型的情况，我们构建了一种实际算法，该算法寻求理论下限，并证明了与这种行为相似的行为，表明上限。 2。一种针对使用更多颗粒状尺度的现实解决方案的方法，例如限制了被认为是不守规矩的问题的解决方案的大小。对于图表上的某些问题，我们获得了候选解决方案大小的情况的结果。 3。考虑问题中并行性评估的一种方法：我们检查了在平行计算中被认为是无法控制的问题，在哪些情况下可以处理。具体来说，我们已经解决了以给定图的最小词汇顺序找到最大独立点的问题。还显示，使用“最长的定向路径长度”参数可以在某种程度上评估此问题的并行性。另一方面，这还表明该参数在其他问题中具有局限性，并且在称为随机图的图上效果不佳。