ブール代数に基づいた計算の複雑さに関する研究

この論文をさがす

著者

    • 天野, 一幸 アマノ, カズユキ

書誌事項

タイトル

ブール代数に基づいた計算の複雑さに関する研究

著者名

天野, 一幸

著者別名

アマノ, カズユキ

学位授与大学

東北大学

取得学位

博士 (情報科学)

学位授与番号

甲第5718号

学位授与年月日

1996-03-26

注記・抄録

博士論文

目次

  1. 目次 / p1 (0004.jp2)
  2. 1 序論 / p3 (0006.jp2)
  3. 1.1 本研究の背景と目的 / p3 (0006.jp2)
  4. 1.2 本論文の構成 / p6 (0009.jp2)
  5. 2 論理関数の複雑さ / p9 (0012.jp2)
  6. 2.1 はじめに / p9 (0012.jp2)
  7. 2.2 ブール代数と論理関数 / p9 (0012.jp2)
  8. 2.3 論理回路 / p12 (0015.jp2)
  9. 2.4 チューリング機械と論理回路の関係 / p14 (0017.jp2)
  10. 2.5 過去の結果 / p16 (0019.jp2)
  11. 2.6 Razborovの近似法 / p17 (0020.jp2)
  12. 2.7 まとめ / p21 (0024.jp2)
  13. 3 近似演算の一般化と否定限定論理回路 / p23 (0026.jp2)
  14. 3.1 はじめに / p23 (0026.jp2)
  15. 3.2 近似演算の一般化 / p25 (0028.jp2)
  16. 3.3 否定限定論理回路に対する近似法の適用 / p31 (0034.jp2)
  17. 3.4 まとめ / p41 (0044.jp2)
  18. 4 切断の概念に基づいた近似理論 / p43 (0046.jp2)
  19. 4.1 はじめに / p43 (0046.jp2)
  20. 4.2 切断の概念に基づく近似法 / p45 (0048.jp2)
  21. 4.3 クリーク関数の単調複雑さ / p50 (0053.jp2)
  22. 4.4 近似モデルの構造 / p60 (0063.jp2)
  23. 4.5 擬似補関数に対する近似モデル / p69 (0072.jp2)
  24. 4.6 非決定性論理回路に対する近似モデル / p77 (0080.jp2)
  25. 4.7 まとめ / p82 (0085.jp2)
  26. 5 k-限定独立性に基づいたDNF式の近似アルゴリズム / p84 (0087.jp2)
  27. 5.1 はじめに / p85 (0088.jp2)
  28. 5.2 k-限定独立確率分布 / p86 (0089.jp2)
  29. 5.3 DNF式の充足割り当ての近似数え上け / p92 (0095.jp2)
  30. 5.4 まとめ / p109 (0112.jp2)
  31. 6 結論 / p111 (0114.jp2)
  32. 謝辞 / p114 (0117.jp2)
  33. 参考文献 / p115 (0118.jp2)
  34. 発表論文 / p120 (0123.jp2)
0アクセス

各種コード

  • NII論文ID(NAID)
    500000134968
  • NII著者ID(NRID)
    • 8000000974043
  • DOI(NDL)
  • NDL書誌ID
    • 000000299282
  • データ提供元
    • NDL-OPAC
    • NDLデジタルコレクション
ページトップへ