アルゴリズム
この技法は、難しい問題をほぼ最適なアルゴリズムが既知の別の問題に変換するものである。例えば、ソートされていない数列から中央値を求める選択アルゴリズムとして、まずその数列をソートし、そこから真ん中に位置する値を取り出すという方式がある。
筆算 - かけ算(尾乗法)、わり算(長除法)
ユークリッドの互除法 - 最大公約数を求める
ガウスの消去法 - 線型方程式系(連立方程式)の解を求める
ニュートン法 - 繰り返し計算により解の精度を高める方法で非線型方程式の数値解を1つ求める
ガウス=ルジャンドルのアルゴリズム - 円周率を求める
素数判定法 - 与えられた自然数が素数かどうかを判定する
素因数分解 - 与えられた自然数を素因数分解する
高速フーリエ変換(FFT) - 離散フーリエ変換を計算機上で計算する。工学、理学、医療工学などに広く応用されている。例えば、波形データが含む周波数成分を算出するなど。
アルゴリズム分類の1つの方法として、実装手段による分類がある。
最初の要素(数)が最大と仮定する。
残りのリスト上の数を順に見ていき、最大の数よりも大きい数が見つかったら、それを新たな最大として記憶する。
最後に記憶した数がそのリストでの最大の数であり、これで処理が完了する。
次に、プログラミング言語的にやや形式的に記述すると、次のような擬似コードになる(「←」は代入を表し、「return」はその後に記された値を返してアルゴリズムが終了することを意味する)。
簡単なアルゴリズムの例として、(整列されていない)有限長の数列(リスト)に含まれる(大きさが一定値以下の整数の)最大の数を見つけ出すアルゴリズムを考える。ここでは、リストに含まれる全ての数を調べる必要があるが、一度に調べらることができるのは1つだけであるとする。ここから得られるアルゴリズムを、日本語で記述すると次のようになる。
アルゴリズムは、制御された演繹であるとも言われる。これを アルゴリズム = 論理 + 制御 と表現することもある。論理部分は計算で使われる公理を表し、制御部分は公理に演繹が適用される方法を決定する。これは論理プログラミングというパラダイムの基本である。純粋な論理プログラミングでは、制御部分が固定されていて、アルゴリズムは論理部分だけで指定される。この手法の魅力は、プログラム意味論的なエレガントさがある点である。公理の変化は定式化されたアルゴリズムの変更を伴う。