計算量理論II【電子版】

電子

SDB Digital Books  別巻2

計算量理論II【電子版】

P≠NP 予想の解決に向けて:近似/並列/確率性アルゴリズム
定価:
2,750
(本体:2,500円+税)
難易度:上級

発行日:2017年9月10日

発行:サイエンス社

ISBN:978-4-7819-9929-6

サイズ:電子書籍

ページ数:329ページ

在庫:在庫あり

内容詳細

最大の未解決問題であるP≠NP予想にアタックするために,アルゴリズムの並列化,近似アルゴリズム,アルゴリズムへのランダム性の導入,現在のコンピュータとはまったく違う原理に基づく量子アルゴリズムといった観点からアプローチし,その可能性と限界について考察する.学部3,4年生以上を対象とした,著者渾身の書.

ご注文に際しての注意事項
×プリントアウト
×注文キャンセル
~この商品は電子書籍です.電子書籍についてのご利用案内を必ずご確認ください.~

目次

第1章 近似とは
  1.1 最適化問題
  1.2 最適化問題vs決定問題

第2章 近似可能性
  2.1 近似比―近似の精度
  2.2 定数近似できない問題―最初の例
  2.3 定数近似できる問題のリスト

第3章 巡回セールスマン問題
  3.1 TSPの近似―概要
  3.2 メトリックTSP
  3.3 (1,2)-TSP
  3.4 歩き回りTSP

第4章 いくらでも良い近似ができる問題
  4.1 PTAS
  4.2 PTASとFPTASの例
  4.3 強NP完全な決定問題とFPTAS

第5章 近似における完全問題
  5.1 NP最適化問題における完全性
  5.2 NPO完全な問題
  5.3 APX完全な問題
  5.4 PTAS完全な問題
  5.5 近似問題のクラスの間の関係

第6章 発見的手法による近似
  6.1 ヒューリスティックス
  6.2 確率的な手法

第7章 並列計算
  7.1 並列計算のモデル1:交代性TM
  7.2 並列計算量のクラス
  7.3 線形未満の時間限定ATM
  7.4 交代回数限定のATM

第8章 逐次計算と並列計算の関係
  8.1 決定性/非決定性計算量と交代性計算量
  8.2 もっとATMについて
  8.3 多項式時間階層

第9章 並列計算のモデル2:論理回路
  9.1 論理回路―基本的定義
  9.2 ブール関数の回路計算量

第10章 論理回路と言語
  10.1 回路計算量の下界
  10.2 一様論理回路族
  10.3 アドバイス関数と非一様な論理回路族

第11章 並列計算により高速化できる問題
  11.1 NC問題
  11.2 論理回路とATM

第12章 並列計算のモデル3:PRAM
  12.1 PRAM機械とプログラム
  12.2 並列アルゴリズムの技法
  12.3 同時読み込み/書き出しと排他的読み込み/書き出し
  12.4 PRAMと他のモデルとの関係
  12.5 並列計算の定律

第13章 乱択/確率性アルゴリズム
  13.1 乱択アルゴリズムと平均時間計算量
  13.2 確率性アルゴリズムとは

第14章 確率性TMとその部分クラスたち
  14.1 基本的定義
  14.2 多項式時間限定PTMとクラスPP
  14.3 エラー確率限定PTM:クラスBPP
  14.4 モンテカルロアルゴリズムとラスベガスアルゴリズム

第15章 戸田の定理
  15.1 確率性計算と数え上げ問題:導入
  15.2 パリティ計算量のクラス⊕P
  15.3 ヴァリアント・ヴァジラーニの定理
  15.4 PH⊆P#SAT:ランダム還元から決定性の還元へ
  15.5 ⊕P,#P,PHの相対化

第16章 対話型証明系
  16.1 決定性対話型証明系
  16.2 対話型証明系IP
  16.3 PCP定理

第17章 NP⊆PCP(n3;1)
  17.1 証明の概要
  17.2 証明
  17.3 PCP定理成立に至る小史

第18章 脱ランダム化
  18.1 脱ランダム化の十分条件:擬似乱数生成器
  18.2 脱ランダム化の必要条件:回路計算量の下界
  18.3 擬似乱数生成法

第19章 数理論理学と計算量のクラス
  19.1 1階述語論理
  19.2 2階述語論理

第20章 量子計算
  20.1 量子ビット―量子の世界の基本単位―とその操作
  20.2 量子コンピュータの数理モデル
  20.3 量子回路,量子チューリング機械,量子計算量
  20.4 ショアの因数分解アルゴリズム

第21章 雑多な補足
  21.1 多項式時間同型性
  21.2 決定木
  21.3 平均計算量

参考書案内
索引

サポート情報