BOOK SEARCH
アルゴリズム理論入門
岩間 一雄(著)
ネット書店で購入する amazon e-hon 紀伊國屋書店 honto Honya Club Rakutenブックス くまざわ書店
書店の店頭在庫を確認する 紀伊國屋書店
内容紹介
学部の専門科目でアルゴリズムや計算量理論を学ぶ人を対象とした入門書。事前の知識を前提せず，高校生でも問題なく理解できる構成となっている。「ちょっと面白い話」を多数挿入し，通読しやすくするために平易な記述に努めた。
編集部から
本書は（株）昭晃堂から発行していた書目を朝倉書店より再発行するものです。
目次
1.アルゴリズムを好きになっていただくために
天秤で偽コインを発見する／共通テストの順位を計算する／k 番めに大きい数をさがす／まとめと文献
2.計算機のモデルはあくまで数学モデルである
有限オートマトン／書き込み可能有限オートマトン／チューリング機械／乱アクセス機械／非決定性チューリング機械／まとめと文献
3.チューリング機械でチューリング機械を模倣する
チューリング機械の符号化と模倣／どんなTMによっても認識されない言語／書き込み可能faとTMの違い／必ず停止するTM／まとめと文献
4.計算機で解く「問題」とは何か
問題とは／問題の難しさ・易しさ／まとめと文献
5.計算機では解けない問題がある
非可解な問題／ポストの対応問題／まとめと文献
6.可解な問題は本当に解けるのか
時間限定チューリング機械／定数係数は重要か／計算時間の階層／まとめと文献
7.時間量だけでなく領域量も議論しよう
領域限定チューリング機械／領域量と並列計算／まとめと文献
8.計算困難性をいかにして証明するか
非決定性多項式時間／NP完全性／NP完全問題は沢山ある／まとめと文献
9.問題のクラスをもっと細分しよう
P完全性／近似可能性／近似不能な問題／NPより上のクラス／まとめと文献
10.最近のアルゴリズム理論―あとがきにかえて―
