アルゴリズム
アルゴリズムには様々な記法があり、自然言語、擬似コード、フローチャート、プログラミング言語などがある。アルゴリズムの自然言語表現は冗長であいまいになる傾向があり、複雑なアルゴリズムや技術的な場面では単独ではほとんど使用されない。擬似コードやフローチャートはアルゴリズムを構造的に表現でき、自然言語のようなあいまいさもほとんどない。プログラミング言語でアルゴリズムを示すこともよくある。
アルゴリズムの記述は、例えばチューリング機械を使ったならば、として次の3つに分類している書籍などがある。
分割統治法は、問題を(通常再帰的に)複数または単一の同じ種類のもっと小さい問題に還元していき、最終的に容易に解ける程度の大きさにする。分割統治の例としてはマージソートがある。ソートは入力データを分割してそれぞれに対して行われ、統治フェーズではそれらの結果をマージする。分割統治法を単純化したものとして decrease and conquer algorithm がある。これは、問題を全く同じ複数の部分問題に分割し、その解をより大きな問題を解くのに利用する。分割統治法では一般に分割された個々の部分問題は全く同じではないため、統治フェーズは decrease and conquer algorithm よりも複雑になる。decrease and conquer algorithm の例として二分探索がある。
線型計画法で解ける問題では、制約条件として入力に関する線型の不等式があり、入力に関するある線型の関数を最大化(または最小化)する値の組合せを求めるものである。有向グラフに関する最大フロー問題など、多くの問題が線型計画問題として記述でき、シンプレックス法などの汎用アルゴリズムで解くことができる。線型計画法の解空間を整数に限定したものを整数計画法と呼ぶ。