忍者ブログ

I'm Standing on the Shoulders of Giants.

読んだ本から個人的に惹かれた部分を抜き出します。心理学およびその周辺領域を中心としています。 このBlogの主な目的は,自分の勉強と,出典情報付きの情報をネット上に残すことにあります。書誌情報が示されていますので,気になった一節が見つかったら,ぜひ出典元となった書籍をお読みください。

   

[PR]

×

[PR]上記の広告は3ヶ月以上新規記事投稿のないブログに表示されています。新しい記事を書く事で広告が消えます。

NP困難問題

計算機科学者の間で“うまく解ける”問題とは,問題の規模が10倍になっても,100倍ないし1000倍程度の時間をかければ解ける問題のことをいう。このような問題は,規模が100倍になれば計算量は1万倍以上になるが,計算機が10万倍速くなればたちどころに解ける。
 ところが,ごく当たり前の問題の中に,問題の規模が10倍になると,どのように工夫しても,2^10倍=1000倍の計算量が必要になると思われる,厄介な問題が存在することが明らかになったのである。
 規模が100倍なら計算量は2^100倍,すなわち10^30倍になる。計算機が100万(10^6)倍速くなっても,このような問題を普通のやり方で解こうとすると何兆年もかかる。しかも世の中は,このような“うまく解けない問題”,すなわち「NP困難問題」が溢れているというのである。
 この結果,わが国でも70年代に入ると,難しい問題を解くためのアルゴリズムや,ソフトウェア研究の重要性が認識されるようになった。京都大学,大阪大学,東京工業大学などの有力大学に,情報科学科・情報工学科・計算機科学科が出来たのはこの頃である。
 しかしどの大学も,その規模は一学科分(教官定員15人,学生定員40人程度)で,米国の有力大学に匹敵する“ソフトウェア中心の”計算機科学科は,どこにもなかった。政府・産業界・学界は,依然としてソフトウェアを軽視していたのである。

今野 浩 (2012). 工学部ヒラノ助教授の敗戦:日本のソフトウェアはなぜ敗れたのか 青土社 pp.16-17
PR

bitFlyer ビットコインを始めるなら安心・安全な取引所で

Copyright ©  -- I'm Standing on the Shoulders of Giants. --  All Rights Reserved
Design by CriCri / Photo by Geralt / powered by NINJA TOOLS / 忍者ブログ / [PR]