計算できるもの、計算できないもの

―実践的アプローチによる計算理論入門

[cover photo]
TOPICS
Math
発行年月日
PRINT LENGTH
420
ISBN
978-4-87311-933-5
原書
What Can Be Computed?
FORMAT
Print PDF
Ebook
5,060円
Ebookを購入する
Print
5,060円

計算機による計算とは何か、計算できるものとできないものの境界はどこにあるのか―それを明らかにする計算理論は、計算機科学においてもっとも基本的、かつ重要なものです。本書では、概念の説明や、結果の証明にPythonプログラムを利用する実践的なアプローチにより、計算可能問題と計算不能問題、扱いやすい問題と扱いにくい問題があること、文章では簡単に表現できても計算機には解けない重要な問題が数多くあること、効率よく解ける問題と解けない問題があることなどを、計算理論の礎を築いたアラン・チューリングとリチャード・カープの論文の抜粋とともに解明します。チューリングマシン、有限オートマトン、万能計算、非決定性、チューリング還元、計算量クラス、NP完全性などのトピックをカバーしています。

目次

謝辞
まえがき:教科書として使う方へ
全体像

1章 はじめに:計算できるもの, できないものとは
    1.1 扱いやすい問題
    1.2 扱いにくい問題
    1.3 計算不能問題
    1.4 本書の内容についてのもう少し詳しい説明
    1.5 本書を理解するために必要な予備知識
    1.6 本書の目標
    1.7 なぜ計算理論を学ぶのか
    演習問題

第 I 部 計算可能性理論

2章 コンピュータプログラムとは何か
    2.1 Python プログラムの初歩的な知識
    2.2 文字列入出力(SISO) Python プログラム
    2.3 ASCII 文字と複数行文字列
    2.4 問題のあるプログラム
    2.5 Python プログラムの形式的な定義
    2.6 判定プログラムとプログラムの等価性
    2.7 現実のプログラムと SISO Python プログラムの比較
    演習問題

3章 不可能な Python プログラム
    3.1 背理法
    3.2 ほかのプログラムを解析するプログラム
    3.3 プログラム yesOnString.py
    3.4 プログラム yesOnSelf.py
    3.5 プログラム notYesOnSelf.py
    3.6 yesOnString.py も存在し得ない
    3.7 完璧なバグ検出プログラムは存在し得ない
    3.8 それでもバグは見つけられるが, 完璧に見つけることはできない
    演習問題

4章 計算問題とは何か
    4.1 グラフ, アルファベット, 文字列, 言語
    4.2 計算問題の定義
    4.3 計算問題のカテゴリー
    4.4 問題を「解く」ことの形式的な定義
    4.5 言語の認識と判定
    演習問題

5章 チューリングマシン:もっとも単純なコンピュータ
    5.1 チューリングマシンの定義
    5.2 少し複雑なチューリングマシン
    5.3 シングルテープチューリングマシンからマルチテープチューリングマシンへ
    5.4 マルチテープチューリングマシンから Python プログラム, さらにその先へ
    5.5 逆方向: Python でチューリングマシンをシミュレートする
    5.6 古典的コンピュータは, 量子コンピュータをシミュレートできる
    5.7 すべての既知のコンピュータはチューリング等価である
    演習問題

6章 万能コンピュータプログラム
    6.1 万能 Python プログラム
    6.2 万能チューリングマシン
    6.3 実世界における万能計算
    6.4 ほかのプログラムを書き換えるプログラム
    6.5 決定不能だが認識可能な問題
    演習問題

7章 還元:問題が難しいことを証明する方法
    7.1 やさしいことを示すための還元
    7.2 難しいことを示すための還元
    7.3 チューリング還元の形式的な定義
    7.4 チューリング還元の性質
    7.5 計算不能問題の多さ
    7.6 その他の計算不能問題
    7.7 プログラムに関する問題以外の計算不能問題
    7.8 プログラムについての問いがすべて計算不能なわけではない
    7.9 計算不能性の証明テクニック
    演習問題

8章 非決定性:手品か現実か
    8.1 非決定性 Python プログラム
    8.2 非判定問題における非決定性プログラム
    8.3 計算木
    8.4 何が計算可能かは非決定性によっては変わらない
    8.5 非決定性チューリングマシン
    8.6 非決定性チューリングマシンの形式的な定義
    8.7 非決定性のモデル
    8.8 認識不能問題
    8.9 非決定性を研究するのはなぜか
    演習問題

9章 有限オートマトン:限られた資源による計算
    9.1 決定性有限オートマトン(DFA)
    9.2 非決定性有限オートマトン(NFA)
    9.3 NFA と DFA の等価性
    9.4 正規表現 
    9.5 正規言語ではない言語もある
    9.6 正規言語ではないその他の言語
    9.7 正規言語の結合
    演習問題

第 II 部 計算量理論

10章 計算量理論:効率が重視されるとき
    10.1 計算量理論は漸近実行時間を使う
    10.2 ビッグオー記法
    10.3 プログラムの実行時間
    10.4 時間計算量を評価するための基礎
    10.5 計算量では計算モデルが意味を持つ
    10.6 計算量クラス
    演習問題

11章 クラス Poly とクラス Expo :もっとも根本的な2つの計算量クラス
    11.1 クラス Poly とクラス Expo の定義
    11.2 クラス Poly はクラス Expo の部分集合である
    11.3 クラス Poly とクラス Expo の境界についての最初の考察
    11.4 クラス Poly とクラス Expo は計算モデルを選ばない
    11.5 HaltEx 問題:クラス Expo に属するがクラス Poly に属さない判定問題
    11.6 クラス Poly に属さないその他の問題
    11.7 入力の不合理な符号化方法は計算量に影響を与える
    11.8 ではなぜクラス Poly を研究するのか
    演習問題

12章 クラス PolyCheck とクラス NPoly :簡単に検証できる難しい問題
    12.1 検証器
    12.2 多項式時間検証器
    12.3 計算量クラス PolyCheck
    12.4 計算量クラス NPoly
    12.5 クラス PolyCheck とクラス NPoly は同じ
    12.6 PolyCheck/NPoly のサンドイッチ
    12.7 効率よく計算できるものが何かは非決定性によって変わるようだ
    12.8 クラス NPoly についての但書
    演習問題

13章 多項式時間写像還元: X は Y と同じくらいやさしいことの証明
    13.1 多項式時間写像還元の定義
    13.2 多項式時間写像還元の意味
    13.3 多項式時間還元のための証明テクニック
    13.4 ハミルトン閉路での多項式時間還元の例
    13.5 3 つの充足可能性問題(CircuitSat, Sat, 3-Sat)
    13.6 CircuitSat, Sat, 3-Sat の間での多項式時間還元
    13.7 多項式時間等価とその意味
    演習問題

14章 NP 完全性:もっとも難しい問題の難しさの程度は同じである
    14.1 P ‰ NP 問題
    14.2 NP 完全性
    14.3 NP 困難性
    14.4 P = NP ならどうなるか
    14.5 CircuitSat 問題は「もっとも難しい」 NP 問題の 1 つである
    14.6 NP 完全性は遍在している
    14.7 NP 完全性の証明テクニック
    14.8 NP 完全についての良い話と悪い話
    演習問題

第 III 部 起源と応用

15章 もともとのチューリングマシン
    15.1 チューリングの「計算機械」の定義
    15.2 機械は人間が計算できるものを計算できる
    15.3 チャーチ – チューリングの提唱:自然法則?
    演習問題

16章 正しいことをすべて証明できるとは限らない
    16.1 機械による証明
    16.2 論理系としての算術
    16.3 数学の決定不能性 16.4 数学の不完全性
    16.5 私たちが学んだことは何か, なぜそれを学んだのか
    演習問題

17章 カープの 21 個の問題
    17.1 カープ論文の全体像
    17.2 カープの NP 完全性の定義
    17.3 21 種類の NP 完全問題のリスト
    17.4 21 種類の NP 完全問題の間の還元
    17.5 論文の最後の部分: NP 困難性
    演習問題

18章 結論:何が計算されるようになるか
    18.1 計算できるものは何かという問いにまつわる重要ポイント

参考文献
索引