書籍
書籍

「P≠NP」問題 現代数学の超難問

0.0

販売価格

¥
990
税込
還元ポイント
9pt

・在庫状況 について

在庫表示と発送目安について
この商品を出品する
店舗取り置きサービスについて
この商品のコレクション情報を確認する
コレクション機能とは？
フォーマット 書籍
発売日 2015年09月18日
国内/輸入 国内
出版社講談社
構成数 1
パッケージ仕様 新書
SKU 9784062579339
ページ数 224
判型 新書

構成数 : 1枚

第0章 現代社会とコンピュータ
第1章 コンピュータとは何ものか
1-1 人間から歯車式コンピュータまで
1-2 現代の電子式コンピュータ
1-3 現代の電卓・コンピュータの使い方
第2章 コンピュータ科学の誕生
2-1 黎明期_計算可能性理論
2-2 ハードウエアの設計理論
第3章 アルゴリズムの理論
3-1 アルゴリズム理論の誕生
3-2 アルゴリズム理論の展開_計算量理論
3-3 アルゴリズム理論の題材
3-4 アルゴリズム理論の成果
第4章 P≠NP問題
4-1 "NP"の登場
4-2 P≠NP問題
第5章 おわりに
5-1 歴史を少々
5-2 P≠NP問題のむずかしさ
5-3 P≠NP問題を巡る、さまざまな展開
5-4 P≠NP問題の重要性

  1. 1.[書籍]

20世紀、急速に進化・発展したコンピュータの世界。コンピュータに計算させるためのプログラム、その基になるアルゴリズムの理論が誕生した。アルゴリズム、そして計算量の理論から生まれた「多項式時間(P)で解ける」とは。そして、「非決定性多項式時間(NP)で解ける」とはどういうことか。ミレニアム問題の1つ、現在でも未解決の数学の難問を、コンピュータの歴史からさかのぼって説明します。


現代社会において、あらゆるところに利用され、なくてはならない存在のコンピュータ。遥か昔、計算をするためだけの道具だった計算機は、歴史とともに発展し、現代のコンピュータの姿となったが、いまでももの凄いスピードで進化し続けている。

このコンピュータの発展とともに生まれたのが、計算の方法・手順を考えるアルゴリズムの理論や、そして計算量の理論だ。計算の複雑さからアルゴリズムの評価が検討され、問題を解く上での基本ステップの実行回数から時間計算量が考えられてきた。
ある問題のアルゴリズムが作れたからといって、その問題がきれいに簡単に解けるのだろうか? --答えはNOだ。問題を解くアルゴリズムを作れたからといって、実際にコンピュータに計算させたら、果てしない時間(例えば地球の寿命を超えるような時間)がかかってしまうような問題もある。

「問題が解ける・解けない」「計算できる・計算できない」を考えたとき、問題の難易度によって、クラスPの問題とかクラスNPの問題とかにクラス分けができる。このクラスPとクラスNPが完全に一致するかどうかを決めるのが、P≠NP問題である。1971年以来、多くの数学者が挑戦し続けているが、P≠NP(PとNPが一致しない)であるか、P=NP(PとNPが一致する)であるか、どちらも証明されていない。現代数学における未解決の超難問である。

本書は、コンピュータの歴史から、アルゴリズム理論、計算量理論を経て、「P≠NP問題」を丁寧に解説し、2000年にアメリカのクレイ研究所がミレニアム問題として懸賞金を懸けた7つの難問の一つ、「P≠NP問題」に迫ります。

作品の情報

メイン
著者： 野崎昭弘

メンバーズレビュー

レビューを書いてみませんか？

読み込み中にエラーが発生しました。

画面をリロードして、再読み込みしてください。