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



SGCライブラリ 43

臨時別冊・数理科学2005年11月
「アルゴリズムと計算量」
〜 Lectures on Computational Complexity 〜

谷 聖一(日本大学教授) 著

定価:2,006円(本体1,857円+税)
発行:サイエンス社
発行日:2005-11-25
JAN 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 対話型証明系とグラフ同型判定問題

参考文献
索引