algorithm
「algorithm」とは・「algorithm」の意味
「algorithm」とは、問題を解決するための手順や計算方法を指す言葉である。コンピューターサイエンスや数学の分野でよく使われ、特にプログラミングにおいては、効率的なアルゴリズムが重要視される。アルゴリズムは、入力データを受け取り、一連の手順に従って処理を行い、最終的には出力データを生成する。「algorithm」の発音・読み方
「algorithm」の発音は、IPA表記では /ˈælɡəˌrɪðəm/ であり、カタカナ表記では「アルゴリズム」となる。日本人が発音するカタカナ英語では「アルゴリズム」と読む。「algorithm」の定義を英語で解説
An algorithm is a step-by-step procedure or set of instructions for solving a problem or accomplishing a task, especially in the fields of mathematics and computer science. Algorithms are often used in programming to process input data and generate output data in an efficient and accurate manner.「algorithm」の類語
「algorithm」の類語には、以下のような言葉がある。Procedure
「procedure」は、特定の目的を達成するための一連の手順や操作を指す。アルゴリズムと似ているが、より一般的な用途に使用される。Method
「method」は、問題を解決するための手法やアプローチを指す。アルゴリズムと同様に、手順や計算方法を示すことがある。「algorithm」に関連する用語・表現
Sorting algorithm
「sorting algorithm」は、データを特定の順序で並べ替えるためのアルゴリズムを指す。例えば、バブルソートやクイックソートなどがある。Search algorithm
「search algorithm」は、データ構造から特定の要素を見つけ出すためのアルゴリズムを指す。例えば、線形探索や二分探索などがある。「algorithm」の例文
1. The algorithm processes the input data and generates the output data.（アルゴリズムは入力データを処理し、出力データを生成する。） 2. He developed a new algorithm for solving the problem.（彼はその問題を解決するための新しいアルゴリズムを開発した。） 3. The efficiency of an algorithm is an important factor in programming.（アルゴリズムの効率はプログラミングにおいて重要な要素である。） 4. The sorting algorithm arranged the data in ascending order.（ソートアルゴリズムはデータを昇順に並べ替えた。） 5. The search algorithm found the target element in the data structure.（探索アルゴリズムはデータ構造から目的の要素を見つけ出した。） 6. The algorithm's complexity affects its performance.（アルゴリズムの複雑さはその性能に影響する。） 7. The programmer optimized the algorithm to reduce processing time.（プログラマーは処理時間を短縮するためにアルゴリズムを最適化した。） 8. The algorithm was tested on various data sets to ensure its accuracy.（アルゴリズムの正確性を確認するために、さまざまなデータセットでテストが行われた。） 9. The algorithm is designed to handle large amounts of data efficiently.（アルゴリズムは大量のデータを効率的に処理するように設計されている。） 10. The algorithm is based on a mathematical model.（アルゴリズムは数学的モデルに基づいている。）
アルゴリズム【algorithm】
アルゴリズム
アルゴリズムとは、物事を進めていくための明確な手順、特に問題を解くための手順のことである。
アルゴリズムという語は、バグダット（現在のイラクの都市）の数学者であるal-Khwarizmi（アル・フワーリズミー）に由来する。なお代数学のalgebra（アルジェブラ）も同じ語源だと言われている。数学においては、古くから、代数方程式を機械的に解く方法が存在していた。このような一定の決まった手順に従って、確定的に問題を解くことができる場合、この手順のことをアルゴリズムと呼ぶ。
計算機は、一定の手順を記述したプログラムを実行する機械である。従って、計算機は、一定のアルゴリズムをプログラムによって記述し、そのアルゴリズムに従った処理を実行することができる。アルゴリズムが対象にする問題は、ソートやマージ、分類、探索などの論理的あるいは数学的なものである。なお、アプリケーション全体は、一定のアルゴリズムを含むことがあるが、通常、アプリケーション自体をアルゴリズムとは呼ばない。
アルゴリズムとしてテーマになるものは、探索法やソート法、ハッシュ法、暗号化手法、圧縮展開手法などがある。アルゴリズムは、対象とするデータが持つデータ構造と密接に関連し、ある構造を前提にした処理方法、手順として提示される。例えば、グラフ構造というデータ構造を前提にして、そのグラフ上のグラフ探索アルゴリズムが定式化される。
Donald Ervin Knuth（ドナルド・エルビン・クヌース）は、スタンフォード大学名誉教授で、アルゴリズムとプログラミングの研究で有名である。主著『The Art of Computer Programming』は、プログラミング技法の名著である。またアルゴリズム解析という新分野を開拓した。
アルゴリズム
【英】：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困難な問題に対して多項式時間アルゴリズムは存在しないと信じられている.
与えられた問題に対して効率の良いアルゴリズムを開発するには,
が必要である.
代表的なアルゴリズム設計技法としては以下のものが知られている.
例: 最小木問題 (minimum spanning tree) に対するクラスカル (J. B. Kruskal Jr.) のアルゴリズム, その他, 近似アルゴリズム (approximation algorithm) としても良く用いられる.
- ・2分探索 (binary search): 予めソートされた列中で, ある要素を探す. 中央の要素と比較し, それよりも大きいか, 小さいかを調べ, ソート列中のどちら側にあるかを知る. 一回の反復毎に要素数が半分以下になるので,
(ソート列中の要素数) 回の比較で求まる.
- ・分割統治(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.
| 組合せ最適化： | AVL木 NP困難 TDI性 アルゴリズム オンラインアルゴリズム クラスMAX SNP クラスNC |
- Algorithmのページへのリンク
