アルゴリズム理論入門

内容紹介

本書は学部の専門科目でアルゴリズムや計算量理論を学ぶ人を対象とした入門書である．事前の知識を前提としておらず，高校生でも問題なく理解できる構成となっている．「ちょっと面白い話」を頻繁に挿入し，厳密性を犠牲にしても平易な記述に努めた．一つか二つの誤解よりも途中で投げ出す危険を恐れたためである．自信を持ってお薦めする．

目次

1. アルゴリズムを好きになっていただくために

   天秤で偽コインを発見する／共通テストの順位を計算する／k 番めに大きい数をさがす／まとめと文献

2. 計算機のモデルはあくまで数学モデルである

   有限オートマトン／書き込み可能有限オートマトン／チューリング機械／乱アクセス機械／非決定性チューリング機械／まとめと文献

3. チューリング機械でチューリング機械を模倣する

   チューリング機械の符号化と模倣／どんなTMによっても認識されない言語／書き込み可能faとTMの違い／必ず停止するTM／まとめと文献

4. 計算機で解く「問題」とは何か

   問題とは／問題の難しさ・易しさ／まとめと文献

5. 計算機では解けない問題がある

   非可解な問題／ポストの対応問題／まとめと文献

6. 可解な問題は本当に解けるのか

   時間限定チューリング機械／定数係数は重要か／計算時間の階層／まとめと文献

7. 時間量だけでなく領域量も議論しよう

   領域限定チューリング機械／領域量と並列計算／まとめと文献

8. 計算困難性をいかにして証明するか

   非決定性多項式時間／NP完全性／NP完全問題は沢山ある／まとめと文献

9. 問題のクラスをもっと細分しよう

   P完全性／近似可能性／近似不能な問題／NPより上のクラス／まとめと文献

10. 最近のアルゴリズム理論―あとがきにかえて―