効率的なプログラムを作成するには、定石となる「アルゴリズム」を理解する必要があるとのこと。そこで、プログラミングの基礎として「アルゴリズム」についても今後まとめていきたいと思います。今回は、その序章としてアルゴリズムとは？についてまとめます。
アルゴリズムとは
アルゴリズムとは、「与えられた課題を解決するための手順」のことです。良いアルゴリズムは効率的に課題を解決するのに役立ちます。
wikipediaから引用すると、
アルゴリズム（英: algorithm [ˈælgəˌrɪðəm]）とは、数学、コンピューティング、言語学、あるいは関連する分野において、問題を解くための手順を定式化した形で表現したものを言う。算法と訳されることもある。
「問題」はその「解」を持っているが、アルゴリズムは正しくその解を得るための具体的手順および根拠を与える。さらに多くの場合において効率性が重要となる。
アルゴリズムに必要な条件
アルゴリズムに必要な条件は以下に示すように、「正当性」と「停止性」の２つあります。
正当性
アルゴリズムは、「指定された条件を満たす入力が与えられた場合、必ず正しい結果を導き出すことを保証する」ことが必要です。これを「アルゴリズムの正当性」と呼びます。
アルゴリズムの正当性は、アサーションという手法によって検証が可能です。
アサーションとは、アルゴリズムの手順の中の任意の位置で、その時点において満たさなければいけない条件や結果がが正しいかどうかを細かく判定することを言います。PythonでもAssert文で条件を決めてエラーを出力する構文があります。
停止性
アルゴリズムは、最終的に必ず停止する必要があります。無限ループに陥って答えを出さない手順はアルゴリズムとは言えません、「アルゴリズムの停止性」は、「いかなる条件の入力値が与えられた場合でも、有限時間内に必ず正しく停止することを保証する」ことで示されます。
主なアルゴリズム
ここでは、主なアルゴリズムをいくつか挙げます。
| 分類 | 主な具体例 |
|---|---|
| 技術計算 |
|
| 並べ替え（ソート） |
|
| 探索（サーチ） |
|
| 文字列の中から特定のパターンを探すための照合アルゴリズム |
|
今後、それぞれについて、擬似コードによるアルゴリズム例と、Pythonによるコード例もつけてもう少し詳しく紹介していく予定です。
（参考文献：杉浦賢、図解でかんたんアルゴリズム 情報処理のかなめとなる考え方が手に取るようにわかる、Softbank Creative）
コメント