ORWiki - 利用者の投稿記録 [ja]

ミニマックス定理 (ゲーム理論における)

2007-07-14T08:04:41Z

222.225.128.87:

【みにまっくすていり (minimax theorem)】

2変数関数 <math>F\,</math> に対して以下の等式が成立するための諸条件を述べた定理.
 
<center>
<math>\inf_{x\in{X}}\sup_{y\in{Y}}F(x,y)=\sup_{y\in{Y}}\inf_{x\in{X}}F(x,y)\,</math>
</center>
定理によっては, <math>\inf\,</math> と <math>\sup\,</math> をそれぞれ <math>\min\,</math> と <math>\max\,</math> に取り替えた等式を保証するものもある. 関数 <math>F\,</math> が非線形計画問題のラグランジュ関数の場合には, 双対性理論に密接に関係する.

3つ組み記法 (スケジューリング問題の)

2007-07-14T08:02:48Z

222.225.128.87:

【みつぐみきほう (three field notation in scheduling)】

ジョブショップ問題の分類法. 待ち行列のケンドール記号に似せて, <math>\alpha |\beta |\gamma\,</math>で分類する. ここで<math>\alpha\,</math>はショップの構成, <math>\beta\,</math>は制約条件などジョブ環境, <math>\gamma\,</math>は目的関数である. 例えば, <math>1 | \mbox{prec}\,</math>, <math>r_j | C_{\mbox{max}}\,</math>は先行制約(prec)と準備時間制約(<math>r_j\,</math>)のもとで最大完了時間(<math>C_{\mbox{max}}\,</math>)を最小にする1機械問題を表す.

ミックス効率性

2007-07-14T08:01:18Z

222.225.128.87:

【みっくすこうりつせい (mix efficiency)】

CCRモデルの効率値(<math>CCR\,</math>)に対するスラックを考慮した効率値(<math>SLE\,</math>)の比で表される効率性である. したがって, ミックス効率値(<math>MIX\,</math>)は 

<center>
<math>MIX=\frac{SLE}{CCR}\,</math>
</center>

で定義される. スラックを考慮した効率値には, スラック基準効率値などがある.

マルムクイストの指標

2007-07-14T07:59:36Z

222.225.128.87:

【まるむくいすとのしひょう (Malmquist index)】

分析対象である活動(DMU)の効率性の時間的成長を測定する指標であり, マルムクイストの指標は<math>M_o^t(\mbox{y}_s, \mbox{y}_t, \mbox{x})= d_o^t(\mbox{x}, \mbox{y}_t)/d_o^t(\mbox{x},\mbox{y}_s)\,</math>により求められる. ただし, <math>d_o^t(\mbox{x}, \mbox{y}_s) = \min\left\{\delta |(\mbox{y}_s / \delta, \mbox{x}) \in S^t\right\}\,</math> である (<math>S^t\,</math>は <math>t\,</math> 期における活動領域). マルムクイストの指標はこの式のように, <math>s\,</math> 期における効率値を基準とした <math>t\,</math> 期の効率値の比により与えられる.

マルチンゲール

2007-07-14T07:50:03Z

222.225.128.87:

【まるちんげーる (martingale)】

<math>(\Omega, {\mathcal F}, \mathrm{P})\,</math>を確率空間, <math>\{ {\mathcal F}_t \}\,</math>を<math>\mathcal F\,</math>の増大する部分<math>\sigma\,</math>--集合体族とする. <math>\{ {\mathcal F}_t \}\,</math>に適合した確率過程<math>\{ X_t \}\,</math>が, 任意の<math>t\,</math>に対して <math>\mathrm{E}(|X_t|)<\infty\,</math> を満たし, さらに任意の<math>s, t\,</math>に対して 

<center>
<math>\mathrm{E}(X_t|{\mathcal F}_s) = X_s\,</math>
</center>
が確率1で成り立つ場合,<math>\{ X_t \}\,</math>をマルチンゲールと呼ぶ.

マルコフ連鎖

2007-07-14T07:45:14Z

222.225.128.87:

【まるこふれんさ (Markov chain)】

マルコフ性をもつ離散状態空間上の確率過程. すなわち, 確率過程<math>\{ X(t) \}\,</math> が, 任意の<math>s, t\,</math>と<math>i,j\,</math>に対して
 
<table align = center>
<tr><td><math>\mbox{P}(X(s+t)\,</math></td> <td><math>=j|X(u), \; 0 \leq u < s, X(s)=i)\,</math></td></tr>
<tr><td></td> <td><math>= \mbox{P}(X(s+t)=j|X(s)=i)\,</math></td></tr>
</table>
を満たす場合, マルコフ連鎖と呼ぶ.

マルコフ両決定過程

2007-07-14T07:39:14Z

222.225.128.87:

【まるこふりょうけっていかてい (Markov bidecision process)】

いわゆるマルコフ決定過程では割引き総利得の期待値を最大化している. 割引き率 <math> \beta \,</math> が状態と決定に依存して「割引き関数」<math> \beta(s,a) \,</math> になって, 負値をもとる過程を, マルコフ両決定過程という. この過程では最大化部分問題群ばかりでなく最小化部分問題群までを考えて埋め込む必要がある. このとき両最適値関数間に連立した再帰式(両帰式)が成り立つ.

マルコフ変調ポアソン過程

2007-07-14T07:38:34Z

222.225.128.87:

【まるこふへんちょうぽあそんかてい (Markov modulated Poisson process (MMPP))】

相の推移が連続時間有限状態マルコフ過程にしたがい, 相が状態 <math>i\,</math> にあるときこの <math>i\,</math> に従属した率 <math>\lambda_i\,</math> でポアソン到着が起るもの.

マルコフ政策

2007-07-14T07:37:27Z

222.225.128.87:

【まるこふせいさく (Markov policy)】

有限 <math> N \,</math> 段逐次決定過程における一連の決定列を定める関数列を政策という. 現在の時刻 <math> n \,</math> での状態のみに依存する決定は, 状態空間 <math> X \,</math> から決定空間 <math> U \,</math> への関数 <math> \pi_{n} : X \to U \,</math> で表わされる. 決定関数の列 <math> \pi = \{\pi_{1}, \pi_{2}, \ldots , \pi_{N} \} \,</math> をマルコフ政策という. 加法型最適化問題ではマルコフ政策クラスで最適化が実現され, 動的計画法の再帰式を解く過程で最適点関数を列挙することによって, 最適政策が得られる.

マルコフ過程

2007-07-14T07:18:58Z

222.225.128.87:

【まるこふかてい (Markov process)】

マルコフ性をもつ確率過程. すなわち, 確率過程 <math>\{ X(t) \}\,</math> が, 任意の時点 <math>s, t\,</math> と状態空間の任意の部分集合 <math>A\,</math> に対して
 
<center>
<math>\mbox{P}(X(s+t)\in A|X(u), \; 0 \leq u \leq s)= \mbox{P}(X(s+t) \in A|X(s))\,</math>
</center>

を満たすとき, マルコフ過程と呼ぶ. 状態空間が離散的である場合, マルコフ過程はマルコフ連鎖と呼ばれることが多い.

マルコフ過程

2007-07-14T07:18:46Z

222.225.128.87:

【まるこふかてい (Markov process)】

マルコフ性をもつ確率過程. すなわち, 確率過程 <math>\{ X(t) \}\,</math> が, 任意の時点 <math>s, t\,</math> と状態空間の任意の部分集合 <math>A\,</math> に対して
 
<center>
<math>\mbox{P}(X(s+t)\in A|X(u), \; 0 \leq u \leq s)= \mbox{P}(X(s+t) \in A|X(s))\,</math>
</center>
 
を満たすとき, マルコフ過程と呼ぶ. 状態空間が離散的である場合, マルコフ過程はマルコフ連鎖と呼ばれることが多い.

マルコフ過程

2007-07-14T07:17:37Z

222.225.128.87:

【まるこふかてい (Markov process)】

マルコフ性をもつ確率過程. すなわち, 確率過程 <math>\{ X(t) \}\,</math> が, 任意の時点 <math>s, t\,</math> と状態空間の任意の部分集合 <math>A\,</math> に対して
 
<center>
<math>\mbox{P}(X(s+t)\in A|X(u), \; 0 \leq u \leq s)= \mbox{P}(X(s+t) \in A|X(s))\,<math>
</center>
 
\[
\begin{array}{ll}
\mbox{P}(X(s+t) & \in A|X(u), \; 0 \leq u \leq s) \\
& \hspace*{10mm} = \mbox{P}(X(s+t) \in A|X(s))
\end{array}
\]

を満たすとき, マルコフ過程と呼ぶ. 状態空間が離散的である場合, マルコフ過程はマルコフ連鎖と呼ばれることが多い.

マルコフ型到着過程

2007-07-14T07:09:41Z

222.225.128.87:

【まるこふがたとうちゃくかてい (Markovian arrival process (MAP))】

到着までの状態(相)変化を表す推移速度行列 <math>T\,</math>, 相 <math>s_i\,</math> で到着がおき吸収状態 <math>\sigma_j\,</math> に推移する率 <math>u_{ij}\,</math> の行列 <math>U\,</math>, 吸収状態 <math>\sigma_j\,</math> から相 <math>s_k\,</math> へ推移する推移確率 <math>\alpha_{jk}\,</math> の行列 <math>\alpha\,</math> の3つの行列によって特徴づけられる到着過程. MAP(<math>T\,</math>, <math>U\,</math>, <math>\alpha\,</math>) と表記される. 到着間隔に相関があり, しかも有限状態のマルコフ連鎖で表現できる便利な到着モデルである. 積 <math>U \alpha\,</math> を1つの <math>m \times m\,</math> 行列 <math>D\,</math> で表し, この確率過程をMAP<math>(T,D)\,</math> と書くこともある.

マッチング (平面上の)

2007-07-14T07:05:48Z

222.225.128.87:

【まっちんぐ (matching in the plane)】

与えられた平面上の<math>n=2m\,</math>個の点集合に対して, 2点ずつペアにして<math>m\,</math>個のペアの集合(完全マッチング)<math>M\,</math>を作る問題で, 特に, ペアの重みをそのペアに含まれる2点間の距離(2点を結ぶ線分の長さ)とし, 完全マッチング<math>M\,</math>の重みを<math>M\,</math>に含まれる<math>m\,</math>個のペアの重みの総和として, 重みを最小にする完全マッチング<math>M^*\,</math>を見つける問題を平面最小重み完全マッチングという. この問題は<math>\mbox{O}(n^3)\,</math>の手間で解けるが, バケット法に基づけば近似的に<math>\mbox{O}(n)\,</math>の手間で解ける.

マッチング

2007-07-14T07:02:32Z

222.225.128.87:

【まっちんぐ (matching)】

無向グラフ <math>G = (V, E)\,</math> の枝部分集合 <math>M \subseteq A\,</math> で, どの2つの枝も端点を共有しないものをマッチングと呼ぶ. 枝部分集合 <math>M \subseteq A\,</math> がマッチングならば,<math>M\,</math> の枝に接続する点の数は <math>M\,</math> の要素数の2倍に等しく, またそのときに限って <math>M\,</math> はマッチングである. <math>k\,</math> 本の枝からなるマッチングを
<math>k\,</math>-マッチングと呼び, 特に <math>|V|/2\,</math> 本の枝からなるマッチングを完全マッチングと呼ぶ.

マックスマックス定理 (逐次過程における)

2007-07-14T06:59:39Z

222.225.128.87:

【まっくすまっくすていり (maximax theorem)】

最適性の原理の1つの表現. ミニマックス定理は凹凸性の下で成立するが, マックスマックス定理は再帰・単調性で成り立つ: 
<center>
<math>\mathop{{\rm max}}_{x \in X, y \in Y(x)}g(x;h(x,y)) = \mathop{{\rm max}}_{x \in X}g(x\,; \mathop{{\rm max}}_{y \in Y(x)}h(x,y)\,)
\,</math>
</center>
ここに, <math> g : X \times {\mathbf R}^{1} \to {\mathbf R}^{1} \,</math> は第2変数について非減少. これは2変数同時最適化は2段階逐次最適化に等しいことを述べている. この定理を逐次適用すると, 多変数最適化が1変数最適化の繰り返しで求められる.

待ち時間分布の裾

2007-07-14T06:54:03Z

222.225.128.87:

【まちじかんぶんぷのすそ (tail of waiting time distribution)】

定常状態での客の待ち時間<math>W\,</math>が閾値<math>x\,</math>を超える確率<math>\mbox{P}(W>x)\,</math>. 先着順サービスのG/G/1待ち行列では, 

<center>
<math>\mbox{P}(W>x)=\mbox{P}\left( \sup_{n\geq 0}\{A_n\}>x\right),A_n=\sum_{i=1}^n U_{-i}\,</math>
</center>

で与えられる. ただし, <math>U_i\,</math>は<math>i\,</math>番目の客のサービス時間と<math>i\,</math>番目と<math>i+1\,</math>番目の客の到着間隔の差.

待ち行列モデル MAP/MAP/c

2007-07-14T06:47:50Z

222.225.128.87:

【まちぎょうれつもでるまっぷまっぷしー (queueing model MAP/MAP/$c$)】

到着過程とサービス過程がマルコフ到着過程(MAP)にしたがい, 窓口が <math>c\,</math>個の待ち行列モデル. 到着間隔もサービス時間も再生過程ではなく相関が入る, かなり一般的なモデルである.

待ち行列モデル M/G/1

2007-07-14T06:45:08Z

222.225.128.87:

【まちぎょうれつもでるえむじーわん (queueing model M/G/1)】

客の到着がポアソン過程にしたがい, サービス時間が, 一般分布にしたがう窓口1個(扱い者1人)の無限長の待ち行列を許す最も基本的な待ち行列モデルの1つ. M/G/1 型の待ち行列は, M/G/1モデルから派生する種々の待ち行列を指し, 例えば有限待合室モデル(M/G/1/<math>{\it m}\,</math>), 有限呼源モデル (M(<math>{\it n}\,</math>)/G/1), 休暇時間を伴う待ち行列(バケーションモデル M/G/1 +Vacation)などがある.

待ち行列モデル M/M/1

2007-07-14T06:43:58Z

222.225.128.87:

【まちぎょうれつもでるえむえむわん (queueing model M/M/1)】

ポアソン到着, 指数サービス, 単一窓口の待ち行列モデル. 詳しくいうと, 客は平均 <math>1 / \lambda\,</math> の指数分布にしたがう間隔で到着し, 平均 <math>1/\mu\,</math> の指数分布にしたがう時間サービスを受けて退去する. 客の到着間隔とサービス時間はすべて互いに独立. 窓口は1個で, 客が到着したとき窓口が空いていれば直ちにサービスを受け始め, 塞がっていたら行列の最後尾について自分の順番を待つ. サービス終了時に待っている客がいれば, 待ち行列の先頭の客がサービスを受け始める.

待ち行列モデル M/M/c/c

2007-07-14T06:43:18Z

222.225.128.87:

【まちぎょうれつもでるえむえむしーしー (queueing model M/M/$c$/$c$)】

ポアソン到着, <math>c\,</math>個の指数サービス窓口があり, 待合室が無い待ち行列モデル. 客が到着したとき, サービスを受けている客が$c$人未満の場合は直ちにサービスを受けることができるが, サービスを受けている客が<math>c\,</math>人ならば, サービスを受けることなく立ち去る. このようにサービスを受けずに立ち去る客がある待ち行列は損失系と呼ばれ, 電話回線などのトラフィック理論でしばしば利用される.

待ち行列モデル M/M/c

2007-07-14T06:42:42Z

222.225.128.87:

【まちぎょうれつもでるえむえむしー (queueing model M/M/$c$)】

ポアソン到着, 指数サービス, 窓口が <math>c\,</math> 個の待ち行列モデル. 最も基本的な待ち行列モデルの1つ. 待ち行列モデルを指して "マルコフモデル" というときは, このモデルを指していることが多い.

待ち行列

2007-07-14T06:41:57Z

222.225.128.87:

【まちぎょうれつ (queue)】

(1)　サービスを待つ客が構成する行列のこと. 待ち行列モデルでは, 待合室もしくはバッファで形成される行列のこと. 
(2)　待ち行列モデルのこと.

ポリマトロイド

2007-07-14T06:39:41Z

222.225.128.87:

【ぽりまとろいど (polymatroid)】

有限集合 <math>N\,</math> と以下の条件 (P0)--(P2) を満たす関数 <math>\rho:2^N\to{\mathbf R}\,</math> の組 <math>(N,\rho)\,</math> をポリマトロイドという. 
(P0)　<math>\rho(\emptyset)=0\,</math>. 
(P1)　<math>X\subseteq Y \Rightarrow \rho(X)\leq\rho(Y)\,</math>. 
(P2)　<math>\forall X,Y\subseteq N\,</math>: <math>\rho(X)+\rho(Y)\geq\rho(X\cap Y)+\rho(X\cup Y)\,</math>.

ポラチェック・ヒンチンの公式

2007-07-14T06:33:47Z

222.225.128.87:

【ぽらちぇっくひんちんのこうしき (Pollaczek-Khintchine formula)】

待ち行列モデル M/G/1 における待ち時間分布 <math>W_q(t)\,</math> のラプラス・スチルチェス変換 <math>W^*(s)\,</math> を与える次の関係式のこと. 

<center>
<math>W_q^*(s) = (1-\rho)/ \left\{ 1-\lambda[1-H^*(s)]/s \right\}\,</math>
</center>

ただし, <math>\lambda\,</math> は到着率, <math>H^*(s)\,</math> はサービス時間 <math>H\,</math> のラプラス・スチルチェス変換, <math>\rho = \lambda \mbox{E}(H)\,</math> は利用率である. この関係式から導かれる平均待ち時間の公式 E<math>(W_q)=\lambda \mbox{E}(H^2)/[2(1-\rho)]\,</math> も同じ名前で呼ばれることがある.

ポテンシャル関数 (内点法の)

2007-07-14T06:31:53Z

222.225.128.87:

【ぽてんしゃるかんすう (potential function)】

標準形の線形計画問題「 <math> \mbox{min. } \ c^{\top}x \ \mbox{s.t.} \ Ax = b, \ x \geq 0\,</math> (<math>A\,</math>は<math>m \times n\,</math>行列, <math>b \in {\mathbf R}^m\,</math>, <math>c \in {\mathbf R}^n\,</math>)」に対する内点法で用いられるポテンシャル関数は, 

<center>
<math>f(x:\rho) := (n+\rho)\ln(c^{\top}x -c^*)-\sum_{j=1}^n \ln x_j\,</math>
</center>

(<math>c^*\,</math>は主問題の最小値, <math>\rho\,</math>はパラメータ)で与えられる. カーマーカーが初めて導入した関数であり, 既与の<math>\rho > 0\,</math>に対して, 正領域内の許容解の点列<math>\{x^k\}\,</math>が<math>f(x^k) \rightarrow -\infty\,</math> であるとき, その集積点はすべて最適解という性質をもつ.

ポテンシャル関数 (内点法の)

2007-07-14T06:31:38Z

222.225.128.87:

【ぽてんしゃるかんすう (potential function)】

標準形の線形計画問題「 <math> \mbox{min. } \ c^{\top}x \ \mbox{s.t.} \ Ax = b, \ x \geq 0\,</math> (<math>A\,</math>は<math>m \times n\,</math>行列, <math>b \in {\mathbf R}^m\,</math>, <math>c \in {\mathbf R}^n\,</math>)」に対する内点法で用いられるポテンシャル関数は, 

<center>
<math>f(x:\rho) := (n+\rho)\ln(c^{\top}x -c^*)-\sum_{j=1}^n \ln x_j\,</math>
</center> 

(<math>c^*\,</math>は主問題の最小値, <math>\rho\,</math>はパラメータ)で与えられる. カーマーカーが初めて導入した関数であり, 既与の<math>\rho > 0\,</math>に対して, 正領域内の許容解の点列<math>\{x^k\}\,</math>が<math>f(x^k) \rightarrow -\infty\,</math> であるとき, その集積点はすべて最適解という性質をもつ.

ポテンシャル関数 (内点法の)

2007-07-14T06:29:59Z

222.225.128.87:

【ぽてんしゃるかんすう (potential function)】

標準形の線形計画問題「 <math> \mbox{min. } \ c^{\top}x \ \mbox{s.t.} \ Ax = b, \ x \geq 0\,</math> (<math>A\,</math>は<math>m \times n\,</math>行列, <math>b \in {\mathbf R}^m\,</math>, <math>c \in {\mathbf R}^n\,</math>)」に対する内点法で用いられるポテンシャル関数は,

<center>
<math>f(x:\rho) := (n+\rho)\ln(c^{\top}x -c^*)-\sum_{j=1}^n \ln x_j\,</math>
</center>

(<math>c^*\,</math>は主問題の最小値, <math>\rho\,</math>はパラメータ)で与えられる. カーマーカーが初めて導入した関数であり, 既与の<math>\rho > 0\,</math>に対して, 正領域内の許容解の点列<math>\{x^k\}\,</math>が<math>f(x^k) \rightarrow -\infty\,</math> であるとき, その集積点はすべて最適解という性質をもつ.

ポテンシャル関数 (内点法の)

2007-07-14T06:29:42Z

222.225.128.87:

【ぽてんしゃるかんすう (potential function)】

標準形の線形計画問題「 <math> \mbox{min. } \ c^{\top}x \ \mbox{s.t.} \ Ax = b, \ x \geq 0\,</math> (<math>A\,</math>は<math>m \times n\,</math>行列, <math>b \in {\mathbf R}^m\,</math>, <math>c \in {\mathbf R}^n\,</math>)」に対する内点法で用いられるポテンシャル関数は,

<center>
<math>f(x:\rho) := (n+\rho)\ln(c^{\top}x -c^*)-\sum_{j=1}^n \ln x_j\,</math>
<center>

(<math>c^*\,</math>は主問題の最小値, <math>\rho\,</math>はパラメータ)で与えられる. カーマーカーが初めて導入した関数であり, 既与の<math>\rho > 0\,</math>に対して, 正領域内の許容解の点列<math>\{x^k\}\,</math>が<math>f(x^k) \rightarrow -\infty\,</math> であるとき, その集積点はすべて最適解という性質をもつ.

ホップフィールドネットワーク

2007-07-14T06:27:11Z

222.225.128.87:

【ほっぷふぃーるどねっとわーく (Hopfield network)】

1982年ホップフィールド(J.J. Hopfield)により提案されたニューラルネットワークモデルである. 各辺が定係数<math>T_{ij}=T_{ji}\,</math> をもつ自己ループのない相互結合ネットワークにおいて, 0または1をとる変数<math>V_i\,</math> に関するエネルギー関数

<center>
<math>E = -\sum_j \sum_{i \neq j} T_{ij} V_i V_j \,</math>
</center>
の最小化に際し, ランダムに <math>i\,</math> を選び, 次の反復を行う. 連続値モデルもある.

<center>
<math>V_i :=f\left( \sum_{j\neq i} T_{ij}V_j\right)\,</math>
</center>

ただし, <math>f(\cdot)\,</math>はマッカロック (McCulloch) とピッツ (Pitts) のしきい値関数である.

補助変数法

2007-07-14T06:24:40Z

222.225.128.87:

【ほじょへんすうほう (supplementary variable method)】

例えば M/G/1 において, 時刻 <math>t\,</math> の系内客数を <math>\xi(t)\,</math>, サービス経過時間を <math>X(t)\,</math>, 残余サービス時間を <math>R(t)\,</math> と表せば, 確率過程 <math>\{\xi(t)\}\,</math>はマルコフ過程とはならないが, ベクトル過程 <math>\zeta_X(t) = \{\xi(t), X(t)\}\,</math> および <math>\zeta_R(t) = \{\xi(t), R(t)\}\,</math> は, マルコフ過程となる. 確率変数 <math>X(t)\,</math>, <math>R(t)\,</math> を補助変数といい, 適当な補助変数の導入により, マルコフ化が可能となる. この解析法を補助変数法という.

捕食者/被食者モデル

2007-07-14T06:23:16Z

222.225.128.87:

【ほしょくしゃ / ひしょくしゃもでる (prey/predator model)】

捕食者/被食者モデルは1920年代にロトカ (Lotka) とボルテラ (Volterra) が独立に提起したモデルで, 微分方程式は一般にロトカ・ボルテラ方程式と呼ばれる. 捕食者数<math>N_2\,</math>, 被食者数<math>N_1\,</math>は次の微分方程式にしたがう.

　　　<math>{\mathrm d} N_1/{\mathrm d}t=N_1(a_1-b_1N_2-c_1 N_1)\,</math>
 

　　　<math>{\mathrm d} N_2/{\mathrm d}t=N_2(-a_2+b_2 N_1)\,</math>
 
ここで, <math>a_1,~a_2,~b_1,~b_2,~c_1\geq 0\,</math>である.

ホールの定理

2007-07-14T06:13:27Z

222.225.128.87:

【ほーるのていり (Hall's theorem)】

2部グラフ <math>G = (V^+, V^-; A)\,</math> において, 左側点集合 <math>V^+\,</math> に関する完全マッチングが存在するための必要十分条件は次のように書ける:
 
<center>
<math>|U^+| \leq |\{v \in V^- \mid \ u \in U^+, (u, v) \in A\}|, \forall U^+ \subseteq V^+ .\,</math>
</center>
 
この不等式の右辺は, <math>U^+\,</math> 中に左側点をもつ枝の右側点の数を表す.この必要十分条件をホールの定理と呼ぶ. ケーニグ・ホールの定理 (K\"onig--Hall's Theorem) と呼ばれることもある.

ホーキンス・サイモン条件

2007-07-14T05:20:54Z

222.225.128.87:

【ほーきんすさいもんじょうけん (Hawkins-Simon's condition)】

産業連関表によって計算される生産額ベクトル<math>X\,</math>の各要素は非負でなければならない.投入係数を<math>A\,</math>とすると, このための必要十分条件は<math>|I-A| > 0\,</math>で与えられる. これはホーキンス・サイモンの条件と呼ばれている. <math>I\,</math>は単位行列である.

ポアソン分布

2007-07-14T05:19:30Z

222.225.128.87:

【ぽあそんぶんぷ (Poisson distribution)】

非負整数値 <math>\{0,1,2,3,\ldots\}\,</math> をとる離散型分布の1つ. 実数 <math>\lambda > 0\,</math> をパラメータとして, 確率関数は <math>p(k)=\mathrm{e}^{-\lambda}\lambda^k/k!,\;k=0,1,2,\ldots\,</math> で与えられる. 平均と分散はともに<math>\lambda\,</math>である.

ポアソン到着

2007-07-14T05:18:38Z

222.225.128.87:

【ぽあそんとうちゃく (Poisson arrivals)】

待ち行列モデルにおいて, 客がポアソン過程にしたがって到着する到着過程. 正数 <math>\lambda\,</math> をパラメータにもつポアソン到着では, 時間区間 <math>(t,t+\tau]\,</math> の間に <math>k\,</math> 人の客が到着する確率が e<math>^{-\lambda \tau}(\lambda \tau)^k/k!\,</math> で与えられ, 区間の起点 <math>t\,</math> とは独立である. また, 長さ <math>\tau\,</math> の時間区間内に到着する平均客数は <math>\lambda \tau\,</math> で与えられる.非常に長い期間<math>[0,T]\,</math> の間に <math>\lambda T\,</math> 個の到着時点を互いに独立に <math>[0,T]\,</math> 上の一様分布にしたがってとったときの到着過程とも解釈でき, もっともランダムな到着過程である.

ポアソン過程

2007-07-14T05:16:44Z

222.225.128.87:

【ぽあそんかてい (Poisson process)】

<math>\Lambda(t)\,</math> を連続な非減少実数値関数とする. 計数過程 <math>\{N(t)\}\,</math> が平均測度 <math>\{\Lambda(t)\}\,</math> をもつ
(非定常)ポアソン過程であるとは次を満たすことである. 

　(1) <math>\{N(t)\}\,</math> は独立増分をもつ. 
　(2) <math>u < v\,</math> に対し <math>N(v) - N(u)\,</math> は平均 <math>\Lambda(v) - \Lambda(u)\,</math>のポアソン分布にしたがう.

<math>\Lambda(t)\,</math> が微分可能なときは <math>\lambda(t)=\Lambda'(t)\,</math> が <math>\{N(t)\}\,</math> の強度となる. 特に, <math>\lambda(t)\,</math> が定数のときは定常ポアソン過程である.

辺連結度

2007-07-14T05:11:47Z

222.225.128.87:

【へんれんけつど (edge connectivity)】

無向(有向)グラフ<math>G\,</math>の辺の部分集合は, それを除去するとグラフが連結(強連結)でなくなるとき, 辺カットという. 辺連結度<math>\lambda(G)\,</math>は辺カットの大きさの最小値. グラフの辺に重みがついている場合には, 辺カットの辺の重み和の最小値.

辺分離定理

2007-07-14T05:11:03Z

222.225.128.87:

【へんぶんりていり (edge splitting theorem)】

無向(有向)グラフにおいて1つの点<math>s\,</math>を選び, <math>s\,</math>に接続する2本の(有向)辺<math>(u,s),(s,v)\,</math>を1本の(有向)辺<math>(u,v)\,</math>に取り替える操作を辺分離という. このとき, <math>s\,</math>に接続する2本の辺をうまく選ぶと辺分離後も, グラフの辺連結度(正確には<math>s\,</math>以外の2点間の局所辺連結度の最小値)を変化させずに保つことができる.特に, 無向グラフに対しては(特殊な場合を除き), 辺分離後に<math>s\,</math>以外のすべての2点間の局所辺連結度を変化させない2本の辺の選択が存在する.