アルゴリズム
一般にアルゴリズムは正解を得るものだが、近似アルゴリズムは近似解を求め、その近似性に一定の根拠があれば、これも広義のアルゴリズムとして含めて考えることができる。近似には、決定性の戦略もあれば、乱択の戦略もある。多くの難しい問題では、近似アルゴリズムしか実用的な解法が存在しない。近似アルゴリズムはその近似解の近似性能も評価・保証などがされる必要がある。
アルゴリズム自体は一般に特許化できない。アメリカ合衆国では、抽象概念、数、信号の単純な操作だけから成る請求項は「プロセス」を構成しないとされるので、アルゴリズムは特許化できない。
しかし、アルゴリズムの具体的応用は特許化可能な場合がある。例えば、Diamond v. Diehrのケースでは、単純なフィードバックアルゴリズムを使った合成ゴムの硬化処理が特許として認められた。
データ圧縮アルゴリズムの分野では、ソフトウェア特許が論争の元になることが多く、例えばユニシスのLZWアルゴリズムの特許問題が有名である。
圧縮アルゴリズムで有名な特許問題は他に算術符号も挙げられる。算術符号で取得されている特許の範囲は3点であるとされている。算術符号によって断念されたソフトウェアやファイル形式は多く、代替品が相次いで開発された。
線型計画問題の解法であるカーマーカーのアルゴリズムは日本において特許無効審判がなされたが、2000年12月11日付けで特許庁に当該特許の放棄による特許権抹消の登録が行われたため、最終的に審判が却下された。
入力: 空でない数リスト L、出力: リスト L 内の最大(largest)の数。
再帰アルゴリズムは、ある条件が成り立つまで自身を再帰的に呼び出すものであって、関数型言語でよく使われる。反復アルゴリズムは、ループのような反復構造と場合によってはスタックなどのデータ構造を補助的に使い、問題を解く。一部の問題は、どちらか一方の実装が自然である。例えば、ハノイの塔は再帰的実装の方が分かりやすい。再帰アルゴリズムは全て反復アルゴリズムでも実装可能であり、逆も同じである(ただし、複雑さは変化する)。
アルゴリズムは、入力長に対する計算時間で分類される。あるアルゴリズムは入力長に対して線形時間で完了する。また別のアルゴリズムは指数時間以上かかるし、場合によっては完了しないこともある。さらに、問題によっては計算量の異なる複数のアルゴリズムが存在するし、効率的なアルゴリズムが全く知られていない問題もある。問題によっては、別の問題への写像が存在する。以上のようなことから、計算量による分類は、アルゴリズムについてではなく、問題について行うのが適当とされている。つまり、問題を解く最善のアルゴリズムの計算量に基づいて、問題を分類する。
アルゴリズム自体が保護される訳では無いが、商標の基準を満たしていればアルゴリズム名称を商標として登録することはできる。ただしアルゴリズム名称はその性質上から通常は一般名詞として通用するものであり、一般名詞と同じ語について商標の基準を満たして商標として登録しても、一般名詞の一般名詞としての(すなわちごく当然の)使用を妨げるという通念に反するような権利の濫用はできないような商標法上の制限があるため、通常の、商品名などを登録した場合と違い権利は制限される。