アルゴリズムとは?

Weblio 辞書 > 同じ種類の言葉 > 情報 > コンピュータ > アルゴリズム > アルゴリズムの意味・解説 

アルゴリズム [4] 【algorithm】

〔もとは算用数字を用いた筆算のこと。アラビアの数学アル=フワリズミの名にちなむ〕
計算問題解決するための手順,方式

アルゴリズム

読み方あるごりずむ
【英】:algorithm

概要

その実行が必ず有限ステップ停止する有限個の機械的操作の列のこと. ここで, 機械的操作とは, 計算機基本命令考え良い. ORにおいては, 定式化した問題に対し具体的に解を求めて現実適用する必要があるので, 問題の解を得る効率良いアルゴリズムを求めることは非常に重要である. アルゴリズムの代表的設計法としては, 貪欲法(greedy), 2分探索, 動的計画, 分割統治等がある.

詳説

 アルゴリズム (algorithm) とは, その実行が必ず有限ステップ停止する有限個の機械的操作の列のことであり, 算法とも訳される.ここで, 機械的操作とは, 計算機基本命令の列と考え良い. この名称は, 9世紀アラビア代数学者, フワーリズミー (al-Khwarizmi) に由来する.数学研究においては, 問題に対して解を構成する手順求め接近法と, 解の存在証明する接近法とが典型的であるが, 前者の, 解を求め手順のうち有限ステップ停止するものがアルゴリズムである. ユークリッド(Euclid) の互除法, 定規とコンパスによる作図, 高次方程式解法等, 古くよりアルゴリズムを求め研究がなされてきた. その中で, アルゴリズムの概念厳密に定義する必要性が, 1900年提唱されたヒルベルト(D. Hilbert) の第10問題, すなわち, 不定不等式有理整数解の存在判定するアルゴリズムを求め問題以来, 次第に明確に意識されるようになり, 1930年代至ってチューリング (A. M. Turing), チャーチ (A. Church), クリーネ (S. C. Kleene) によってそれぞれ異なった計算モデル用いてアルゴリズムの厳密な定義がなされた. それらは, 等価であることが知られている. 特に, チューリングによりそれを解くアルゴリズムが存在しない問題があること (チューリング機械停止問題, halting problem for Turing machines) が示されたことの意義大きい.

 アルゴリズムの設計法は, 1940年代電子計算機出現とともに精力的研究されてきた. 巡回セールスマン問題 (traveling salesman problem) 等, 原理的有限ステップでは解けるが, 現実的時間で解くアルゴリズムを作るのが困難な問題があることが知られるにつれ, 次第計算の複雑さ (computational complexity) への認識が高まってきた. 一般に, 実行時間入力サイズ多項式時間 (polynomial time) 以下のアルゴリズムを効率良いアルゴリズムという. 1971年クック (S. A. Cook) によりNP困難性 (NP-hardness, 計算の複雑さ参照) の概念導入され, それ以来, カープ (R. Karp) を始め多く研究者によって, 巡回セールスマン問題等, 組合せ最適化問題 (combinatorial optimizationproblem) を含む幾多問題NP困難であることが証明されてきた. あるNP困難問題対す多項式時間のアルゴリズムがあれば, 従来多項式時間のアルゴリズムを作るのが困難と思われてきた多く問題に対して多項式時間アルゴリズム構成できる.しかしながら, それはほとんどありえないことから, NP困難問題に対して多項式時間アルゴリズム存在しないと信じられている.

 与えられた問題に対して効率良いアルゴリズムを開発するには,

問題構造対する深い洞察
・アルゴリズム設計技法知識

が必要である.

 代表的なアルゴリズム設計技法としては以下のものが知られている.

貪欲アルゴリズム (greedy, 欲張り法ともいう) : 解の構成要素を, 効果のあるものから順に選択していく.

 例: 最小木問題 (minimum spanning tree) に対すクラスカル (J. B. Kruskal Jr.) のアルゴリズム, その他, 近似アルゴリズム (approximation algorithm) としても良く用いられる.

2分探索 (binary search): 予めソートされた列中で, ある要素探す. 中央の要素比較し, それよりも大きいか, 小さいかを調べ, ソート列中のどちら側にあるかを知る. 一回反復毎に要素数が半分下になるので, \log\, (ソート列中の要素数) 回の比較求まる.

 例: 辞書中での単語検索.

分割統治(divide and conquer): 解くべき問題小規模部分問題分割して解き, 部分問題の解を統合することで全体の解を得ようとする方法. これは, 逐次のみならず並列アルゴリズム設計においても基本的方法である.
動的計画 (dynamic programming):「最適方策(optimal policy) は, それまで決定どのようであろうとも, それ以降最適決定を下さなければならない. (R. Bellman)」という, 最適性の原理 (principles of optimality) に基づく. アルゴリズム的観点から見ると, 一度計算した結果記憶しておくことで冗長な計算避け方法である. 最短路問題 (shortest path problem) に対す各種アルゴリズム等, グラフ・ネットワーク問題 (graph and network problems), および, 組合せ最適化問題において多く応用例がある.

 問題良い構造をもつと効率良いアルゴリズムを設計することが可能となる. 特に, 貪欲アルゴリズムがうまく適用できる問題構造については, マトロイド (matroid) の項目を, その他, グラフ・ネットワークの構造を持つ問題効率良いアルゴリズムが存在するものについては, グラフ・ネットワーク, グラフ連結度 (connectivity), ネットワークフロー問題 (network flow problem), マッチング問題 (matching problems) 等の項目を, また, 組合せ最適化問題について, その他, 劣モジュラ最適化 (submodular optimization), 離散凸解析 (discrete convexanalysis) 等の項目を参照されたい. また, データ構造 (data structure) を工夫することで効率良いアルゴリズムを設計できる場合が多い.

 なお, アルゴリズムの実行時にデータ次々入力され, 実行前に入力されるデータ未知であるアルゴリズムをオンラインアルゴリズム (online algorithm) という. オンラインアルゴリズムいくつかの例が [1] にある. また, これまでは, 逐次かつ決定的アルゴリズムを論じてきたが, 実行確率動作導入した確率アルゴリズム (probabilistic algorithm, または, ramdomized algorithm), 複数プロセッサ上で並列アルゴリズム (parallel algorithm), および, 分散環境下での複数計算機間に跨る計算に関する分散アルゴリズム (distributed algorithm) については, それぞれの用語解説, 及び, 並列アルゴリズムについては, [5, 9, 15, 16] を, 分散アルゴリズムについては, [10, 14, 19] を参照されたい. 文献[3] は, 連立1次方程式解法, 逆行列計算から始め, 非線形最適化 (nonlinear optimization), ネットワーク最適化 (networkoptimization) 等に関連した多様な並列, ないし, 分散アルゴリズムを扱っており, OR関係者にとって便利である. なお, 紙数の関係で本中項目では離散的対象に関する厳密に解を求めるアルゴリズムに話題を限ったが, 線形計画 (linear programming), 非線形計画 (nonlinear programming) 等, 各種数理計画に関するアルゴリズムについては, それぞれ該当する項目を参照されたい. また, NP困難問題に対して良い実行可能解 (feasible solution) を現実的に求め近似アルゴリズムやその枠組であるメタヒューリスティックス (metaheurisitics) についても, それぞれ該当する項目を参照されたい.



参考文献

[1] A. V. Aho, J. E. Hopcroft and J. D. Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley, 1974; 野崎昭弘, 野下浩平共訳,『アルゴリズムの設計解析I, II』, サイエンス社, 1977.

[2] 浅野孝夫, 今井浩, 『計算とアルゴリズム-計算機科学-』, オーム社, 1986.

[3] D. P. Bertsekas, J. Tsitsiklis, Parallel and Distributed Computation, Prentice-Hall, 1989.

[4] T. H. Cormen, C. E. Leiserson, R. L. Rivest, Introduction to Algorithms, MIT Press, 1990; 浅野哲夫, 岩野和生, 尾博司, 山下雅史, 和田幸一訳,『アルゴリズムイントロダクション』, 第1-3巻, 近代科学社, 1995.

[5] A. Gibbons, W. Rytter, Efficient Parallel Algorithms, Cambridge University Press, 1988.

[6] 平田富夫,『アルゴリズムとデータ構造』, 森北出版, 1990.

[7] 茨木俊秀,『アルゴリズムとデータ構造』, 昭晃堂, 1989.

[8] 石畑清,『アルゴリズムとデータ構造』, 岩波書店, 1989.

[9] J. Jáá, An Introduction to Parallel Algorithms, Addison-Wesley, 1992.

[10] 亀田恒彦, 山下雅史,『分散アルゴリズム』, 近代科学社, 1994.

[11] D. E. Knuth, The Art of Computer Programming, Vol.I, Addison-Wesley, 1973; 広瀬健訳,『基本算法 / 基礎概念』, サイエンス社, 1978, および, 米田信夫, 筧捷彦訳, 『基本算法 / 情報構造』, サイエンス社, 1978.

[12] D. E. Knuth, The Art of Computer Programming, Vol.II, Addison-Wesley, 1981; 渋谷正昭訳,『準数値算法 / 乱数』, サイエンス社, 1981, および, 中川圭介訳, 『準数値算法 / 算術演算』, サイエンス社, 1986.

[13] Jan van Leeuwen ed., Handbook of Theoretical Computer Science Vol.A: Algorithms and Complexity, Elsevier Science B. V., 1990; 廣瀬健, 野崎昭弘, 小林次郎監訳,『コンピュータ基礎理論ハンドブックI, アルゴリズムと複雑さ』, 丸善, 1994.

[14] N. A. Lynch, Distributed Algorithms, Morgan Kaufmann, 1996.

[15] 宮野悟,『並列アルゴリズム』, 近代科学社, 1993.

[16] F. P. Preparata著, 上林弥彦, 岡部寿男, 浜口清治, 武永康編・訳,『プレパラータ先生超並列計算講義』, 共立出版, 1996.

[17] R. Sedwick, Algorithms, 2nd ed., Addison-Wesley, 1988; 野下浩平, 星守, 佐藤創, 田口共訳,『アルゴリズム第1巻=基礎・整列』, 近代科学社, 1990,『アルゴリズム第2巻=探索文字列計算幾何』, 近代科学社, 1992, および,『アルゴリズム第3巻=グラフ数理トピックス』, 近代科学社, 1993.

[18] 島内剛一, 有澤誠, 野下浩平, 浜田穂積, 伏見正則編,『アルゴリズム辞典』, 共立出版, 1994.

[19] G. Tel, Introduction to Distributed Algorithms, Cambridge University Press, 1994.

「OR事典」の他の用語
組合せ最適化:  AVL木  NP困難  TDI性  アルゴリズム  オンラインアルゴリズム  クラスMAX SNP  クラスNC

アルゴリズム

問題解決するための手順や手続き模式したものです。

アルゴリズム

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2017/08/11 09:19 UTC 版)

アルゴリズム: algorithm [ˈælgəˌrɪðəm])とは、数学コンピューティング言語学、あるいは関連する分野において、問題を解くための手順を定式化した形で表現したものを言う。算法と訳されることもある。




  1. ^ ユークリッド『原論』第 7 巻「数論」、命題 1〜3。
  2. ^ アラビア語: الخوارزمي‎, ラテン文字転写: al-Khwarizmi
  3. ^ Yuri Gurevich「Sequential Abstract State Machines Capture Sequential AlgorithmsACM Transactions on Computational Logic、第1巻、no 1 (2000年7月)、pages 77–111
  4. ^ a b c d クリーネ, ステフェン (1952年(初版)). Introduction to Metamathematics (第10版 1991年 ed.). ノースホーランド出版. 
  5. ^ クヌース, ドナルド (1997年). Fundamental Algorithms, Third Edition. 米国マサチューセッツ州リーディング: アジソン・ウェスレイ. 
  6. ^ a b ミンスキー, マービン (1967年). Computation: Finite and Infinite Machines (初版 ed.). プレンティスホール、米国ニュージャージー州. 
  7. ^ : undecided、不定
  8. ^ Sipser, Michael (2006年). Introduction to the Theory of Computation. PWS出版社. 
  9. ^ Kowalski, Robert (1979年). “Algorithm=Logic+Control”. Communications of the ACM (ACM Press) 22 (7): 424–436. doi:10.1145/359131.359136. ISSN 0001-0782. 
  10. ^ a b Burgin, M. Super-recursive algorithms, Monographs in computer science, Springer, 2005. ISBN 0387955690
  11. ^ 米国特許商標庁 (2006), 2106.02 **>Mathematical Algorithms< - 2100 Patentability, Manual of Patent Examining Procedure (MPEP).
  12. ^ 著作権なるほど質問箱 - 文化庁
  13. ^ 基本情報技術者 平成24年春期 午前問78 - 基本情報技術者試験ドットコム


「アルゴリズム」の続きの解説一覧

アルゴリズム

出典:『Wiktionary』 (2010/12/20 03:19 UTC 版)

発音

IPA: /??/

語源

名詞

アルゴリズム

  1. コンピュータ等に仕事をさせる場合処理手順算法さんぽうプログラム言語使用して記述されたアルゴリズムがプログラムである。



アルゴリズムと同じ種類の言葉


英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「アルゴリズム」の関連用語

アルゴリズムのお隣キーワード

   

英語⇒日本語
日本語⇒英語
   
検索ランキング



アルゴリズムのページの著作権
Weblio 辞書情報提供元は参加元一覧にて確認できます。

  
三省堂三省堂
Copyright (C) 2001-2019 Sanseido Co.,Ltd. All rights reserved.
株式会社 三省堂三省堂 Web Dictionary
日本オペレーションズ・リサーチ学会日本オペレーションズ・リサーチ学会
Copyright (C) 2019 (社)日本オペレーションズ・リサーチ学会 All rights reserved.
Supplement Kuchikomi RankingSupplement Kuchikomi Ranking
(C)2019 All Rights Reserved. 健康食品のあり方を考える日本サプリメント評議会の運営です。
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアのアルゴリズム (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。
Text is available under Creative Commons Attribution-ShareAlike (CC-BY-SA) and/or GNU Free Documentation License (GFDL).
Weblioに掲載されている「Wiktionary日本語版(日本語カテゴリ)」の記事は、Wiktionaryのアルゴリズム (改訂履歴)の記事を複製、再配布したものにあたり、Creative Commons Attribution-ShareAlike (CC-BY-SA)もしくはGNU Free Documentation Licenseというライセンスの下で提供されています。

©2019 Weblio RSS