アルゴリズム

Pocket

アルゴリズム、P≠NP問題

現代社会で重要な役割を果たすアルゴリズム
「アルゴリズム」というのは、一般的に言えば「問題を解く手続き」のことを言うが、通常は、コンピュータのプログラムの形で書かれた計算手続きのことを指す。
ジョン・マコーミック (長尾高弘訳)、『世界でもっとも強力な9のアルゴリズム』(日経BP社、2012年7月)は、検索、暗号、データベースなどに関連するいくつかの具体的なアルゴリズムを、きわめて平易に解説している。
これらは、いずれも現代の経済活動に不可欠なアルゴリズムだ。とくに、「公開鍵暗号」(第4章)、「誤り訂正符号」(第5章)、デジタル署名(第9章)は、eコマースにおける取引で不可欠のものだ。
しかし、こうした技術は1970年代以降に開発された比較的新しいものであるため、学校でも教えていない。本書は、サイモン・シン (青木 薫訳)『暗号解読』、上、下、新潮文庫、 2007年6月)と並んで、専門家でない者がアイディアの概略を知るには適切な入門書だ。

クリストファー・スタイナー (永峯 涼訳)、『アルゴリズムは世界を支配する』(角川EPUB選書)は、いくつかの興味深いアルゴリズムについて具体的に説明している。
第3章『ボット・トップ40』で、音楽がヒットするかどうかを判断するアルゴリズムが紹介されている。また、バッハの音楽を分析して、感動的な曲を作り出したアルゴリズムの話も紹介されている。大変興味深い。

イアン・エアーズ(山形 浩生訳)、『 その数学が戦略を決める』 (文春文庫、2010年6月)には、脚本だけで映画の興行成績を予測するアルゴリズム「エパコギクス」が紹介されている。
このアルゴリズムは、従来のような回帰方程式で予測をするのではなく、「ニューラル・ネットワーク」という人間の脳を真似た仕組みで予測を行なうのである。これについても、簡単な説明がある。

P≠NP問題
アルゴリズムに関して原理的に問題となるのは、「解があることが分かっている問題は、有限時間の計算で実際に解けるのか?」ということである。あるいは、「効率的なアルゴリズムがある問題(クラスP)は、答えが正しいことを容易に確かめられる問題(クラスNP)と同じか?」という問題である。これは、P=NP問題、またはP≠NP問題と呼ばれている。これは現代数学の大問題である

これに関する研究を行なったのが天才的数学者アラン・チューグだ。B・ジャック・コープランド (服部 桂訳)、『チューリング』(エヌティティ出版、2013年12月)は、チューリングの伝記。
彼が考え出した「チューリング・マシン」という仮想機械は、「問題を数学的に解くことができるか?」を検証しようとするものだ。彼は第2次大戦中、イギリスの暗号解読チームに属していた。そして第2次大戦中の対Uボート作戦(ドイツの暗号「エニグマ」の解読作戦)に参加し、中心的な役割を果たした。こうした事情もあって、謎に包まれた人物だった。『チューリング』は、戦後の業績も含めて、彼の足跡を紹介している。

ウィリアム・J・クック( 松浦俊輔訳)『 驚きの数学 巡回セールスマン問題 』(青土社、2013年5月)も、P≠NP問題を論じている。これは、正解を算出するための効率的なアルゴリズムがいまだに見つかっていない問題なのである。

デイヴィッド・バーリンスキ(林 大訳)『 史上最大の発明アルゴリズム: 現代社会を造りあげた根本原理』(ハヤカワ文庫NF―数理を愉しむシリーズ、NF 381、2012年4月)は、この問題を基礎論的観点から論じている。
ただし、あまり具体的な話ではないので、実務に興味のある人には、向かないかもしれない。

『素数の音楽』は、「リーマン予想」と呼ばれる数論(整数論)の問題を解説している。
これは、「一見したところまったく出鱈目に並んでいるように見える素数が、ある側面から見れば規則的に並んでいるのではないか?」という予想である。数学者ベルンハルト・リーマンが19世紀半ばに提起したものだ。それはいまに至るまで証明されていない数学の難問の一つだ。リーマン予想は、日常生活とはまったく関係がない純粋数学の問題と考えられてきたのだが、eコマースとの関係で注目されるようになった。なぜなら、リーマン予想予想もP≠NP問題にかかわっているからだ。素因数分解問題は、解があると分かっている問題である。しかし、効率的なアルゴリズムは発見されておらず、しらみつぶしに試すしか方法がない。仮にリーマン予想が正しく、素因数分解問題を解く効率的なアルゴリズムが発見されれば、eコマースの基礎である公開鍵暗号が破れてしまい、現代社会の基盤が覆されるかもしれない。

カテゴリー: 未分類 パーマリンク