「honto 本の通販ストア」サービス終了及び外部通販ストア連携開始のお知らせ
詳細はこちらをご確認ください。
読割 50
または紙の本
「Ｐ≠ＮＰ」問題 現代数学の超難問 （ブルーバックス）
著者 野崎 昭弘 （著）
アルゴリズム、そして計算量の理論から生まれた多項式時間（Ｐ）で解けるとは、そして非決定多項式時間（ＮＰ）で解けるとはどういうことか。アルゴリズムと時間計算量の未解決問題、...
「Ｐ≠ＮＰ」問題 現代数学の超難問 （ブルーバックス）
「Ｐ≠ＮＰ」問題 現代数学の超難問
ワンステップ購入とは ワンステップ購入とは
このセットに含まれる商品
前へ戻る
- 対象はありません
次に進む
商品説明
アルゴリズム、そして計算量の理論から生まれた多項式時間（Ｐ）で解けるとは、そして非決定多項式時間（ＮＰ）で解けるとはどういうことか。アルゴリズムと時間計算量の未解決問題、Ｐ≠ＮＰ問題に迫る。【「TRC MARC」の商品解説】
20世紀、急速に進化・発展したコンピュータの世界。コンピュータに計算させるためのプログラム、その基になるアルゴリズムの理論が誕生した。アルゴリズム、そして計算量の理論から生まれた「多項式時間（P）で解ける」とは。そして、「非決定性多項式時間（NP）で解ける」とはどういうことか。ミレニアム問題の１つ、現在でも未解決の数学の難問を、コンピュータの歴史からさかのぼって説明します。
現代社会において、あらゆるところに利用され、なくてはならない存在のコンピュータ。遥か昔、計算をするためだけの道具だった計算機は、歴史とともに発展し、現代のコンピュータの姿となったが、いまでももの凄いスピードで進化し続けている。
このコンピュータの発展とともに生まれたのが、計算の方法・手順を考えるアルゴリズムの理論や、そして計算量の理論だ。計算の複雑さからアルゴリズムの評価が検討され、問題を解く上での基本ステップの実行回数から時間計算量が考えられてきた。
ある問題のアルゴリズムが作れたからといって、その問題がきれいに簡単に解けるのだろうか？ －－答えはＮＯだ。問題を解くアルゴリズムを作れたからといって、実際にコンピュータに計算させたら、果てしない時間（例えば地球の寿命を超えるような時間）がかかってしまうような問題もある。
「問題が解ける・解けない」「計算できる・計算できない」を考えたとき、問題の難易度によって、クラスＰの問題とかクラスＮＰの問題とかにクラス分けができる。このクラスＰとクラスＮＰが完全に一致するかどうかを決めるのが、Ｐ≠ＮＰ問題である。1971年以来、多くの数学者が挑戦し続けているが、Ｐ≠ＮＰ（ＰとＮＰが一致しない）であるか、Ｐ＝ＮＰ（ＰとＮＰが一致する）であるか、どちらも証明されていない。現代数学における未解決の超難問である。
本書は、コンピュータの歴史から、アルゴリズム理論、計算量理論を経て、「Ｐ≠ＮＰ問題」を丁寧に解説し、2000年にアメリカのクレイ研究所がミレニアム問題として懸賞金を懸けた7つの難問の一つ、「Ｐ≠ＮＰ問題」に迫ります。【商品解説】
目次
- 第0章 現代社会とコンピュータ
- 第1章 コンピュータとは何ものか
- 1-1 人間から歯車式コンピュータまで
- 1-2 現代の電子式コンピュータ
- 1-3 現代の電卓・コンピュータの使い方
- 第2章 コンピュータ科学の誕生
- 2-1 黎明期_計算可能性理論
- 2-2 ハードウエアの設計理論
- 第3章 アルゴリズムの理論
- 3-1 アルゴリズム理論の誕生
著者紹介
野崎 昭弘
- 略歴
- 〈野崎昭弘〉１９３６年横浜市生まれ。東京大学大学院数物系研究科修了。大妻女子大学名誉教授。専門はアルゴリズム理論、多値論理学、数学教育。著書に「離散数学「数え上げ理論」」など。
関連キーワード
あわせて読みたい本
前へ戻る
- 対象はありません
次に進む
この著者・アーティストの他の商品
前へ戻る
- 対象はありません
次に進む
紙の本
現代数学でも未だに未解決な問題をコンピュータの発展の歴史を追いながら追求していく画期的な一冊です！
2020/02/13 10:09
0人中、0人の方がこのレビューが役に立ったと投票しています。
投稿者：ちこ - この投稿者のレビュー一覧を見る
本書は、現代数学でも未解決の「多項式時間」と「非決定性多項式時間」との関係について書かれた一冊です。現代は、コンピューター技術が急速に進み、コンピュータで計算を行うためのアルゴリズムが確立されました。しかし、そのアルゴリズムから生まれた「多項式時間」である「P」と、「非決定性多項式時間」である「NP」が等しくないという数学上の難問が発生しました。同書では、この難問をコンピュータの発展の歴史をひも解きながら、解説した面白い一冊です。
