内容紹介
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問題」に迫ります。
目次
- 第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問題の重要性
製品情報
製品名 | 「P≠NP」問題 現代数学の超難問 |
---|---|
著者名 | 著:野崎 昭弘 |
発売日 | 2015年09月18日 |
価格 | 定価 : 本体900円(税別) |
ISBN | 978-4-06-257933-9 |
通巻番号 | 1933 |
判型 | 新書 |
ページ数 | 224ページ |
シリーズ | ブルーバックス |
おすすめの本
-
電子あり
イラストで学ぶ ディープラーニング 改訂第2版
-
Rで学ぶ統計的データ解析
-
電子あり
絵でわかるネットワーク
-
電子のみ
講談社ブルーバックス通巻2000番記念小冊子
-
電子あり
多角形と多面体 図形が織りなす不思議世界
-
【Web-CAB・GAB Compact・IMAGES対応】 これが本当のCAB・GABだ! 2022年度版
-
電子あり
人間と機械のあいだ 心はどこにあるのか
-
電子あり
高校数学からはじめるディープラーニング 初歩からわかる人工知能が働くしくみ
-
カラー図解 Javaで始めるプログラミング 知識ゼロからの定番言語「超」入門
-
電子あり
イラストで学ぶ 情報理論の考え方
-
電子あり
サイバー攻撃 ネット世界の裏側で起きていること
-
電子あり
今度こそわかるP ≠ NP予想