アルゴリズムと計算量【電子版】

電子

SDB Digital Books  16

アルゴリズムと計算量【電子版】

Lectures on Computational Complexity
定価:
2,043
(本体:1,857円+税)
難易度:中級

発行日:2017年3月10日

発行:サイエンス社

ISBN:978-4-7819-9916-6

サイズ:電子書籍

ページ数:158ページ

在庫:在庫あり

内容詳細

数学,物理,化学,生物などの諸科学と計算機科学との有機的交流は今後ますます深まると思われる.本書は諸科学にバックグラウンドを持つ方々にとっての入門となることを目指した計算量理論のテキスト・レクチャーノートである.

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

目次

第1章 はじめに
1.1 アルゴリズムって何
1.2 アルゴリズムの性能
1.3 記法
1.4 グラフとグラフに関する計算問題

第2章 計算モデルと計算可能性
2.1 自然数
2.2 帰納的関数
2.3 ゲーデル数
2.4 λ-定義可能関数
2.5 チューリング機械
2.6 Church-Turingの提唱
2.7 ランダムアクセス機械

第3章 計算可能でない問題
3.1 様々なチューリング機械
3.2 帰納的に可算な問題と計算可能な問題
3.3 計算可能でない問題
3.4 帰着と決定不能問題

第4章 計算量クラスと基本定理
4.1 計算量
4.2 計算量の基本性質
4.3 オーダ記法
4.4 構成可能性と階層定理

第5章 計算量クラスΡとΝΡ
5.1 クラスΡ
5.2 クラスΝΡ
5.3 多項式時間版の帰着と困難性・完全性
5.4 ΝΡ-完全問題
5.5 Cook-Levinの定理の証明
5.6 様々なΝΡ-完全問題

第6章 基本的な計算量クラスとそれらの関係
6.1 基本的な計算量クラス
6.2 補集合の計算量クラスとImmerman-Szelepcenyiの定理
6.3 基本的な計算量クラスに対する完全性
6.4 神託付チューリング機械,チューリング帰着
6.5 多項式時間階層

第7章 おわりに
7.1 確率的な計算の例
7.2 確率計算の計算量クラス
7.3 対話型証明系とグラフ同型判定問題

参考文献
索引

サポート情報