ASCII.jpデジタル用語辞典の解説
出典 ASCII.jpデジタル用語辞典ASCII.jpデジタル用語辞典について 情報
出典 ASCII.jpデジタル用語辞典ASCII.jpデジタル用語辞典について 情報
(星野力 筑波大学名誉教授 / 2007年)
出典 (株)朝日新聞出版発行「知恵蔵」知恵蔵について 情報
出典 株式会社平凡社百科事典マイペディアについて 情報
出典 株式会社平凡社世界大百科事典 第2版について 情報
出典 ブリタニカ国際大百科事典 小項目事典ブリタニカ国際大百科事典 小項目事典について 情報
計算や問題解決の手順のこと。定められた手続に従って計算していけばいつかは答えが得られ、それが正解であることが保証されている手続である。最大公約数を求めるユークリッドの互除法などがその例。ただし計算量や記憶容量の問題を考えたときに、それが現実的に実行可能であることは意味しない。よくいわれるNP完全問題は、要素の数nに対して指数関数的に資源(計算時間や記憶容量のこと)が増加するので、計算時間が宇宙の寿命より長かったり、メモリー容量が宇宙の分子の数より大きかったりして、現実的には解けないことが多い。
したがってアルゴリズムは正解が求められるというだけでは不足で、その計算量が問題とされる。たとえば大量のデータを整列する(大きさの順とかアルファベット順とかで並べ替える)「ソート」のアルゴリズムは、要素数nに対しnlog(n)のオーダーで計算できるものが最善であり、場合によってはn2のものも多用されている。
人工知能(AI)などでは、ヒューリスティクスとよばれる擬似アルゴリズムが使われることが多い。これは、平均的には効率よく解を求められるが、場合によっては間違っていたり、最適の解ではなかったりすることがあるというものである。しかし、日常生活を送るうえではこれで十分なことが多い。たとえば、カーナビゲーションで経路探索を行った場合、最短経路より数%長い探索結果が出てしまうことなどは許容されるであろう(実際、交通状況に依存するので、カーナビの最短経路がもっとも早いとは限らない)。
また、多くの都市をどの順で回れば最適かという「巡回セールスマン問題」の最適解を求めるにはn!に比例する時間がかかり、20都市程度でも現実的な計算はできない。
一般的に計算量が膨大になる問題でも、最適解でなくてよければ、現実的に計算可能なヒューリスティクスはいくつかある。ニューラルネットワークを使って近似解を求める方法も知られている。
[中島秀之 2019年7月19日]
出典 精選版 日本国語大辞典精選版 日本国語大辞典について 情報
…アルゴリズムの計算効率や問題の難しさを測るための尺度。主なものに,時間効率を測るための時間計算量,メモリー効率を測るための領域計算量などがある。…
…アラル海の南ホラズムの出身で,アッバース朝のカリフ,マームーン治下のバグダードで活躍した。われわれが今日用いているアラビア数字は,彼がインドから導入したもので,アラビア記数法やそれに基づく計算を意味する〈アルゴリズム〉という語は,彼の名前が転訛したものである。彼の著作のうち最も有名なものは《代数学》で,これはアラビア数学の嚆矢をなすばかりでなく,後のヨーロッパに初めて代数というものの存在を教えたものであることは,アルジェブラalgebra(代数学)という語がこの本の書名の一部al‐jabr(移項して負の項をなくす操作)に由来することからもわかる。…
※「アルゴリズム」について言及している用語解説の一部を掲載しています。
出典|株式会社平凡社世界大百科事典 第2版について | 情報
《「ノブレスオブリージュ」とも》身分の高い者はそれに応じて果たさねばならぬ社会的責任と義務があるという、欧米社会における基本的な道徳観。もとはフランスのことわざで「貴族たるもの、身分にふさわしい振る舞...
12/21 デジタル大辞泉を更新
12/21 デジタル大辞泉プラスを更新
12/10 日本大百科全書(ニッポニカ)を更新
10/28 デジタル大辞泉を更新
10/28 デジタル大辞泉プラスを更新
10/27 日本大百科全書(ニッポニカ)を更新