エルゴード理論の計算機工学への応用

遍历理论在计算机工程中的应用

• 批准号: 12740066
• 负责人: 中田 寿夫
• 金额: $ 1.34万
• 依托单位: Fukuoka University of Education
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Encouragement of Young Scientists (A)
• 财政年份: 2000
• 资助国家: 日本
• 起止时间: 2000 至 2001
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-12740066/
• 关键词: エルゴード理論; 分散アルゴリズム; ネットワーク; マルコフ連鎖; 局所多数決問題; 合意問題; 順序統計量; 極値理論

本年度は主に次の2つのことを行った。1.有限グラフ上の確率的局所多数決問題における平均合意時間の研究2.確率的ネットワークにおける最短路の調査1.については有限グラフにおいて局所的な多数決を行い、自分の意見の更新れを確率的に決める方法を固定して、それについての平均合意時間について研究した。既に得られていたオーダに関する一般論を具体的におしすすめて、初期状態を見ただけで判断できるような評価式を得ることに成功した。しかし、それはまだタイトな評価とは言えないので、まだまだ改良の余地はある。さらに平均合意時間だけではなくて、合意するまでの分布も調べる必要があるが、今のところは解析が難解で今後の課題となっている。2.は具体的には次のような問題を考えている:「各枝に確率的な重みを持ったサイクルをもたないネットワークにおいて入口と出口が一点ずつあるとする。このとき、入口から出口までのパスの重みの最小のものと最大のものの分布を調べよ」一般のグラフについての考察は困難なので、特殊なグラフについて調査している。手段としてはネットワーク理論の既存の結果や極値理論や順序統計学を用いた結果を用いる。なお、この研究は九州大学システム情報科学研究院、山下雅史氏のグループとの共同研究であり、LSIの設計応用面から見ても有用な研究であると思われるが、まだまだ発展途上の話題である。

This year's main event is the second time. 1. A Study on the Average Desirable Time of the Majority Decision Problem of the Office with Limited Accuracy 2. A Study on the Shortest Path of the Generation of Accuracy 1. A Study on the Average Desirable Time of the Majority Decision Problem of the Office with Limited Accuracy 2. A Study on the Method of the Majority Decision Problem of the Office with Limited Accuracy 3. The general theory is that the initial state of the game is not correct. The answer to this question is: "There is room for improvement." The average desired time is equal to the average desired time. The average desired time is equal to the average desired time. The average desired time is equal to the average desired time. 2. To examine the specific problems in the next step: "The weight of each branch is determined by the number of entries and exits." The distribution of the minimum and maximum of the maximum Methods and methods: The existing results of the theory and the results of the sequence statistics are used. Research and development topics for LSI design applications are discussed at Kyushu University Institute of Information Science and Masashi Yamashita.

项目成果

T.Nakata, M.Yamashita: "Some Upper Bounds on Expected Agreement Time of a Probabilistic Local Majority Polling Game"Carleton Scientific. 11. 293-304 (2001)

T.Nakata、M.Yamashita：“概率性本地多数投票游戏的预期达成一致时间的一些上限”Carleton Scientific。

Nakata,Imahayashi,Yamashita: "A Probabilistic Local Majority Polling Game on Weighted Directed Graphs with an Application to the Distributed Agreement Problem"Networks. 35. 266-273 (2000)

Nakata、Imahayashi、Yamashita：“加权有向图上的概率局部多数投票游戏及其在分布式协议问题中的应用”网络。

中田寿夫: "正則グラフ上の単純投票に対する平均合意時間"京都大学数理解析研究所講究録. 1148. 181-186 (2000)

Hisao Nakata：“在正则图上进行简单投票的平均共识时间”京都大学数学科学研究所 Kokyuroku。1148. 181-186 (2000)。