計算量理論I【電子版】

書影
電子

SDB Digital Books  別巻1

計算量理論I【電子版】

アルゴリズムの数学的定義からP≠NP予想まで
定価:
2,750
(本体:2,500円+税)
難易度:上級

発行日:2017年3月10日

発行:サイエンス社

ISBN:978-4-7819-9914-2

サイズ:電子書籍

ページ数:224ページ

在庫:在庫あり

内容詳細

数学理論としても深さがあるだけでなく実用的な応用という側面からも重要な計算量理論について,チューリング機械と呼ばれる数学モデルを使い,その基礎を学ぶ.学部3,4年生以上を対象とした,著者渾身の書.

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

目次

第0章 準備
  0.1 アルファベット・語・言語
  0.2 再帰的定義
  0.3 2項関係
  0.4 グラフ
  0.5 論理式とブール関数
  0.6 擬似プログラムによるアルゴリズムの記述
  0.7 漸近記法

第1章 アルゴリズムの数学モデル
  1.1 歴史的背景
  1.2 アルゴリズムの本質は?
  1.3 エルブラン・ゲーデル計算可能関数
  1.4 帰納的関数
  1.5 whileプログラム
  1.6 ラムダ定義可能関数
  1.7 マルコフアルゴリズム

第2章 チューリング機械
  2.1 多テープチューリング機械
  2.2 オフラインTM
  2.3 両方向テープ
  2.4 チューリング計算可能関数
  2.5 問題の符号化(なぜTMがアルゴリズムなのか)
  2.6 なぜ計算可能関数がアルゴリズムなのか?

第3章 決定性/非決定性TMと計算量
  3.1 非決定性とは
  3.2 TMによる計算量

第4章 基本定理
  4.1 計算量の線形圧縮
  4.2 テープ本数の削減
  4.3 1テープTMと交差列
  4.4 その他の計算量

第5章 計算量のクラスの間の基本的関係
  5.1 基本的クラス
  5.2 非決定性vs決定性,時間量vsスペース量
  5.3 サヴィッチの定理
  5.4 イマーマン・セレプトセーニィの定理

第6章 計算量の階層
  6.1 帰納的言語のクラス
  6.2 決定性計算量の階層
  6.3 非決定性計算量の階層

第7章 決定不能問題
  7.1 アルゴリズムが存在しない問題とは
  7.2 ライスの定理
  7.3 算術階層
  7.4 ヒルベルトの第10問題

第8章 問題の還元
  8.1 還元とは
  8.2 決定不能問題の還元
  8.3 完全問題

第9章 NP完全問題
  9.1 クラスNP
  9.2 SAT
  9.3 NP完全問題オンパレード
  9.4 NP完全問題の間の還元

第10章 なぜNP完全問題なのか?
  10.1 NP完全問題と暗号系
  10.2 離散対数問題
  10.3 オラクル(相対化)
  10.4 補足:群・環・体とmod nの整数論

第11章 その他の計算量のクラス
  11.1 クラスcoNP
  11.2 クラスP
  11.3 クラスPSPACE
  11.4 クラスNL
  11.5 手に負えない問題

第12章 決定問題以外の問題
  12.1 関数問題
  12.2 数え上げ問題

参考書案内
索引

サポート情報

その他


SDB Digital Books 別巻1
「計算量理論I【電子版】」サポートページ