実際の店頭在庫とは異なることがございます。ご来店の際は事前にお電話にてお問い合わせください。
著者名 |
野崎昭弘 |
出版社 |
講談社 |
出版年月 |
2015年09月 |
参考価格 |
¥990 |
頁数 |
224p |
ISBN |
978-4-06-257933-9 |
内容 |
【要旨情報】 問題を解く鍵はアルゴリズムと時間計算量だ!20世紀、急速に進化・発展したコンピュータの世界。コンピュータに計算させるためのプログラム、その基になるアルゴリズムの理論が誕生した。アルゴリズム、そして計算量の理論から生まれた多項式時間(P)で解けるとは、そして、非決定性多項式時間(NP)で解けるとはどういうことか。
【e-honおすすめコメント】 現代社会において、あらゆるところに利用され、なくてはならない存在のコンピュータ。遥か昔、計算をするためだけの道具だった計算機は、歴史とともに発展し、現代のコンピュータの姿となったが、いまでももの凄いスピードで進化し続けている。このコンピュータの発展とともに生まれたのが、計算の方法・手順を考えるアルゴリズムの理論や、そして計算量の理論だ。計算の複雑さからアルゴリズムの評価が検討され、問題を解く上での基本ステップの実行回数から時間計算量が考えられてきた。ある問題のアルゴリズムが作れたからといって、その問題がきれいに簡単に解けるのだろうか? --答えはNOだ。問題を解くアルゴリズムを作れたからといって、実際にコンピュータに計算させたら、果てしない時間(例えば地球の寿命を超えるような時間)がかかってしまうような問題もある。「問題が解ける・解けない」「計算できる・計算できない」を考えたとき、問題の難易度によって、クラスPの問題とかクラスNPの問題とかにクラス分けができる。このクラスPとクラスNPが完全に一致するかどうかを決めるのが、P≠NP問題である。1971年以来、多くの数学者が挑戦し続けているが、P≠NP(PとNPが一致しない)であるか、P=NP(PとNPが一致する)であるか、どちらも証明されていない。現代数学における未解決の超難問である。本書は、コンピュータの歴史から、アルゴリズム理論、計算量理論を経て、「P≠NP問題」を丁寧に解説し、2000年にアメリカのクレイ研究所がミレニアム問題として懸賞金を懸けた7つの難問の一つ、「P≠NP問題」に迫ります。
>> もっと見る
<< 閉じる
|
目次 |
【目次】 第0章 現代社会とコンピュータ 第1章 コンピュータとは何ものか
第2章 コンピュータ科学の誕生 第3章 アルゴリズムの理論 第4章 P≠NP問題 第5章 おわりに
>> もっと見る
<< 閉じる
|
ジャンル |
新書 > 教養新書 > 教養新書 > ブルーバックス
|
※e-honは、株式会社トーハンが運営するオンライン書店です。
インターネットで注文した書籍を、宅配または三省堂書店の各店舗で受け取れます。
ご利用にあたっては、e-hon会員登録が必要です。