形式的定義
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2016/12/06 00:17 UTC 版)
「交替性チューリング機械」の記事における「形式的定義」の解説
形式的には(テープが一本の)交替性チューリング機械は、5-タプル M = ( Q , Γ , δ , q 0 , g ) {\displaystyle M=(Q,\Gamma ,\delta ,q_{0},g)} で表され、それぞれは以下のような意味を持つ。 Q {\displaystyle Q} は、状態の有限集合 Γ {\displaystyle \Gamma } は、テープ上のアルファベットの有限集合 δ : Q × Γ → P ( Q × Γ × { L , R } ) {\displaystyle \delta :Q\times \Gamma \rightarrow {\mathcal {P}}(Q\times \Gamma \times \{L,R\})} は、遷移関数(L はヘッドを左に移動させ、R はヘッドを右に移動させる) q 0 ∈ Q {\displaystyle q_{0}\in Q} は、初期状態 g : Q → { ∧ , ∨ , a c c e p t , r e j e c t } {\displaystyle g:Q\rightarrow \{\wedge ,\vee ,accept,reject\}} は、各状態の種類を指定する関数 M が状態 q ∈ Q {\displaystyle q\in Q} にあり、 g ( q ) = a c c e p t {\displaystyle g(q)=accept} なら、受理状態であることを示している。また g ( q ) = r e j e c t {\displaystyle g(q)=reject} なら、拒絶状態であることを示している。 g ( q ) = ∧ {\displaystyle g(q)=\wedge } なら、1ステップで到達可能な全ての構成が受理状態であれば、受理状態であるし、1ステップで到達可能な状態の中に拒絶状態のものがあれば、拒絶状態である。 g ( q ) = ∨ {\displaystyle g(q)=\vee } なら、1ステップで到達可能な状態の中に受理状態のものがあれば、受理状態であるし、1ステップで到達可能な全ての構成が拒絶状態であれば、拒絶状態である(通常の NTM は全てこの状態)。M が入力文字列 w を受理するとは、M の初期構成(Mの状態が q 0 {\displaystyle q_{0}} で、ヘッドはテープの左端にあり、テープには w がある)が受理状態であることを意味し、初期構成が拒絶状態なら拒絶する。
※この「形式的定義」の解説は、「交替性チューリング機械」の解説の一部です。
「形式的定義」を含む「交替性チューリング機械」の記事については、「交替性チューリング機械」の概要を参照ください。
形式的定義
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2016/06/06 09:16 UTC 版)
「文脈自由言語の反復補題」の記事における「形式的定義」の解説
任意の文脈自由言語 L に対して,(反復長 (pumping length) と呼ばれる)ある正の整数 p > 0 が存在し、L 内の |w| ≥ p となる任意の文字列 w を以下のように表すことができる: w = uvxyz 全ての0以上の整数 i ≥ 0 について uv ixy iz が L に含まれる。 なお、文字列 a と b があるとき ab はその連結した文字列を表し、|a| は a の長さを表す。また、ai は a を i 回反復した文字列を表す。
※この「形式的定義」の解説は、「文脈自由言語の反復補題」の解説の一部です。
「形式的定義」を含む「文脈自由言語の反復補題」の記事については、「文脈自由言語の反復補題」の概要を参照ください。
形式的定義
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2017/07/28 08:15 UTC 版)
母集団分布を F とするとき、母集団から抽出された(無作為)標本 (random sample) とは分布 F に従う独立同分布確率変数列 x1, x2, ... のことである。確率変数列の長さを標本のサイズという。とりうる標本の全体が成す集合 Ω, 確率を定めうる集合の全体 M (⊂ 2^Ω), 分布を表す確率測度 P からなる確率空間 (Ω, M, P) を標本空間という。 例えば母集団の分布 F が母平均 E[X] = m, 母分散 V[X] = σ2 を持つならば、標本 x1, x2, ... は i を任意の番号として平均 E[xi] = m, 分散 V[xi] = σ2 を満たす。 標本から適当な操作を行って新たに作り出される確率変数を統計量と呼ぶ。統計量は(同じ量でも)標本の採り方に依存して定まり、一般に母集団の分布とは異なる分布に従う。統計量の従う分布を標本分布と呼ぶ。 例えば標本 x = (x1, x2, ..., xn) に対し、その平均 x ¯ := x 1 + x 2 + ⋯ + x n n {\displaystyle {\bar {\mathbf {x} }}:={\frac {x_{1}+x_{2}+\cdots +x_{n}}{n}}} を取る操作を考えるとき、x の標本 x の取り方をさまざまに考えるものとして得られる確率変数は統計量である。この統計量は標本平均と呼ばれ、X などで表す。母集団の分布 F が母平均 E[X] = m, 母分散 V[X] = σ2 を持つならば、標本平均 X の従う標本分布について、平均 E[X] = m, 分散 V[X] = σ2/n を得る。
※この「形式的定義」の解説は、「標本 (統計学)」の解説の一部です。
「形式的定義」を含む「標本 (統計学)」の記事については、「標本 (統計学)」の概要を参照ください。
形式的定義
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2021/06/02 05:58 UTC 版)
標準的用語は存在しない。書籍によって個々に用語やシンボルを定義している。多くの場合、「レジスタ転送」的な記号を使うが、構文定義はその都度行う必要がある。 レジスタマシンは以下のような要素から成る。 有限個数でかつ無限長のレジスタ: 有限個(またはモデルによっては無限個)のレジスタ群 r0, ..., rn があり、個々のレジスタは無限長で1つの非負整数(0, 1, 2, ...)を格納する。レジスタ同士の算術ができるか、一部のレジスタがアキュムレータとして算術に使われたり、アドレスレジスタとして使われたりする。 タリーカウンタ/マーク: モデルにおける離散的識別可能オブジェクト/マーク。最も単純なカウンタマシンでは、1回の算術演算で1つのオブジェクト/マークが追加または削除される(つまり、インクリメントまたはデクリメント)。Melzak (1961) や Minsky (1961) のカウンタマシンや RAM または RASP では、1回の加算や減算で1つ以上のオブジェクト/マークの追加・削除が行われる。モデルによっては、コピー制御命令によってオブジェクト/マークの「かたまり」をレジスタからレジスタに1回の操作で移動させることができる。 (非常に)制限された命令セット: 命令は算術演算命令と制御命令の2種類に分類される。「命令セット」はそのモデルがチューリング等価となるよう選択される(つまり、任意の計算可能関数を計算可能である)。算術演算命令: 全レジスタを対象に実行できる場合とアキュムレータだけを対象に実行できる場合がある。次のようなセットから選択される(例外もある)。カウンタマシン: {インクリメント (r)、デクリメント (r)、ゼロクリア (r)} 最小構成 RAM、RASP: {インクリメント (r)、デクリメント (r)、ゼロクリア (r)、即値ロード k、加算 (r1,r2)、減算 (r1,r2)、インクリメント アキュムレータ、デクリメント アキュムレータ、クリア アキュムレータ、レジスタ r の内容をアキュムレータに加算、レジスタ r の内容をアキュムレータから減算、} 最大構成 RAM、RASP: 上記に加えて {乗算、除算、各種ビット論理演算(左シフト、ビットテストなど)} 制御命令:カウンタマシン: オプションで {コピー (r1,r2)} RAM、RASP: {コピー (r1,r2)} または {r からアキュムレータへのロード、アキュムレータから r へのストア、即値のアキュムレータへのロード} のどちらかが必須 全モデル: レジスタ内容のテストを伴う条件付き分岐命令が少なくとも1つ必要。例えば {ゼロのとき分岐、ゼロでないとき分岐、等しいとき分岐、等しくないとき分岐} 全モデルでオプション: { 無条件分岐(GOTO) } レジスタ指定方法:カウンタマシン: 間接指定(レジスタの内容が別のレジスタの番号を指定)はなく、オペランドで直接指定する。 RAM、RASP: 間接指定可能で、オペランドでの直接指定もある。 入出力: 全モデルでオプション 状態レジスタ: 上述のレジスタ群とは別に、命令レジスタ(IR)に現在の命令と命令テーブル上のその命令のアドレスを格納する。このレジスタと命令テーブルは有限状態機械内にある。IR はモデル上はアクセスできない。RAM や RASP でレジスタのアドレス指定をする場合、命令テーブルまたはIRの内容で直接指定されるか、IR内の命令で指定されるレジスタの内容で間接指定される。 IR はいわゆる「プログラムカウンタ」(PC)ではない。RASP には PC もあり、これはアキュムレータのようなレジスタであり、現在のレジスタ上の命令を指す。RASP はさらに第三のレジスタ「プログラム命令レジスタ」も持つ場合がある。 ラベル付き命令のリスト、一般に逐次的順序: 有限な命令列 I1, ..., Im。カウンタマシン、RAM、ポインタマシンの場合、命令は有限状態機械内のテーブルに格納される。したがって、これらは一種のハーバード・アーキテクチャであり、命令とデータが明確に分離されている。RASP の場合、プログラムはレジスタに格納される。したがって、RASP はノイマン型アーキテクチャの一種である。一般的なプログラムのように命令は逐次的順序で置かれ、分岐が発生する場合以外は命令は逐次的に実行される。例外として、Lambek (1961) や Minsky (1961) の abacus カウンタマシンモデルがある。この場合、各命令には少なくとも1つの次の命令を指す識別子 "z" があり、条件付き分岐命令ではそれが2つになる。abacus モデルにはデクリメントと条件付き分岐を1つに組み合わせた命令(JZ + DEC = JZDEC)がある。例えば、{ INC ( r, z ), JZDEC ( r, ztrue, zfalse ) } のようになる。
※この「形式的定義」の解説は、「レジスタマシン」の解説の一部です。
「形式的定義」を含む「レジスタマシン」の記事については、「レジスタマシン」の概要を参照ください。
形式的定義
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2018/12/26 02:14 UTC 版)
組合せ最適化問題のインスタンスは、 ( X , P , Y , f , e x t r ) {\displaystyle (X,P,Y,f,\mathrm {extr} )} の要素の組 (tuple) として形式的に記述できる。 ここで X は解空間(solution space、その中に f と P が定義されている) P は実現可能かどうかを判定する関数 Y は実現可能な解の集合 f は最適化関数 extr は極値(extreme、最大または最小)
※この「形式的定義」の解説は、「組合せ最適化」の解説の一部です。
「形式的定義」を含む「組合せ最適化」の記事については、「組合せ最適化」の概要を参照ください。
形式的定義
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2022/01/01 00:50 UTC 版)
ベルヌーイ過程は、確率空間の言語で形式化される。ベルヌーイ過程は、集合 { 0 , 1 } {\displaystyle \{0,1\}} に関する確率変数 X を伴う確率空間 ( Ω , P r ) {\displaystyle (\Omega ,Pr)} であり、全ての ω ∈ Ω {\displaystyle \omega \in \Omega } について、確率 p で X i ( ω ) = 1 {\displaystyle X_{i}(\omega )=1} となり、確率 1-p で X i ( ω ) = 0 {\displaystyle X_{i}(\omega )=0} となる。
※この「形式的定義」の解説は、「ベルヌーイ過程」の解説の一部です。
「形式的定義」を含む「ベルヌーイ過程」の記事については、「ベルヌーイ過程」の概要を参照ください。
形式的定義
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2020/05/16 09:30 UTC 版)
モノイド圏 (C, ⊗, I, α, λ, ρ) は、以下に挙げる構造を備える圏 C を言う: テンソル積あるいはモノイド積と呼ばれる双函手 ⊗: C × C → C, モノイド単位あるいは単位対象と呼ばれる対象 I, テンソル積が以下の条件を満足するという事実を表す、ある種の整合性条件を満足する三つの自然同型 α および λ, ρ:結合律: 各三対象 A, B, C に対する成分が同型 α A , B , C : ( A ⊗ B ) ⊗ C ≅ A ⊗ ( B ⊗ C ) {\displaystyle \alpha _{A,B,C}\colon (A\otimes B)\otimes C\cong A\otimes (B\otimes C)} で与えられる、結合子 (associator) と呼ばれる自然同型 α が存在する。 左単位律および右単位律: 成分がそれぞれ λ A : I ⊗ A ≅ A , ρ A : A ⊗ I ≅ A {\displaystyle \lambda _{A}\colon I\otimes A\cong A,\quad \rho _{A}\colon A\otimes I\cong A} で与えられ、それぞれ左単位子、右単位子 (unitor) と呼ばれるふたつの自然同型 λ, ρ が存在する。 ここで、これらの自然変換に対する整合性条件とは次のようなものである。 C の任意の対象 A, B, C, D に対し、図式 は可換である。 C の任意の対象 A に対し、図式 は可換である。 自然変換 α, λ, ρ が恒等変換である(すなわち結合律、単位律が同型でなく等号で成立する)ようなモノイド圏は、強モノイド圏、狭義モノイド圏、厳密モノイド圏 (strict monoidal category) などと呼ぶ。任意のモノイド圏は、ある強モノイド圏にモノイド同値である。
※この「形式的定義」の解説は、「モノイド圏」の解説の一部です。
「形式的定義」を含む「モノイド圏」の記事については、「モノイド圏」の概要を参照ください。
形式的定義
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2022/03/09 08:27 UTC 版)
形式的には、決定的アルゴリズムは有限状態機械で定義される。この場合、ある「状態」はある時点でその機械が何をしているかを表している。有限状態機械はある状態から別の状態へ厳密に遷移する。有限状態機械が決定的(決定性)であるとは、ある入力を与えられたときにその機械が通る状態遷移の経路が常に同じであることを意味する。 決定性のある計算模型の例としては、決定性チューリング機械や決定性有限状態機械がある。
※この「形式的定義」の解説は、「決定的アルゴリズム」の解説の一部です。
「形式的定義」を含む「決定的アルゴリズム」の記事については、「決定的アルゴリズム」の概要を参照ください。
形式的定義
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2021/01/16 04:57 UTC 版)
「モナド (プログラミング)」の記事における「形式的定義」の解説
モナドは、元となる型システムが与えられたとき、その内部に対応する型システム(モナド的型システムと呼ぶ)を埋め込む構成である(つまり、各モナド的型は元のシステムの型でもある)。このモナド的型システムは元の型システムの重要な点は全て保存するが、モナドに固有の特徴を追加する。 モナドは複数の方法で定義できる。そのうちの1つは「モナドとは、ある法則(モナド則)を満たす三つ組みである」 で表される定義である。すなわち圏論のクライスリ圏におけるクライスリトリプルである。
※この「形式的定義」の解説は、「モナド (プログラミング)」の解説の一部です。
「形式的定義」を含む「モナド (プログラミング)」の記事については、「モナド (プログラミング)」の概要を参照ください。
形式的定義
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2022/05/05 13:59 UTC 版)
形式的に、集合 X の部分集合からなる完全加法族 A 上で定義される可算加法的測度 μ とは拡張された区間 [0, ∞] に値を持つ(つまり、無限大も許す非負値の)関数であって、次の性質を満たすもののことである: 空集合の測度は 0 である。 μ ( ∅ ) = 0. {\displaystyle \mu (\emptyset )=0.} 完全加法性(可算加法性):E1, E2, E3, ... がどの二つも互いに共通部分を持たない A に属する集合の列ならば μ ( ⋃ i E i ) = ∑ i μ ( E i ) {\displaystyle \mu \left(\bigcup _{i}E_{i}\right)=\sum _{i}\mu (E_{i})} A の元は可測集合 (measurable sets) と呼ばれる。 また、数学的構造 (X, A, μ ) は 測度空間 (measure space) と呼ばれる。次の性質は、上の定義から導かれるものである: 単調性:E1 と E2 が可測集合で E1 ⊆ E2 を満たすならば、 μ ( E 1 ) ≤ μ ( E 2 ) {\displaystyle \mu (E_{1})\leq \mu (E_{2})} E1, E2, E3, ... が可測集合の列で、各 n において En ⊆ En+1 ならば、En たちの和集合は可測で μ ( ⋃ i E i ) = lim i μ ( E i ) {\displaystyle \mu \left(\bigcup _{i}E_{i}\right)=\lim _{i}\mu (E_{i})} E1, E2, E3, ... が可測集合の列で、各 n において En ⊇ En+1 ならば、En たちの共通部分も可測である。さらに、少なくとも 1 つの n について En の測度が有限値であるならば μ ( ⋂ i E i ) = lim i μ ( E i ) {\displaystyle \mu \left(\bigcap _{i}E_{i}\right)=\lim _{i}\mu (E_{i})}
※この「形式的定義」の解説は、「測度論」の解説の一部です。
「形式的定義」を含む「測度論」の記事については、「測度論」の概要を参照ください。
形式的定義
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2020/04/04 15:34 UTC 版)
次の定義が適用される。 確率変数のクラス C {\displaystyle {\mathcal {C}}} が一様可積分であるとは、 ϵ > 0 {\displaystyle \epsilon >0} が与えられた時、 E ( | X | I | X | ≥ K ) ≤ ϵ {\displaystyle E(|X|I_{|X|\geq K})\leq \epsilon } がすべての X ∈ C {\displaystyle X\in {\mathcal {C}}} に対して成立するような K ∈ [ 0 , ∞ ) {\displaystyle K\in [0,\infty )} が存在することを言う。ただし I | X | ≥ K {\displaystyle I_{|X|\geq K}} は指示関数 I | X | ≥ K = { 1 if | X | ≥ K , 0 if | X | < K {\displaystyle I_{|X|\geq K}={\begin{cases}1&{\text{if }}|X|\geq K,\\0&{\text{if }}|X|
※この「形式的定義」の解説は、「一様可積分性」の解説の一部です。
「形式的定義」を含む「一様可積分性」の記事については、「一様可積分性」の概要を参照ください。
形式的定義
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2022/08/01 09:51 UTC 版)
演繹(または証明)は、命題論理のような形式体系の文脈では正確に定義できる。命題 α は、前提の集合 Σ に推論規則を繰り返し適用することで演繹される。演繹は、この推論規則の繰り返し適用の記録である。 より形式的には、命題の有限な列 β1 ,..., βn が、前提の集合 Σ からの α の演繹であるとは、次が成り立つ場合である。 βn = α であり、かつ 全ての 1 ≤ i ≤ n について、βi が前提であるか(すなわち、βi ∈ Σ)または βi がそれ以前に出現した命題に何らかの推論規則を適用した結果である。 公理的命題論理のバージョンによって採用する公理や推論規則が異なる。例えば、フレーゲは、6つの公理と2つの規則を採用した。バートランド・ラッセルとアルフレッド・ノース・ホワイトヘッドは、5つの公理からなる体系を示唆した。 ヤン・ウカシェヴィチによる公理的命題論理のバージョンでは、次のような公理群 A を採用した。 [PL1] p → (q → p) [PL2] (p → (q → r)) → ((p → q) → (p → r)) [PL3] (¬p → ¬q) → (q → p) そして、推論規則 R としては、モーダスポネンスを採用した。 [MP] α と α → β から、β を推論する。 推論規則により、Σ に含まれる論理式と公理群から新たな論理式を導出できる。
※この「形式的定義」の解説は、「自然演繹」の解説の一部です。
「形式的定義」を含む「自然演繹」の記事については、「自然演繹」の概要を参照ください。
形式的定義
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2021/09/01 03:27 UTC 版)
「チャージ (物理学)」の記事における「形式的定義」の解説
より抽象的には、チャージは対象とする物理系の連続対称性の任意の生成作用素(生成演算子)である。物理系がある種の対称性を持つとき、ネーターの定理は保存カレントの存在を示唆する。カレントにおいて“流れているもの”がチャージに相当し、チャージは(局所)対称性の生成演算子である。このチャージは、ネーターチャージと呼ばれることがある。 例えば、電磁気学においては、U(1)対称性の生成演算子が電荷であり、保存するカレントは電流である。 局所的には、あらゆるチャージと関連する力学的な対称性はゲージ場である。[訳語疑問点] この理論では、チャージはそのゲージ場を"放射"する。このように考えたとき、例えば、電磁気学のゲージ場は電磁場であり、ゲージ粒子は光子である。 "チャージ"という言葉は、対称性の生成演算子を言及する"生成演算子"の類義語として使われることがある。より正確には、対称群がリー群のとき、そのチャージはリー群のルート系に一致するものとして理解することができ、ルート系の離散性によってチャージの量子化を説明することができる。
※この「形式的定義」の解説は、「チャージ (物理学)」の解説の一部です。
「形式的定義」を含む「チャージ (物理学)」の記事については、「チャージ (物理学)」の概要を参照ください。
形式的定義
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2022/05/14 04:54 UTC 版)
「非決定性有限オートマトン」の記事における「形式的定義」の解説
非決定性有限オートマトン(NFA)は、 { S , Σ , T , s 0 , A } {\displaystyle \{S,\Sigma ,T,s_{0},A\}} の5つの要素から構成され、各要素は以下のような性質を持つ。 状態の有限集合( S {\displaystyle S} ) 入力文字の有限集合( Σ {\displaystyle \Sigma } ) 遷移関数( T : S × ( Σ ∪ ε ) → P ( S ) {\displaystyle T:S\times (\Sigma \cup {\varepsilon })\rightarrow P(S)} ) 状態 s 0 {\displaystyle s_{0}} を特に「初期(または開始)状態」として区別する( s 0 ∈ S {\displaystyle s_{0}\in S} ) 状態の集合 A {\displaystyle A} を特に「受容(または終了)状態」として区別する( A ⊆ S {\displaystyle A\subseteq S} ) ここで P ( S ) {\displaystyle P(S)} は S {\displaystyle S} の冪集合であり、 ε {\displaystyle \varepsilon } は空の文字列であり、 Σ {\displaystyle \Sigma } は入力文字群である。 M {\displaystyle \mathbf {M} } が M = ( S , Σ , T , s 0 , A ) {\displaystyle \mathbf {M} =(S,\Sigma ,T,s_{0},A)} で構成される NFA で、 X {\displaystyle X} が Σ {\displaystyle \Sigma } に含まれる文字で構成された文字列とする。 M {\displaystyle \mathbf {M} } が文字列 X {\displaystyle X} を受容するのは、以下の条件が成立した場合である。まず、 X {\displaystyle X} を x 1 , x 2 ⋯ x n , x i ∈ ( Σ ∪ ε ) {\displaystyle x_{1},x_{2}\cdots x_{n},x_{i}\in (\Sigma \cup {\varepsilon })} と表したときに、これを入力された M {\displaystyle \mathbf {M} } がとる状態遷移が r 0 , r 1 , ⋯ r n , r i ∈ S {\displaystyle r_{0},r_{1},\cdots r_{n},r_{i}\in S} のようになるとき、以下の条件が成り立つ。 r 0 = s 0 {\displaystyle r_{0}=s_{0}} r i ∈ T ( r i − 1 , x i ) , f o r i = 1 , ⋯ , n {\displaystyle r_{i}\in T(r_{i-1},x_{i}),for\,i=1,\cdots ,n} r n ∈ A {\displaystyle r_{n}\in A} マシンは初期状態 s 0 {\displaystyle s_{0}} から開始され、入力文字列を読み込む。オートマトンは遷移関数 T {\displaystyle T} に現在状態と入力文字(あるいは空の文字)を与えて次に遷移すべき状態を得る。しかし、「NFA の次の状態は現在の入力イベントのみで決定されるのではなく、その後の任意個数の入力イベント(文字列)にも影響される。NFAが影響される入力イベントが続く限り、次の遷移先を決定することはできない」。オートマトンが読み込みを終了したときに受容状態にあれば、NFA はその入力文字列を受容したと言える。さもなくば、その入力文字列は拒否されたと見なされる。 ある NFA が受容する文字列全体の集合が NFA の受容する言語である。この言語は正規言語の範囲に一致する。
※この「形式的定義」の解説は、「非決定性有限オートマトン」の解説の一部です。
「形式的定義」を含む「非決定性有限オートマトン」の記事については、「非決定性有限オートマトン」の概要を参照ください。
形式的定義
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2021/04/18 17:52 UTC 版)
半順序集合 (P, ≤) 上の要素 c が以下の同値な条件を満たすとき、コンパクト(あるいは有限)と呼ばれる: P の任意の有向部分集合 D に対して、D が上限 sup D を持ち、かつ c ≤ sup D ならば c ≤ d を満たす D の元 d が存在する。 P の任意のイデアル I に対して、I が 上限 sup I を持ち、かつ c ≤ sup I ならば、c は I の元である。 さらに、半順序集合 P が結び半束(すなわち、任意の二元の上限が存在する)であるとき、これらの条件は以下の命題と同値である: P の空でない部分集合 S に対して、S が上限 sup S を持ち、かつ c ≤ sup S ならば、c ≤ sup T である S の有限部分集合 T が存在する。 特に、c = sup S のとき、c は有限部分集合 S の上限である。 これらの同値性は、関連する概念の定義から簡単に導かれる。結び半束の場合、有限の(空でない)上限で閉じることによって、任意の集合は同じ上限を持つ有向集合に変換することができることに注意。 有向完備半順序や完備束を考えるときは当然、特定の上限が存在するという追加条件を省くことができる。さらに、有向完備である結び半束は完備束になることに注意(最小元を持たないこともある)。詳細については、完備性(英語版)を参照。
※この「形式的定義」の解説は、「コンパクト要素」の解説の一部です。
「形式的定義」を含む「コンパクト要素」の記事については、「コンパクト要素」の概要を参照ください。
形式的定義
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2019/10/01 07:51 UTC 版)
ムーア・マシンは { S, Σ, Λ, T, G, q 0 {\displaystyle q_{0}} , F } の7要素から構成され、以下の性質を持つ。 状態の有限集合 ( S ) 入力文字の有限集合 ( Σ ) 出力文字の有限集合 ( Λ ) 遷移関数 (T : S × Σ → S) は状態と入力から次の状態を導く。 出力関数 (G : S → Λ) は状態から出力文字を導く。 開始状態 ( q 0 ) {\displaystyle (q_{0})} 完了状態の集合 F ムーア・マシンの状態数は、同等機能のミーリ・マシンの状態数より多い(あるいは同数)。
※この「形式的定義」の解説は、「ムーア・マシン」の解説の一部です。
「形式的定義」を含む「ムーア・マシン」の記事については、「ムーア・マシン」の概要を参照ください。
形式的定義
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2019/10/01 03:04 UTC 版)
L {\displaystyle L} を正規言語とすると、 L {\displaystyle L} のみに依存する次のような反復長 p ≥ 1 {\displaystyle p\geq 1} が存在する。 L {\displaystyle L} に属する長さ p {\displaystyle p} 以上の任意の文字列 w {\displaystyle w} は w = x y z {\displaystyle w=xyz} と書ける(つまり、 w {\displaystyle w} は3つの部分文字列に分けられる)。ここで、 x {\displaystyle x} 、 y {\displaystyle y} 、 z {\displaystyle z} は次の条件を満たす。 | y | ≥ 1 {\displaystyle |y|\geq 1} | x y | ≤ p {\displaystyle |xy|\leq p} 全ての i ≥ 0 {\displaystyle i\geq 0} について、 x y i z ∈ L {\displaystyle xy^{i}z\in L} y は反復される部分文字列(0回を含む任意の回数繰り返され、結果として生成される文字列も L に属する)。|y| は文字列 y の長さを意味し、(1)の条件は y が少なくとも長さを持つ空でない文字列であることを意味している。(2)の条件は繰り返しが先頭から p 文字以内から開始されることを意味する。x および z については特に制限はない。 反復補題の形式的表現を以下に示す。 ( ∀ L ⊆ Σ ∗ ) ( regular ( L ) ⇒ ( ( ∃ p ≥ 1 ) ( ( ∀ w ∈ L ) ( ( | w | ≥ p ) ⇒ ( ( ∃ x , y , z ∈ Σ ∗ ) ( w = x y z ∧ ( | y | ≥ 1 ∧ | x y | ≤ p ∧ ( ∀ i ≥ 0 ) ( x y i z ∈ L ) ) ) ) ) ) ) ) {\displaystyle {\begin{array}{l}(\forall L\subseteq \Sigma ^{*})\\\quad ({\mbox{regular}}(L)\Rightarrow \\\quad ((\exists p\geq 1)((\forall w\in L)((|w|\geq p)\Rightarrow \\\quad ((\exists x,y,z\in \Sigma ^{*})(w=xyz\land (|y|\geq 1\land |xy|\leq p\land (\forall i\geq 0)(xy^{i}z\in L))))))))\end{array}}}
※この「形式的定義」の解説は、「正規言語の反復補題」の解説の一部です。
「形式的定義」を含む「正規言語の反復補題」の記事については、「正規言語の反復補題」の概要を参照ください。
形式的定義
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2020/01/12 14:48 UTC 版)
ある長さの時間を任意に定め、X をその時間に送信される信号、Y を同じ時間に通信路を介して受信される信号をそれぞれあらわす確率変数とする。通信路のノイズの性質などをすべてまとめて、X が与えられたときの Y の条件付き確率分布関数 p Y | X ( y | x ) {\displaystyle p_{Y|X}(y|x)} によって通信路の入出力特性が完全に記述されるものとする。すると、X と Y の同時分布 p X , Y ( x , y ) {\displaystyle p_{X,Y}(x,y)} は、通信路 p Y | X ( y | x ) {\displaystyle p_{Y|X}(y|x)} と、その通信路を介して送信される信号の周辺分布 p X ( x ) {\displaystyle p_{X}(x)} とによって決定される: p X , Y ( x , y ) = p Y | X ( y | x ) p X ( x ) {\displaystyle p_{X,Y}(x,y)=p_{Y|X}(y|x)\,p_{X}(x)} 以上の条件の下で、通信路を介して伝送することのできる情報の量をなるべく大きくすることを考える。伝送情報量に対する尺度として相互情報量 I ( X ; Y ) {\displaystyle I(X;Y)} を用いることができる。相互情報量の上限が通信路容量であり、以下のように定義される。 C = sup p X I ( X ; Y ) {\displaystyle C=\sup _{p_{X}}I(X;Y)\,}
※この「形式的定義」の解説は、「通信路容量」の解説の一部です。
「形式的定義」を含む「通信路容量」の記事については、「通信路容量」の概要を参照ください。
形式的定義
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2021/09/14 15:20 UTC 版)
プレーヤーのタイプの決定: プレーヤーは i で、i は S (送り手) または R (受け手) とする。 偶然手番が送り手のタイプ tj ∈ T = {t1, ..., tJ} を決定する (J はありうる送り手のタイプの数)。 行動の選択: S はシグナル mk ∈ M = {m1, ..., mK} を選ぶ (K は S が送りうる異なるシグナルの数)。 R は応答行動 al ∈ A = {a1, ..., aL} を選ぶ (L は R が選びうる異なる応答行動の数)。 利得関数はそれぞれ US (tj, mk, al), UR (tj, mk, al) である。 ゲームの進行: 第 1 段階で、自然 (nature, Natur) は、送り手のタイプ t ^ j ∈ T {\displaystyle {\hat {t}}_{j}\in T} を、確率分布 p, ただし p (tj) > 0, p (t1) + … + p (tJ) = 1, に応じて選ぶ。 第 2 段階で、送り手 S は (自分のタイプ t ^ j {\displaystyle {\hat {t}}_{j}} を知ったうえで) シグナル m ^ k {\displaystyle {\hat {m}}_{k}} を選ぶ。 第 3 段階で、受け手 R は送られたシグナル m ^ k {\displaystyle {\hat {m}}_{k}} を観察して応答行動 a ^ l {\displaystyle {\hat {a}}_{l}} を選ぶ。 利得はそれぞれ U S ( t ^ j , m ^ k , a ^ l ) , U R ( t ^ j , m ^ k , a ^ l ) {\displaystyle U_{\rm {S}}({\hat {t}}_{j},{\hat {m}}_{k},{\hat {a}}_{l}),U_{\rm {R}}({\hat {t}}_{j},{\hat {m}}_{k},{\hat {a}}_{l})} になる。
※この「形式的定義」の解説は、「シグナリングゲーム」の解説の一部です。
「形式的定義」を含む「シグナリングゲーム」の記事については、「シグナリングゲーム」の概要を参照ください。
形式的定義
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2021/09/14 14:36 UTC 版)
多様体 M が漸近的に単純であるとは、 M のどんなヌル測地線の未来端点も過去端点も M ~ {\displaystyle {\tilde {M}}} の境界上にあるような共形コンパクト化 M ~ {\displaystyle {\tilde {M}}} が可能であることを意味する。 過去端点についての条件はブラックホールにおいて成り立たないので、弱い漸近的単純性条件を適当な漸近的に単純な多様体の共形コンパクト化 M ~ {\displaystyle {\tilde {M}}} について、その境界近傍と等長な開集合 U⊂M が存在するという条件として定義する。 弱い漸近的単純性条件を満たす多様体が、 M ~ {\displaystyle {\tilde {M}}} の近傍でリッチテンソルがゼロとなるという意味で漸近的に空白であるとき、その多様体は漸近的に平坦であるという。
※この「形式的定義」の解説は、「漸近的に平坦な時空」の解説の一部です。
「形式的定義」を含む「漸近的に平坦な時空」の記事については、「漸近的に平坦な時空」の概要を参照ください。
形式的定義
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2021/11/20 05:50 UTC 版)
滑らかな多様体(smooth manifold) M {\displaystyle M} 上の複素ベクトル束 E {\displaystyle E} におけるエルミート計量(Hermitian metric)とは、各々のファイバー上で滑らかに変化する正定値エルミート形式である。そのような計量は滑らかな切断 h ∈ Γ ( E ⊗ E ¯ ) ∗ {\displaystyle h\in \Gamma (E\otimes {\bar {E}})^{*}} であって、 E p {\displaystyle E_{p}} の任意の元 ζ , η {\displaystyle \zeta ,\eta } に対し h p ( η , ζ ¯ ) = h p ( ζ , η ¯ ) ¯ {\displaystyle h_{p}(\eta ,{\bar {\zeta }})={\overline {h_{p}(\zeta ,{\bar {\eta }})}}} であり、 E p {\displaystyle E_{p}} の任意の 0 でない元 ζ {\displaystyle \zeta } に対し h p ( ζ , ζ ¯ ) > 0 {\displaystyle h_{p}(\zeta ,{\bar {\zeta }})>0} を満たすような切断として表すことができる。 エルミート多様体(Hermitian manifold)は、その正則接空間(英語版)(holomorphic tangent space)上にエルミート計量を持つ複素多様体である。同様に、概エルミート多様体(almost Hermitian manifold)は、その正則接空間上にエルミート計量を持つ概複素多様体である。 エルミート多様体上では、計量は正則局所座標 ( z α ) {\displaystyle (z^{\alpha })} を用いて h = h α β ¯ d z α ⊗ d z ¯ β {\displaystyle h=h_{\alpha {\bar {\beta }}}\,dz^{\alpha }\otimes d{\bar {z}}^{\beta }} と表わされる。ここに h α β ¯ {\displaystyle h_{\alpha {\bar {\beta }}}} は正定値エルミート行列の成分である。
※この「形式的定義」の解説は、「エルミート多様体」の解説の一部です。
「形式的定義」を含む「エルミート多様体」の記事については、「エルミート多様体」の概要を参照ください。
形式的定義
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2021/11/29 01:54 UTC 版)
形式的には、1次元のDCT F: RN → RN は、ある可逆な線形写像(ただし、R は実数の集合)、または同じことであるが、ある正則な N × N 正方行列であって、以下に示された式で表される。ただし、これらの式では、N 個の実数列 x0, ..., xN−1 が N 個の実数列 X0, ..., XN−1 に変換される。
※この「形式的定義」の解説は、「離散コサイン変換」の解説の一部です。
「形式的定義」を含む「離散コサイン変換」の記事については、「離散コサイン変換」の概要を参照ください。
形式的定義
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2021/06/23 10:02 UTC 版)
自然数の集合 S について、定義域が S と正確に一致するような何らかの部分再帰関数(部分計算可能関数)f が存在するとき、S は帰納的可算であると言う。つまり f が定義される必要十分条件は、f への入力が S の元であることである。 この定義は任意の可算集合 A に拡張できる。そのためには、A の元をゲーデル数で表し、もし対応するゲーデル数の集合が帰納的可算ならば A の何らかの部分集合が帰納的可算になることを言えば良い。
※この「形式的定義」の解説は、「帰納的可算集合」の解説の一部です。
「形式的定義」を含む「帰納的可算集合」の記事については、「帰納的可算集合」の概要を参照ください。
形式的定義
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2021/12/08 03:46 UTC 版)
f {\displaystyle f} : X × {\displaystyle \times } Y → {\displaystyle \rightarrow } Z としたとき、一般に X = Y = { 0 , 1 } n {\displaystyle X=Y=\{0,1\}^{n}} および Z = { 0 , 1 } {\displaystyle Z=\{0,1\}} と仮定する。アリスは n ビットの文字列 x {\displaystyle x} ∈ {\displaystyle \in } X を持ち、ボブは n ビットの文字列 y {\displaystyle y} ∈ {\displaystyle \in } Y を持つ。1回につき1ビットずつ両者間で通信を行い(何らかの通信プロトコルが適用される)、アリスとボブは最終的にいずれかが f ( x , y ) {\displaystyle f(x,y)} の値を計算できるようにしたい。取り決めとして、一方で答えが判明したらもう一方にあと 1ビットの通信をするだけで全通信が完了するものとする。この通信プロトコルの最悪の通信複雑性( D ( f ) {\displaystyle D(f)} で表される)は次のように定義される。 D ( f ) = {\displaystyle D(f)=} アリスとボブの間で交換されるビット数の最悪ケースの最小値 ここで関数 f {\displaystyle f} を行列 A {\displaystyle A} (入力行列と呼ぶ)として考えるのが便利である。この行列の行は x {\displaystyle x} ∈ {\displaystyle \in } X に対応して並んでおり、列は y {\displaystyle y} ∈ {\displaystyle \in } Y に対応して並んでいる。入力行列の各要素は A x , y = f ( x , y ) {\displaystyle A_{\mathrm {x,y} }=f(x,y)} である。初期状態でアリスもボブも行列 A 全体を知っている(つまり、両者は関数 f {\displaystyle f} を知っている)。そうすると、関数の値の計算問題は対応する行列の要素を選び取る問題に変換される。この問題はアリスかボブのどちらかが x {\displaystyle x} と y {\displaystyle y} の両方を知った時点で答えがわかる。通信を開始するとき、答えとしてありうるのは行列の全要素なので n 2 {\displaystyle n^{2}} 個存在する。その後、互いに 1ビットずつ通信すると、解ではあり得ない行や列が除外されていく。 より形式的に表現すると、集合 R ⊆ {\displaystyle \subseteq } X × {\displaystyle \times } Y があり、 ( x 1 , y 1 ) {\displaystyle (x_{1},y_{1})} ∈ {\displaystyle \in } R かつ ( x 2 , y 2 ) {\displaystyle (x_{2},y_{2})} ∈ {\displaystyle \in } R のとき常に ( x 1 , y 2 ) {\displaystyle (x_{1},y_{2})} ∈ {\displaystyle \in } R ならば、R を長方形であるという。また、R を R = M × {\displaystyle \times } N (ただし、M ⊆ {\displaystyle \subseteq } X かつ N ⊆ {\displaystyle \subseteq } Y)であるような A の部分行列と見ることもできる。既に k {\displaystyle k} ビットの情報をやり取りした状態を考えて見よう。ある h {\displaystyle h} ∈ {\displaystyle \in } { 0 , 1 } k {\displaystyle \{0,1\}^{k}} について、次のように行列が定義される。 T h = { ( x , y ) : {\displaystyle T_{\mathrm {h} }=\{(x,y):} 入力 ( x , y ) {\displaystyle (x,y)} でやり取りされた k ビットが h {\displaystyle h} である } {\displaystyle \}} ここで、 T h {\displaystyle T_{\mathrm {h} }} ⊆ {\displaystyle \subseteq } X × {\displaystyle \times } Y であり、 T h {\displaystyle T_{\mathrm {h} }} は長方形であると同時に A の部分行列である。
※この「形式的定義」の解説は、「通信複雑性」の解説の一部です。
「形式的定義」を含む「通信複雑性」の記事については、「通信複雑性」の概要を参照ください。
形式的定義
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2022/04/15 08:15 UTC 版)
数学的には、エネルギー地形は各物理状態をエネルギーに対応づける連続写像 f : X → R {\displaystyle f:X\to \mathbb {R} } である。ここで、 X {\displaystyle X} は位相空間である。 連続の場合、 X = R n {\displaystyle X=\mathbb {R} ^{n}} となる。ここで、 n {\displaystyle n} は系の自由度である。連続エネルギー地形のグラフは、 R n + 1 {\displaystyle \mathbb {R} ^{n+1}} 上の超曲面となる。 エネルギー地形上の丘や谷は、それぞれ f {\displaystyle f} の極大値および極小値に対応する。
※この「形式的定義」の解説は、「エネルギー地形」の解説の一部です。
「形式的定義」を含む「エネルギー地形」の記事については、「エネルギー地形」の概要を参照ください。
形式的定義
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2021/09/20 03:03 UTC 版)
n {\displaystyle n} の各位の和(数字和)を求める関数を f ( n ) {\displaystyle f(n)} とする。 f ( n ) , f ( f ( n ) ) , f ( f ( f ( n ) ) ) , ⋯ {\displaystyle f(n),f(f(n)),f(f(f(n))),\dotsb } と計算していくと、最終的に定数値に収束する。この定数値( n {\displaystyle n} の数字根)を求める関数を f ∗ ( n ) {\displaystyle f^{*}(n)} とする。
※この「形式的定義」の解説は、「数字根」の解説の一部です。
「形式的定義」を含む「数字根」の記事については、「数字根」の概要を参照ください。
形式的定義
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2021/06/23 10:02 UTC 版)
L を concrete set(具体集合)という順序集合とし、L′ を別の順序集合 abstract set(抽象集合)とする。これら2つの集合は相互に元をマップする全域関数によって関連付けられる。 関数αは abstraction function(抽象化関数)と呼ばれ、x が L の元であるとき、α(x) が L′ の元となる。すなわち、L′ の元 α(x) は L の元 x の抽象化(abstraction)である。 関数γは concretization function(具体化関数)と呼ばれ、x′ が L′ の元であるとき、γ(x′) が L の元となる。すなわち、L の元 γ(x′) は L′ の元 x′ の具体化(concretization)である。 L1、L2、L′1、L′2 を順序集合とする。具体的意味論 f は、L1 から L2 への単調関数である。L′1 から L′2 への関数 f′ を f の「妥当な抽象化; valid abstraction」と呼び、L′1 に属する全ての x′ について (f ∘ γ)(x′) ≤ (γ ∘ f′)(x′) が成り立つ。 プログラム意味論は一般に、ループや再帰関数における不動点を使って表される。L が完備束で、f が L から L への単調関数とする。すると、f′(x′) ≤ x′ であるような x′ は f の最小不動点の抽象化である。 ここで問題となるのは、そのような x′ を求める方法である。L′ の高さが有限であるか、少なくとも昇鎖条件(全ての昇順は最終的に定常である)があるなら、そのような x′ は帰納によって次のように定義された昇順 x′n の定常の限界値として得られる。 x′0=⊥ (L′ の極小な元) x′n+1=f′(x′n) それ以外のケースでも、widening operator ∇ を通して、そのような x′ を得ることが可能である。これは、全ての x と y について x ∇ y が x と y のどちらよりも大きいか等しいという演算である。ここで全ての順序 y′n について、次のように定義される順序は最終的に定常的である。 x′0=⊥ x′n+1=x′n ∇ y′n 従って、y′n=f(x′n) となる。 場合によっては、ガロア接続(Galois connection)(α, γ) を使って抽象化を定義できる。ここで、αは L から L′ への関数、γは L′ から L への関数である。これは、必ずしも存在するとは限らない最良の抽象化の存在を前提としている。例えば、実数の組 (x,y) の集合を凸多面体で囲むことで抽象化する場合、x2+y2 ≤ 1 で定義される円板の最良の抽象化は存在しない。
※この「形式的定義」の解説は、「抽象解釈」の解説の一部です。
「形式的定義」を含む「抽象解釈」の記事については、「抽象解釈」の概要を参照ください。
形式的定義
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2022/03/05 10:13 UTC 版)
ここでは、一つの状態遷移系の上で双模倣性を定義する。二つの状態遷移系の双模倣性は、それらの和として得られる状態遷移系の双模倣性から導かれる。 ラベル付き状態遷移系 (S, Λ, →) について、「双模倣性」関係は S 上の二項関係 R (すなわち、R ⊆ S × S)であり、R と R-1 が共に Simulation Preorder となるものである。 つまり、R が双模倣性関係であるとは、S の要素のペア (p, q) が R に含まれるときに、Λ の要素 α と S の要素 p' について次の性質が満たされ、かつ R-1 に対しても同様の性質が満たされることをいう。 p → α p ′ {\displaystyle p\mathrel {\overset {\alpha }{\rightarrow }} p'} ならば、 q → α q ′ {\displaystyle q\mathrel {\overset {\alpha }{\rightarrow }} q'} の関係が成り立つ S の要素 q' が存在し、(p', q') も R に含まれる。 S 内の2つの状態 p と q に対して (p, q) が R に含まれる双模倣性関係 R が存在するとき、p と q は「双模倣的」であるといい、 p ∼ q と表記する。 双模倣的関係 ∼ は同値関係である。さらに、それは与えられた遷移系上の双模倣性関係のうち最大のものを与える。 p が q の模倣であり、q が p の模倣であっても、双模倣性があるとは限らないことに注意が必要である。p と q が双模倣的であるためには、p から q への模倣と q から p への模倣が二項関係における「逆(en:Inverse relation)」でなければならない。
※この「形式的定義」の解説は、「双模倣性」の解説の一部です。
「形式的定義」を含む「双模倣性」の記事については、「双模倣性」の概要を参照ください。
形式的定義
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2021/08/04 05:25 UTC 版)
「決定性有限オートマトン」の記事における「形式的定義」の解説
DFA とは5組 A = (Q, Σ, δ, q0, F) のうち以下の性質(右側)を満たすものをいう。それぞれの要素は以下(左側)のように呼ばれる。 状態集合 (Q : 有限集合) 文字集合 (Σ : 有限集合) 遷移関数 (δ : Q × Σ → Q) 開始状態 (q0 ∈ Q) 受理状態の集合 (F ⊆ Q) いま a = a0a1 ... an−1 という文字集合 Σ に含まれる文字から構成される文字列が与えられたとする。各 i = 0, …, n−1 について帰納的に qi+1 := δ(qi, ai) とおく。 qn ∈ F が成り立つとき、 A は文字列 a を受理すると言う。状態の列 qi は文字列 a が与えられたとき、遷移関数 δ にしたがってこのマシンが状態遷移を繰り返すことを示している。言語の中でこのマシンが受容する文字列の集合が、このDFAの理解する言語である。
※この「形式的定義」の解説は、「決定性有限オートマトン」の解説の一部です。
「形式的定義」を含む「決定性有限オートマトン」の記事については、「決定性有限オートマトン」の概要を参照ください。
形式的定義
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2021/02/07 02:11 UTC 版)
アフィン空間 (A, V(A)), (B, V(B)) に対し、写像 f: A → B と f が引き起こす線型写像 V(f): V(A) → V(B) の組 (f, V(f)) をアフィン写像という。ここで f が V(f) を引き起こすとは、f と V(f) との間に条件 任意の a ∈ V(A) に対し、 a = P Q → ( P , Q ∈ A ) ⇒ V ( f ) ( a ) = f ( P ) f ( Q ) → {\displaystyle a={\overrightarrow {\mathrm {PQ} }}\quad (\mathrm {P} ,\mathrm {Q} \in A)\Rightarrow V(f)(a)={\overrightarrow {f(\mathrm {P} )f(\mathrm {Q} )}}} が成り立つ。 任意の P ∈ A, a ∈ V に対し、f(P + a) = f(P) + V(f)(a) が成り立つ。ただし、"+ a", "+ V(f)(a)" はそれぞれ、A, B における平行移動を表す。 が満たされることをいう。このアフィン写像を f × V(f): (A, V(A)) → (B, V(B)) あるいは単に f: A → B で表す。 原点を固定して A = O + V(A), B = O′ + V(B) とみるとき、アフィン写像 f: A → B は具体的に A の点 P に対して f ( P ) = f ( O + O P → ) = f ( O ) + V ( f ) ( O P → ) = O ′ + ( V ( f ) ( O P → ) + O ′ f ( O ) → ) {\displaystyle f(\mathrm {P} )=f(\mathrm {O} +{\overrightarrow {\mathrm {OP} }})=f(\mathrm {O} )+V(f)({\overrightarrow {\mathrm {OP} }})=\mathrm {O} '+(V(f)({\overrightarrow {\mathrm {OP} }})+{\overrightarrow {\mathrm {O} 'f(\mathrm {O} )}})} と書くことができて、特に位置ベクトルの間の関係 y = V ( f ) ( x ) + b ( x := O P → , y := O ′ f ( P ) → , b := O ′ f ( O ) → ) {\displaystyle y=V(f)(x)+b\quad (x:={\overrightarrow {\mathrm {OP} }},\,y:={\overrightarrow {\mathrm {O} 'f(\mathrm {P} )}},\,b:={\overrightarrow {\mathrm {O} 'f(\mathrm {O} )}})} が得られる。つまり、アフィン写像は位置ベクトルの空間としての V(A) と V(B) の間で、線型写像 T = V(f) と定ベクトル b による平行移動の合成 y = Tx + b として作用することがわかる(位置ベクトルについてみれば V(f) と b の分だけずれている)。
※この「形式的定義」の解説は、「アフィン写像」の解説の一部です。
「形式的定義」を含む「アフィン写像」の記事については、「アフィン写像」の概要を参照ください。
形式的定義
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2021/12/22 07:06 UTC 版)
「共変性と反変性 (計算機科学)」の記事における「形式的定義」の解説
プログラミング言語の型システムにおいて、型構築子 (type constructor) 等が、 型の順序関係を維持する (≤ で順序づけたとき、特殊から一般の順になる)[訳語疑問点] とき、共変である (covariant) という。 型の順序関係を反転させるとき、反変である (contravariant) という。 上記いずれにも該当しないとき、非変である (nonvariant) という。 共変かつ反変のとき、双変である (bivariant) という。 この区分は、クラス階層におけるメソッドの引数および戻り値の型を検討するときに重要である。C++のようなオブジェクト指向言語においては、クラス B がクラス A のサブタイプであるとき、B のメンバー関数はいずれも、戻り値の型集合が A のものと同じかより小さくなければならない。すなわち戻り値の型は共変である。一方、B のメンバー関数のとりうる引数の型集合が、A のものと同じかより大きいとき、引数の型は反変である。B のインスタンスにとって問題なのは、どうすれば A のインスタンスを完全に置換可能かということである。型安全性と置換可能性を保証する唯一の方法は、入力に対しては A と同等かより寛容に、出力に対しては A と同等かより厳格に振る舞うことである。ただし、すべてのプログラミング言語があらゆる文脈でこの2つの性質を保証しているわけではなく、不必要に厳格なものもある。つまり、特定の文脈においては共変性や反変性をサポートしないことがある。
※この「形式的定義」の解説は、「共変性と反変性 (計算機科学)」の解説の一部です。
「形式的定義」を含む「共変性と反変性 (計算機科学)」の記事については、「共変性と反変性 (計算機科学)」の概要を参照ください。
形式的定義
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2010/08/09 21:14 UTC 版)
ミーリ・マシンは (S, Σ, Λ, T, G, s) の6要素から成り、以下の性質を持つ。 状態の有限集合 (S) 入力文字列の有限集合 (Σ) 出力文字列の有限集合 (Λ) 遷移関数 (T : S × Σ → S). 出力関数 (G : S × Σ → Λ). 開始状態 (s ∈ S)
※この「形式的定義」の解説は、「ミーリ・マシン」の解説の一部です。
「形式的定義」を含む「ミーリ・マシン」の記事については、「ミーリ・マシン」の概要を参照ください。
- 形式的定義のページへのリンク