株式会社サイエンス社 株式会社新世社 株式会社数理工学社
ホーム 会社案内 社員募集 ご意見・ご感想 リンク 当サイトの利用  



SDB Digital Books 別巻1

「計算量理論I【電子版】」
〜 アルゴリズムの数学的定義からP≠NP予想まで 〜

守屋悦朗(早稲田大学教授) 著

定価:2,700円(本体2,500円+税)
発行:サイエンス社
発行日:2017-03-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 数え上げ問題

参考書案内
索引