この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。
出典を追加して記事の信頼性向上にご協力ください。（2011年11月）
線型計画問題 (せんけいけいかくもんだい、英語：linear programming problem) とは、最適化問題において、目的関数が線型関数で、なおかつ線型関数の等式と不等式で制約条件が記述できる問題である。この問題を解く手法を線型計画法という。 行列やベクトルを用いて表現すると、行列Aとベクトルb,cが与えられたとき、制約条件Ax≤b, x≥0をみたしつつcTxを最大化するベクトルxを求める問題のことである。 線型計画問題は次のように記述できる。 max : c T x sub.to : A x ≤ b x ≥ 0 {\displaystyle {\begin{matrix}\max &:&c^{T}x\\{\mbox{sub.to}}&:&Ax\leq b\\&&x\geq 0\end{matrix}}} これを標準型といい、制約条件に線型不等式
数学的表現
アルゴリズムが提案したシンプレックス法（単体法）がよく知られている。このアルゴリズムは、実用上は高速であり、ほとんど常に変数の数・制約条件の数の大きい方のオーダーの反復回数で解が求まる。しかし、Dantzig が提唱したもの（ピボット規則）は理論的には多項式時間アルゴリズムではない。常に多項式時間で解が得られるピボット規則の存在性は、現在も未解決問題である。単体法という名前は、Dantzigが提案した特殊な図解法においては、アルゴリズムの進行に従って単体が下に落ちていくように見えることに由来する。
その後、1979年、Leonid Khachiyan
が初めての多項式時間アルゴリズムである楕円体法（英語版）を提案する。さらに、1984年、ナレンドラ・カーマーカー（Narendra Karmarkar）はより効率の良いカーマーカー法を提案し、大規模な問題に対してはシンプレックス法よりも高速であると主張した。現代においては、カーマーカー法に触発された汎用の内点法で十分に高速に解ける。比較ソート
バブルソート
選択ソート
挿入ソート
シェルソート
クイックソート
マージソート
ヒープソート
シェーカーソート
コムソート
ノームソート
図書館ソート
イントロソート
奇偶転置ソート
線形時間ソート
鳩の巣ソート
基数ソート
バケットソート
並行ソート
ソーティングネットワーク
バッチャー奇偶マージソート
シェアソート
非効率的
ボゴソート
ストゥージソート
グラフ
トポロジカルソート
探索
リスト
線形探索
二分探索
木・グラフ
幅優先探索
最良優先探索
均一コスト探索
A*
深さ優先探索
反復深化深さ優先探索
深さ制限探索
双方向探索
分枝限定法
文字列
クヌース?モリス?プラット法