アルゴリズムと計算量

書影

SGCライブラリ  43

臨時別冊・数理科学2005年11月

アルゴリズムと計算量

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

発行日:2005年11月25日

発行:サイエンス社

ISBN:4910054701159

サイズ:並製B5

ページ数:160ページ

在庫:品切れ

内容詳細

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

目次

第1章 はじめに
1.1 アルゴリズムって何
1.2 アルゴリズムの性能\r
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 帰着と決定不能問題\r

第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 対話型証明系とグラフ同型判定問題

参考文献
索引


サポート情報

その他

電子版のご案内


臨時別冊数理科学 SGCライブラリ 43
「アルゴリズムと計算量」 サポートページ


関連書籍