アルゴリズム理論入門
朝倉書店
著者：岩間一雄
1.アルゴリズムを好きになっていただくために
1.1 天秤で偽コインを発見する
1.2 共通テストの順位を計算する
1.3 k 番めに大きい数をさがす
1.4 まとめと文献
2.計算機のモデルはあくまで数学モデルである
2.1 有限オートマトン
2.2 書き込み可能有限オートマトン
2.3 チューリング機械
2.4 乱アクセス機械
2.5 非決定性チューリング機械
2.6 まとめと文献
3.チューリング機械でチューリング機械を模倣する
3.1 チューリング機械の符号化と模倣
3.2 どんなTMによっても認識されない言語
3.3 書き込み可能faとTMの違い
3.4 必ず停止するTM
3.5 まとめと文献
4.計算機で解く「問題」とは何か
4.1 問題とは
4.2 問題の難しさ・易しさ
4.3 まとめと文献
5.計算機では解けない問題がある
5.1 非可解な問題
5.2 ポストの対応問題
5.3 まとめと文献
6.可解な問題は本当に解けるのか
6.1 時間限定チューリング機械
6.2 定数係数は重要か
6.3 計算時間の階層
6.4 まとめと文献
7.時間量だけでなく領域量も議論しよう
7.1 領域限定チューリング機械
7.2 領域量と並列計算
7.3 まとめと文献
8.計算困難性をいかにして証明するか
8.1 非決定性多項式時間
8.2 NP完全性
8.3 NP完全問題は沢山ある
8.4 まとめと文献
9.問題のクラスをもっと細分しよう
9.1 P完全性
9.2 近似可能性
9.3 近似不能な問題
9.4 NPより上のクラス
9.5 まとめと文献
10.最近のアルゴリズム理論―あとがきにかえて―
索引