アルゴリズム

アルゴリズム理論入門

岩間一雄

朝倉書店

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.最近のアルゴリズム理論―あとがきにかえて―

索引