野崎昭弘

Individuals/organizations Page

Books

P≠np問題とは何か ブルーバックス

野崎昭弘

☆
☆
☆
☆
☆
Write review 

Product Details

Genre
：
Sciences&Physics
ISBN/Catalogue Number
：
ISBN 13 : 9784062579339
ISBN 10 : 4062579332
Format
：
Books
Publisher
：
Kodansha
Release Date
：
September/2015
Release Country
：
Japan
Co-Writer, Translator, Featured Individuals/organizations
:
野崎昭弘 ,  

Content Description

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

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

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

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


【著者紹介】
野崎昭弘 : １９３６年、横浜市生まれ。東京大学理学部数学科卒業、同大学院数物系研究科修了。電電公社（現ＮＴＴ）電気通信研究所、東京大学教養学部、同理学部、山梨大学工学部、国際基督教大学教養学部、大妻女子大学社会情報学部、サイバー大学ＩＴ総合学部教授を経て、大妻女子大学名誉教授。専門はアルゴリズム理論、多値論理学、数学教育。『ゲーデル、エッシャー、バッハ』（共訳・白揚社、第２２回日本翻訳文化賞受賞）など、著書・和訳多数。第３回日本数学会出版賞受賞（本データはこの書籍が刊行された当時に掲載されていたものです）

（「BOOK」データベースより）

Customer Reviews

Comprehensive Evaluation

☆
☆
☆
☆
☆

0.0

★
★
★
★
★
 
0
★
★
★
★
☆
 
0
★
★
★
☆
☆
 
0
★
★
☆
☆
☆
 
0
★
☆
☆
☆
☆
 
0
Write you own review

Book Meter Reviews

こちらは読書メーターで書かれたレビューとなります。

powered by

  • ちくわん

    読了日：2018/10/13

    コンピューターは詳しいので、高速読み。ハルトマニスの「全員攻撃」発言が、この問題の難しさをあらわす。私の予想では、近いうちにインド関連が解決するだろう。さて、野崎先生が、本書を書くきっかけになった「一般向けの、実にひどい解説書」を探してみるか。

  • Satoshi

    読了日：2020/02/09

    PNP問題についての解説書かと思えば、前半は計算機科学の説明に費やされており、少し期待外れ。NPについて、少し解った気になれた。

  • とりもり

    読了日：2016/01/21

    他の暗号本で「P≠NP」問題に興味を持って読んでみたが、あまり良い本とは言えなかった。先ず、前半部分が冗長過ぎて、肝心の「P≠NP」問題の解説が詳しいとは言えない。正直、半分程度は著者の趣味の記述で、本題の理解には不要という気がする。それなら、本題の解説をもっと充実させて欲しかったというのが、偽らざる感想。この問題には関心があるが、がっつりロジックを追って理解するほどの時間はないので、もう少し手頃な本はないかな〜と思う。★★☆☆☆

  • トルネードＧ＆Ｔ

    読了日：2016/03/06

    アルゴリズム（プログラミング）における計算速度の目安となる「計算量」がどの程度であるのか、という学問領域における「まあまあ早く問題」と「そこそこ早く解ける問題」の差を求めようとする話。本文内で難易度わけがされており初心者は難しい部分を読み飛ばしてざっくりと内容を理解でき、上級者はある程度踏み込んだところまで理解を深められるような構造になっている。肝心の「P≠NP」の話は前書きで筆者も宣言しているようにほんの一部で大部分はそこに至るまでの前提知識の紹介となっているためざっくりとアルゴリズムについても学べる。

  • まえぞう

    読了日：2016/01/09

    有名な問題のひとつで、何のことかわからなかった話の概要が何となく理解できました。コンピューターサイエンスでは重要な話しなんでしょうが、説明は抽象的でついていくのが大変です。

レビューをもっと見る

(外部サイト)に移動します

Recommend Items

Sell This Item