アルゴリズム
アルゴリズムは計算能力によっても分類される。一般にアルゴリズムは計算能力によって階層的に分類される。「再帰的クラス」とは、全てのチューリング計算可能関数についてのアルゴリズムを含むクラスである。このような階層化によって、計算に必要とされる計算資源(時間とメモリ)を制限できる可能性が生じる。「部分再帰クラス」は、全てのチューリング計算可能な関数を得ることはできない。例えば、多項式時間で実行されるアルゴリズムには多くの重要な計算が含まれるが、チューリング計算可能な関数全体を含むことはない。原始再帰関数で実装されるアルゴリズムのクラスは、別の部分再帰的クラスの例である。
Burgin (2005, p. 24) は、関数を計算するアルゴリズムは有限ステップ後に必ず出力が決定されなければならないという一般的条件を緩めたアルゴリズムの汎用的定義を行った。彼は「超再帰的クラス」を「チューリングマシンで計算可能でない関数を計算可能なアルゴリズムのクラス」と定義した(Burgin 2005, p. 107)。これはハイパーコンピュータの手法の研究と密接に関係している。
部分問題の最適解から全体の最適解が得られるような構造の問題や、同じ部分問題の最適解が様々な問題の解法に有効であるような問題の場合、動的計画法を使って既に計算済みの解を再計算するのを避けることができ、解法を効率化できる。例えば重み付けのあるグラフでの最短経路を求める場合、始点に隣接する全ての頂点について最短経路が分かっていれば、容易に最短経路が求められる。動的計画法とメモ化は密接な関係がある。分割統治法との違いは、分割統治法では部分問題は多少なりとも独立しているのに対して、動的計画法では部分問題が重複している。単純な再帰との違いは、再帰部分をキャッシュ化またはメモ化する点である。部分問題が互いに独立している場合、メモ化は何の役にも立たない。したがって、動的計画法はあらゆる複雑な問題の解法とはならない。動的計画法では、メモ化あるいは既に解かれた部分問題の表を使うことによって、指数関数的性質をもつ問題を多項式レベルの複雑性に削減することができる。
自然言語でアルゴリズムを説明したもの。実装の詳細は省かれている。このレベルでは、チューリング機械のテープやヘッドの動きまでは説明しない。
このような計算過程について、アルゴリズムは厳密に定義されなければならず、ありうる全ての状況に適用可能な形で指定される。すなわち、どのような条件のステップでも、ケースバイケースで体系的に扱わなければならず、各ケースの扱い方は明確で(計算可能で)なければならない。
アルゴリズムは明確なステップの明確なリストなので、その計算順序は最も重要である。命令列は、先頭から最後尾に向かって逐次的に実行されるよう記述される。この考え方をより形式的にしたものが制御構造である。
以上の説明は、命令型プログラミングを前提としてアルゴリズムを定式化する場合である。これは、最も典型的な概念であり、タスクを離散的かつ機械的なものとして表すものである。その場合に特有の操作として、変数に値を設定する「代入」がある。これは、直観的にはメモリをメモ帳のようなものとみなすところから生まれた。
これ以外のアルゴリズムの概念化として、関数型プログラミングや論理プログラミングがある。
ここではまず非形式的にアルゴリズムについて述べた後で、停止性など形式的(フォーマル)な議論を続ける。
アルゴリズムはコンピュータが情報を処理する基盤である。すなわち、プログラムは本質的にはアルゴリズムであり、コンピュータが特定のタスク(従業員の給与計算、学生の成績表の印刷など)を(指定された順序で)実行するためのステップをコンピュータに指示する。したがって、アルゴリズムはチューリング完全なシステムで実行可能な操作の並びとみなすこともできる。
アルゴリズムは情報処理と結びついていることが多く、データは何らかの入力源(機器)から読み込まれ、結果は何らかの出力先(機器)に書かれるか、次の処理の入力となるよう保持される。保持されたデータはアルゴリズムを実行する実体の内部状態の一部とみなされる。実際、コンピュータでは状態をデータ構造に保持したりする。
チェスの手を考えるなどといった問題は、グラフ問題としてモデル化できる。そのような問題では、比較的よく研究されているグラフ探索アルゴリズムを使うことができる。このカテゴリーには、探索アルゴリズム、分枝限定法、バックトラッキングも含まれる。