课题基金 / 基金详情

Discrete System Theory and Large-Scale Optimization Methods Based on Binary Decision Diagrams and

Discrete System Theory and Large-Scale Optimization Methods Based on Binary Decision Diagrams and
基于二元决策图的离散系统理论和大规模优化方法
批准号:
09480050
负责人:
IMAI Hiroshi
金额:
$9.47万
依托单位:
依托单位国家:
日本
项目类别:
Grant-in-Aid for Scientific Research (B).
财政年份:
1997
资助国家:
日本
项目状态:
已结题
起止时间:
1997 至 2000

项目摘要

项目成果

IMAI Hiroshi的其他基金

相似基金

相关文献

中文摘要
翻译
在本研究中,我们的目的是提出一个统一的方法,离散系统理论的基础上二叉决策图,并开发一个原型系统的统一系统。通过我们的结果,我们现在可以表示整个中等规模的离散结构,在一个隐式和紧凑的方式,这不能通过现有的方法。我们应用我们的方法来计算网络的可靠性,也计算琼斯多项式的结。这些计算问题是已知的#P-hard,但是,与我们的方法,中等规模的问题可以在实践中严格解决。例如,可以计算14 x14网格的网络可靠性函数。我们还探讨了二元判定图的基本理论,通过研究一个单调布尔函数直接表示和用它们的素蕴涵表示时的大小差异,并提出了新的方法,一种是基于代数方法,另一种是基于量子方法。关于代数方法,Grobner基充分研究网络流问题。关于量子方法,我们研究了二进制决策图的量子模拟,以研究量子计算的计算能力。这些新结果将很快公布。
英文摘要
In this research, we aimed at proposing a unified approach to discrete system theory based on binary decision diagrams, and developing a prototype system for the unified system. By our results, we can now represent the whole moderate-scale discrete structure in a implicit and compact manner, which could not be done by the existing methods. We applied our approach to network reliability computation and also computing the Jones polynomial of a knot. These computation problems are known to be #P-hard, but, with our methods, moderate-size problems can be solved rigorously in practice. For example, the network reliability function of a grid of 14x14 can be computed. We also explore fundamental theory of binary decision diagrams, by investigating the difference in size when a monotone Boolean function is represented directly and when it is represented by their prime implicants.New approaches have also been demonstrated, one is based on algebraic approach, and the other is based on quantum approach. Concerning the algebraic approach, Grobner bases are fully investigated for network flow problems. Concerning the quantum approach, we investigate a quantum analog of binary decision diagrams in order to investigate the computational power of quantum computing. These new results will be published soon.
期刊论文(44)
专著(0)
科研奖励(0)
会议论文
K.Sekine and H.Imai: "Counting the Number of Paths in a Graph via BDDs"IEICE Transactions on Fundamentals. E80-A. 682-688 (1997)
K.Sekine 和 H.Imai:“通过 BDD 计算图中路径的数量”IEICE Transactions on Fundamentals。
DOI: --
发表时间:
期刊:
影响因子: --
作者: []
通讯作者:
S.Fujishige, ed., H.Imai et al: "Discrete Structure and Algorithms V : Network Reliability Computation and Related Topics (in Japanese)"Kindai-kgaku-sha. 1-50 (1997)
S.Fujishige 编辑、H.Imai 等人:“离散结构和算法 V:网络可靠性计算和相关主题(日语)”Kindai-kgaku-sha。
DOI: --
发表时间:
期刊:
影响因子: --
作者: []
通讯作者:
A.Tajima and H.Imai: "Computational Investigations of the Optimality of Two-and Three-Dimensional Triangulations under Several Criteria" Proceedings of the 10th Canadian Conference on Computational Geometry. 44-45 (1998)
A.Tajima 和 H.Imai:“若干标准下二维和三维三角剖分的最优性的计算研究”第十届加拿大计算几何会议论文集。
DOI: --
发表时间:
期刊:
影响因子: --
作者: []
通讯作者:
DOI: --
发表时间:
期刊:
影响因子: --
作者: []
通讯作者:
共 39 条
    Computational Combinatorial Physics by Harmonizing Matroid Theory and Quantum Physics
    • 批准号:
      16K12392
    • 项目类别:
      Grant-in-Aid for Challenging Exploratory Research
    • 资助金额:
      $2.16万
    • 财政年份:
      2016
    • 负责人:
      IMAI Hiroshi
    • 依托单位:
    Interaction between two motor domains of cytoplasmic dynein stepping along microtubules revealed by cryo-electron microscopy.
    Exploration of synthesis and outward acceleration of circumstellar matter through simultaneous multiple-band high-resolution radio imaging
    • 批准号:
      16H02167
    • 项目类别:
      Grant-in-Aid for Scientific Research (A)
    • 资助金额:
      $29.87万
    • 财政年份:
      2016
    • 负责人:
      IMAI Hiroshi
    • 依托单位:
    Exploiting Matroid Minor Theory and Its Connection with Quantum Computing Models
    • 批准号:
      26540004
    • 项目类别:
      Grant-in-Aid for Challenging Exploratory Research
    • 资助金额:
      $2.33万
    • 财政年份:
      2014
    • 负责人:
      IMAI Hiroshi
    • 依托单位:
    国内基金
    海外基金
    XsmiR167为核心的ceRNA network调控文冠果雄花雌蕊败育机制研究
    • 批准号:
      32572006
    • 项目类别:
      面上项目
    • 资助金额:
      50.00万元
    • 批准年份:
      2025
    • 负责人:
      敖妍
    • 依托单位:
    铜募集微纳米网片上调LOX活性稳定胶原网络促进盆底修复的研究
    • 批准号:
      82371638
    • 项目类别:
      面上项目
    • 资助金额:
      49.00万元
    • 批准年份:
      2023
    • 负责人:
      陈信良
    • 依托单位:
    GPSM1介导Ca2+循环-II型肌球蛋白网络调控脂肪产热及代谢稳态的机制研究
    • 批准号:
      82370879
    • 项目类别:
      面上项目
    • 资助金额:
      49.00万元
    • 批准年份:
      2023
    • 负责人:
      严婧
    • 依托单位:
    RagD调控mTORC2溶酶体定位的机制及功能研究
    • 批准号:
      32100578
    • 项目类别:
      青年科学基金项目(C类)
    • 资助金额:
      30.0万元
    • 批准年份:
      2021
    • 负责人:
      陈蕾
    • 依托单位: