アルゴリズムとは
アルゴリズム（Algorithm）とは、問題を解くための効率的手順を定式化した形で表現したものを意味します。例えば、数学、コンピューティング、言語学においての問題を解くための効率的手順を定式化した形で表現のことです。
コンピュータにアルゴリズムを指示するための電子文書をプログラムといい、人間よりも素早く大量に正しい結果を導くことができるのがコンピュータの強みですが、そのためには正しいアルゴリズムにもとづくプログラムが必要であるといわれています。
アルゴリズムの歴史を辿る
記録に残る最古のアルゴリズムは、エウクレイデスの原論に載っているユークリッドの互除法であるといわれています。これは、二つの整数の最大公約数を求めるアルゴリズムです。アルゴリズムという名称は、9世紀の現在のイラクのバグダードの数学者アル・フワーリズミーの名前から来ていると言われています。彼の著作『インドの数の計算法』825年が、12世紀にチェスターのロバート（あるいはバスのアデレード）によってラテン語に翻訳され、『Algoritmi de numero Indorum』（アルゴリトミ・デ・ヌーメロ・インドルム、直訳すると「インドの数に関して」）という題で、以後500年間にわたってヨーロッパ各国の大学で数学の主要な教科書として用いられました。この書は、冒頭にある「Algoritmi dicti」（「アル・フワリズミに曰く」）の一節のため『Algoritmi』（アルゴリトミ）と呼ばれていました。
アルゴリズムの定義
「アルゴリズム」の広く受け入れられている形式的定義はまだ存在しません。しかし、その手がかりはいくつかあり、その大まかな意味は次の引用に表されています。
人間は、何らかの記法で1つの可算無限集合の全ての元の名前を、十分に速く、あるいは長く、あるいは小さく、順に記述することはできない。しかし、特定の可算無限集合について、同程度に役に立つことはできる。例えば、任意の有限な n について、集合の n 番目の元を決定する明確な指示を与えることができる。そのような指示は極めて明示的にすることができ、計算機械が実行できる形式にもできるし、記号について初歩的な操作しかできない人が実施できる形式にもできる。
「可算無限」とは、「無限にまで拡張した整数で数えられる」という意味です。つまり、ここで言うアルゴリズムは、理論的には 0 から無限大までを含む任意の整数（群）の「入力」から、出力すべき整数を「生成」する過程についての指示を「含む」ものとされています。従って例えば、y = m + n のような（2つの任意の入力変数 m と n から出力 y を生成する）代数方程式もアルゴリズムと見ることができます。実際には、アルゴリズムの意味はもっと広く、方程式の例で言うと、次のようになります。
（計算主体が理解できる言語で書かれた）正確な指示であり、計算主体（適当な情報と機能を内包した機械や人）の動作を示した効率的な過程を表す。その過程には、任意の入力の m と n といった整数/記号や + と = といった記号を受け付けて、復号化し、妥当な時間内に出力整数 y を指定された位置に指定された形式で確実かつ効率的に生成することが含まれる。
アルゴリズムの概念は、決定可能性の概念定義にも使われます。その概念は、小さな公理群と規則群を始点として形式体系が如何に形成されるかを説明する際の重要な部分となります。論理学では、アルゴリズムが完了するまでに要する時間は、一般的な物理的次元とは関連していないため、測定できません。そのような不確実性があるため、アルゴリズムという用語を正確に定義できないという側面もあります。
1920〜30年代、アルゴリズムの概念を定式化する為の数学モデル（計算モデル）がいくつも提案されました（チューリングマシン、帰納的関数、λ計算など）。のちにこれらの定義はすべて同等であることがわかり、チャーチはこれらの同値な概念をアルゴリズムと考えることを提案しました（チャーチの提唱）。このため現在では、チューリング機械の状態遷移図（もしくはそれと等価なもの）をアルゴリズムと呼びます。
アルゴリズムの定式化
アルゴリズムはコンピュータが情報を処理する基盤です。すなわち、プログラムは本質的にはアルゴリズムであり、コンピュータが特定のタスク（従業員の給与計算、学生の成績表の印刷など）を（指定された順序で）実行するためのステップをコンピュータに指示します。従って、アルゴリズムはチューリング完全なシステムで実行可能な操作の並びと見做すこともできます。
…チューリングの命題についての非形式的な論証から、より強い命題が正当化される。すなわち、全てのアルゴリズムはチューリング機械でシミュレート可能である…
Savage [1987] によれば、アルゴリズムはチューリング機械によって定義される計算過程である。
アルゴリズムは情報処理と結びついていることが多く、データは何らかの入力源/機器から読み込まれ、結果は何らかの出力先/機器に書かれるか、更なる処理の入力となるよう保持されます。保持されたデータはアルゴリズムを実行する実体の内部状態の一部と見做される。実際、コンピュータでは状態をデータ構造に保持したりします。このような計算過程について、アルゴリズムは厳密に定義されなければならず、ありうる全ての状況に適用可能な形で指定されます。すなわち、どのような条件のステップでも、ケースバイケースで体系的に扱われなければならず、各ケースの扱い方は明確で（計算可能で）なければなりません。アルゴリズムは明確なステップの明確なリストであるため、その計算順序は最も重要です。命令列は、先頭から最後尾に向かって逐次的に実行されるよう記述されます。この考え方をより形式的にしたものが制御構造です。以上の説明は、命令型プログラミングを前提としてアルゴリズムを定式化する場合です。これは、最も典型的な概念であり、タスクを離散的かつ機械的なものとして表すものです。その場合に特有の操作として、変数に値を設定する「代入」があります。これは、直観的にはメモリをメモ帳のようなものと見做すところから生まれました。これ以外のアルゴリズムの概念化として、関数型プログラミングや論理プログラミングがあります。
停止性
アルゴリズムは最終的に必ず停止しなければならないとする定義もあります。例えば、クリーネは停止性のあるアルゴリズムを "decision procedure or decision method or algorithm for the question" としました。停止しない可能性のある手続きについては、クヌースは "computational method"と呼び、クリーネは "calculation procedure or algorithm"と呼んでいます。ミンスキーは、（特定の状態から開始された）アルゴリズムの停止性について次のように述べています。
しかしもし実行中のプロセスの長さが不明ならば、それを試すことは得策ではないかもしれない。何故なら、もしプロセスが永遠に続くなら、我々は答えを得られないかもしれないのだから。
アラン・チューリングが停止性問題として提起した通り、任意のアルゴリズムと初期状態が与えられたとき、それが停止するかどうかを判定するアルゴリズム的手続きは存在しません。なお、アルゴリズムの停止性を解析するtermination analysisというものもあります。
不完全な（あるいは間違った）アルゴリズムは、次のいずれかの結果となります。
■停止しない。
■解の範囲を逸脱した値を返して停止する。
■間違った解を返して停止する。
■解を返さずに停止する。
■これらの組合せ。
クリーネはこれらをアルゴリズム内で検出してエラーメッセージを返すか、可能ならば無限ループに入らせることを提案しました。また、結果が真理値である場合についてクリーネは第三の論理記号 "u"（undecided）を使うことも提案しています。そうすれば、命題を扱うアルゴリズムで何らかの値を常に生成できるとしました。間違った答えを返す問題は、帰納法を使ったアルゴリズムに関する個別の「証明」で解決されます。
通常、これ（アルゴリズムがμ再帰関数を正しく定義しているかという問題）には補助的な証拠を必要とします。それは例えば、個々の引数の値について、計算が一意な値で終了するかという帰納的証明の形式で示されます。
アルゴリズムの表現
アルゴリズムには様々な記法があり、自然言語、擬似コード、フローチャート、プログラミング言語などがあります。アルゴリズムの自然言語表現は冗長であいまいになる傾向があり、複雑なアルゴリズムや技術的な場面では単独ではほとんど使用されません。擬似コードやフローチャートはアルゴリズムを構造的に表現でき、自然言語のようなあいまいさもほとんどありません。プログラミング言語でアルゴリズムを示すこともよくあります。アルゴリズムの記述は、チューリング機械に関する記述として以下の3つに分類されます。
高レベルな記述
自然言語でアルゴリズムを説明したもの。実装の詳細は省かれています。このレベルでは、テープやヘッドの動きまでは説明しません。
実装レベルの記述
チューリング機械のヘッドの動きやテープへのデータ格納方法を自然言語で説明します。このレベルでは機械の状態や遷移関数の詳細は説明しません。
形式的記述
最も詳しい説明。チューリング機械の「状態表」を提示する。
実装
多くのアルゴリズムは、プログラムとして実装されることを意図しています。しかしアルゴリズムの実装手段は他にもあり、電気回路で実装したり、機械で実装したりすることもあります。人間が算術を覚えるのも、脳内の神経網にアルゴリズムが実装されたものと見ることもできます。
アルゴリズム解析
あるアルゴリズムが必要とする計算資源（時間や記憶領域）の量を知ることは重要です。そのような定量的な値を求める手法はアルゴリズム解析と呼ばれ、研究されてきました。例えば、上記のアルゴリズムの必要とする時間をO記法とリストの長さを表す n を使って表すと O(n) となります。このアルゴリズムでは、常に2つの値だけを記憶しておけばいいです（その時点での最大の数と現在見ているリスト上の位置）。従って、必要とする領域は O(1) となりますが、入力となっているリスト上の要素数を数える記憶領域も含めるなら O(log n) となります。同じ問題であっても、アルゴリズムが異なれば、必要とする時間や記憶領域の量も異なる。例えば、ソートには様々なアルゴリズムがあるが、それぞれ必要な時間や記憶領域の量が異なります。アルゴリズム解析は計算機科学の一部であり、特定のプログラミング言語や実装を前提とせずに、抽象的に解析を行うことが多いです。これは、アルゴリズムの様々な属性に注目した他の数学的分野とも共通します。一般に非常に単純化した汎用的表現として擬似コードが使われます。
グラフ理論
グラフ理論（Graph theory）とは、数学の一分野のことをいいます。
具体的には、ノード（節点・頂点）の集合とエッジ（枝・辺）の集合で構成されるグラフの性質について研究する学問（数学）で、
コンピュータのデータ構造、アルゴリズムなどに広く応用されています。
探索アルゴリズム
探索アルゴリズム（たんさくあるごりずむ）とは、例を挙げると問題を入力として、考えられるいくつもの解を評価した後、解を返すアルゴリズムのことです。
主に線形探索と2分探索とがあり、
問題を解く類として研究されているアルゴリズムの多くは探索アルゴリズムといいます。
ある問題の考えられるあらゆる解の集合を探索空間と呼び、力まかせ探索や素朴な（知識を用いない）探索アルゴリズムは、探索空間を探索する手法としては最も単純で直観的であるといわれています。
一方、知識を用いた探索アルゴリズムはヒューリスティクス（Heuristic）を使って探索空間の構造に関する知識を利用し、探索にかかる時間を削減しようとします。
ヒューリスティクス（Heuristic）とは、必ず正しい答えが導けるわけではないが、ある程度のレベルで正解に近い解を得ることが出来る方法のことをいいます。ヒューリスティクスを用いるメリットは、答えの精度は低いため、回答に至るまでの時間が少なくて
済むことです。主に計算機科学と心理学の世界で使われる言葉で、計算機科学ではプログラミングの方法を、心理学では人間の思考方法を指して使われています。
疑似コード
疑似コード（ぎじこーど、Pseudocode、Pseudo-Code）とは、アルゴリズムの構造を記述する際に用いられる擬似的な言語のことです。
擬似コードは、多くの場合、既存のプログラミング言語の文法に似せて表現されます。
アルゴリズム情報理論
アルゴリズム情報理論（あるごりずむじょうほうりろん、Algorithmic information theory）とは、情報理論と計算機科学の一分野であり、計算理論や情報科学とも関連があるアルゴリズムといわれています。
グレゴリー・チャイティン氏によれば、「シャノンの情報理論とチューリングの計算複雑性理論をシェイカーに入れて、力いっぱいシェイクしてできたもの」である。と、いわれています。