Team TripleFalcon. http://www.triplefalcon.com/

概要

 代数は集合とその上に定義した演算について追求する学問です。従って単なる集合ではなく、集合がある程度の構造を持っています。代数系(algebraic system)は集合と演算子の2つの部分からなります。例えば整数全体に足し算を定義すれば、それは代数系です。集合をSとして、Sの上の演算 * とSの組を代数とします。 S と * を括弧でくくり、(S,*)などと表します。(参照→集合,半群,モノイド,,,,代数系)。また、特別な代数系にブール代数があります。

 集合が有限のとき有限代数系(finite)、そうでないときは無限代数系(infinite)と呼ばれます。代数系では集合Sを代数の台と呼びます。  演算が1つの引数をとるとき、(f:S→S のとき)単項(unary)演算といいます。演算が2つの引数をとるとき、(f:S×S→S のときのf)2項(binary)演算といいます。演算が3つの引数をとるとき、(f:S×S×S→S のときのf)3項(ternary)演算といいます。

 表記する場合は、2項演算子は中置形で表記します。例えば 3×3 等の表記です。3項以上の演算子は前置形で表記します。例えば f(3,4,5,6) 等の表記です。

 代数系は、演算子の持つ性質によって半群(semigroup)、モノイド(monoid)、群(group)、環(ring)、体(field)、などに分類されます。本用語集で扱うのはせいぜいガロア体と整数環で、しかも表面的です。それ以外の詳細は専門書や大学のHP等をあたってください。 (S:台 *:乗法 +:加法 0:加法単位元 1:乗法単位元)

名称 概要
半群 (S,*) * が結合的
モノイド (S,*,1) (S,*) が半群で単位元 1 を持つ
(S,*,1) (S,*,1) がモノイドで逆元が存在する
可換群 (S,*,1) (S,*,1) が群で * が可換
(S,+,*,0) (S,+,0) が可換群 (S,*) が半群
可換環 (S,+,*,0) (S,+,*,0) が環で * が可換
(S,+,*,0,1) (S,+,0) が可換群 (S-{0},*,1)が群
ブール代数 (S,+,*,〜,0,1) + * が対称的かつ互いに分配的、補元が存在

 代数系は抽象的で数学の奥深い分野ですが、本用語集では表層の応用面だけ捉えます。計算機とつながりが深いのは、例えば暗号や誤り訂正符号におけるガロア体(Galois field)整数環ではないでしょうか。

 集合Sと演算子・からなる代数系に対して、集合と演算子の型を列挙して、例えば <S,S×S→S> と表記したときこれを代数系の指標といいます。同じ指標を持つ代数系同士を指標が等しいといいます。(N,×,+)(N,∩,∪) は指標が等しいといえます。

Team TripleFalcon. http://www.triplefalcon.com/

閉じた演算

 代数系 (S,*) の閉じた演算とは、演算結果も S に含まれる演算のことです。

定義1) (S,*) が閉じている
def
∀u,v ∈S , u*v∈S

 例えば、偶数の集合は演算 +,− のもとで閉じている(closed) といいます。しかし、奇数の集合に関して演算 +,− は計算結果が奇数でないため、閉じているとはいえません。整数の集合の演算÷も閉じていません。 代数系では閉じた演算が基本です。

Team TripleFalcon. http://www.triplefalcon.com/

単位元

 集合Sの元 e(∈S)が、演算子・の上でSのすべての元について、以下の定義2 の性質を持つ場合は e を左単位元 (left identity) といい、定義3 の性質を持つ場合は e を右単位元といいます。左単位元で右単位元である場合は単位元といいます。 単位元は多くの場合 1 と表記します。

定義2) e∈(S,*) が左単位元
def
∀x∈S , e*x=x
定義3) e∈(S,*) が右単位元
def
∀x∈S , x*e=x

 定理として「u が左単位元 v が右単位元ならば u=v 」が成立します。この場合単位元はただ一つということになります。単位元の例としては、実数足し算における 0 や実数掛け算における 1 等があります。

Team TripleFalcon. http://www.triplefalcon.com/

零元

 代数系(S,*) の元 z が、Sのすべての元について、以下の性質を持つ場合は z を左零元 (left zero) といい、(2) の性質を持つ場合は z を右零元といいます。左零元で右零元である場合は零元といいます。零元は多くの場合 0 と表記します。

定義4) z∈(S,*) が左零元
def
∀x∈S , z*x=z
定義5) z∈(S,*) が右零元
def
∀x∈S , x*z=z

 定理として「u が左零元 v が右零元ならば u=v 」が成立します。この場合は零元はただ一つです。しかし、一つの代数が左零元を(または右零元を)複数持つことは可能です。

Team TripleFalcon. http://www.triplefalcon.com/

逆元

 代数系(S,*) の元 u,v(∈S)が、以下の性質を持つ場合は u を v の左逆元(left inverse)といい、v を u の右逆元といいます。(以下 1 は単位元とします。)左逆元で右逆元の場合は逆元といいます。

定義6) u,v∈(S,*) u が v の左逆元
def
u*v=1
定義7) u,v∈(S,*) v が u の右逆元
def
u*v=1

 例えば、整数の加算を考えた場合、5 の逆元は -5 です。

Team TripleFalcon. http://www.triplefalcon.com/

結合的

 代数系(S,*) の演算子が、以下の性質を持つ場合は結合的 (associative) であるといいます。

定義8) * が結合的
def
∀u,v,w∈S , ((u*v)*w)=(u*(v*w))

 文字に連接という演算を与えてると、連接は結合的です。自然数の足し算や掛け算も結合的です。引き算は結合的ではありません。

Team TripleFalcon. http://www.triplefalcon.com/

可換

 代数系 (S,*) の演算子が、以下の性質を持つ場合は可換(commutative)であるといいます。

定義9) * が可換
def
∀u,v∈S , u*v=v*u

 例えば、自然数の足し算は可換です。引き算は可換ではありません。行列の掛け算も可換ではありません。

Team TripleFalcon. http://www.triplefalcon.com/

準同型

 ここでは簡単のため2項演算子を一個だけ持つ代数について考えます。それ以外の代数系にも自明に拡張できます。

 指標の等しい二つの代数系 (S,*)(S',・) があり、それぞれの台 S から S' への写像 h (h:S→S') が以下の性質を持つとき、h を準同型写像(homomorphism)といいます。このとき代数系 (S',・) は (S,*) の準同型像(homomorphismic image) といいます。

定義10)

関数 h:S→S'  
が準同型写像  
def

 ∀a,b∈S ,
 h(a)・h(b)=h(a*b)

 これは、写像してから演算しても演算してから写像しても結果がひとしいという意味です。 演算子を複数もつ代数系でも、対応する演算子すべてに対して上記が言えれば準同型です。

Team TripleFalcon. http://www.triplefalcon.com/

同型

 (S',・) が (S,*) の準同型像であり、その準同型写像 h:S→S' が全単射である場合、h を同型写像 (isomorphism)といい代数系 (S,*) , (S',・) は同型であるといいます。

 定理として、「同型写像は単位元を単位元に、零元を零元に、逆元を逆元に写す」が成立します。

Team TripleFalcon. http://www.triplefalcon.com/

部分代数系

 代数系(S,*) の台 S の部分集合 S' でも演算 * が閉じているとき、代数系(S',*) を (S,*) の部分代数系(sub algebraic system) といいます。 S'で演算が閉じていることが重要です。 Sの部分集合で作った代数系がすべて部分代数系になるとは限りません。 演算子が複数でも自明に拡張できます。

 群(group) の部分代数系がまた群でもあるとき部分群(subgroup) と呼びます。環(ring)の部分代数系がまた環でもあるとき、部分環(subring)と呼びます。体(field)の部分代数系がまた体でもあるとき部分体(subfield)といいます。

 群の部分代数系は一般に群とは限りませんが、有限群の部分代数系は自動的に群になります。

Team TripleFalcon. http://www.triplefalcon.com/

重要な表現

 代数系を、G=(S,*) 等と表すことができる場合、台集合 S の元 x∈S を x∈G と表記します。 こうすると、いちいち代数系そのものと台集合をいちいち表記し分ける必要がなくなります。 例えば、群 G と表記したら G は代数系でもあるし台集合でもあると考えてよいわけです。 これは、決まりというよりはゆるい約束事ですが、可換な演算子を加法的に + と表記しそうでない演算子を乗法的に * と表記する場合が多いです。

 従って、加法的演算子 + における単位元は 0 と表記し n の逆元は -n のように表現します。 また、乗法的演算子 * の単位元は 1 と表記し n の逆元は n-1 とか 1/n のように表記します。

Team TripleFalcon. http://www.triplefalcon.com/

Team TripleFalcon. http://www.triplefalcon.com/

Team TripleFalcon. http://www.triplefalcon.com/

Team TripleFalcon. http://www.triplefalcon.com/


Team TRIPLE FALCON

アクション&シミュレーション ゲーミングとゲーム製作を真面目に考える 新進気鋭の研究者集団

   
 
用語集TOP

代数系(algebraic system)

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
あ-お か-こ さ-そ た-と な-の
は-ほ ま-も や-よ ら-ろ わ-ん

数学、哲学、工学を横断する事典です。よろしければ活用してください。 ゲーム, アクション,シューティング,シミュレーション,リアルタイム, 計量経済学,計量心理学, コンピュータ,用語集,計算機科学用語集,コンピュータ用語集, 3DCG, グラフィックス,ゲームグラフィックス,美少女, 光反射,鏡面反射,拡散反射,屈折,散乱,異方性反射,影, シェーディング,レンダリング,透視変換, 発光,爆発,爆炎,煙, 物理, 人物,表情,表現,運動,力学,流体, 計算幾何学, グラフ,アフィン変換,アフィン写像,凸包,超平面,3D,3Dの数理, コンピュータサイエンス,コンピュータ, 計算機科学, チューリングマシン,チューリング機械,線形有界オートマトン,プッシュダウンオートマトン,有限オートマトン, オートマトン,状態遷移,遷移関数,対角線論法,文字列,記号, FA,NFA,PDA,NPDA,LBA,NLBA,TM, 計算量,P,NP,PSPACE,NP完全,NP困難,P完全,PSPACE完全,PP,APX,APX完全, 確率チューリング機械,確率オートマトン, 音声, 音階,音量,音律,和音,和声,無限上昇音,MIDI, 色彩, 表色系,顕色系,混色系,RGB,CMY,YCbCr,YUV,YIQ,CIE,L*a*b*, 符号, 圧縮,符号化,情報源符号化, 符号,ブロック符号,ストリーム符号,符号理論, 離散数学, 集合,写像,関数,全単写,単写,全写,対応関係,関係,反射,反射推移閉包, 代数系, 群,環,体,モノイド,半群,準同型写像,同型写像, 形式言語, 言語,正則言語,文脈自由言語,文脈依存言語,確率言語, 文法,正則文法,文脈自由文法,文脈依存文法,確率文脈自由言語, 文字,文字列, 3型言語,2型言語,1型言語,0型言語, 信号処理, 変換,フィルタ,信号処理,DFT,DCT,DST,FFT,Wavelet,フーリエ変換, 離散,コサイン変換,サイン変換,ウェーブレット, 基礎数学, 数学,応用数学,基礎数学,フィボナッチ数列, 解析学, 位相空間,線形空間,距離空間,ベクトル空間,vector,バナッハ空間,Banach,ヒルベルト空間,Hilbert,ユークリッド空間,Euclid, ノルム,内積,可算濃度,非可算濃度, 情報理論, 情報源,情報量,エントロピー,相互情報量,記号,記号列, 複雑系, カオス,フラクタル,フラクタル幾何学,カオス写像, インターネット, セキュリティ,HTTP,SMTP,FTP,プロトコル, その他理論,理論, 紅茶,自転車通勤,備忘録, 暗号, モンゴメリ演算,高速計算法,素因数分解,離散対数問題, 暗号,ブロック暗号,ストリーム暗号,楕円暗号, 乱数,乱数生成,共通鍵暗号,公開鍵暗号,公開鍵署名,鍵共有,鍵交換, 線形攻撃,差分攻撃,補間攻撃,スライド攻撃,量子暗号, 依頼計算,ゼロ知識対話証明,ハッシュ,

AES,Rijndael,RSA,ElGamal,Twofish,Serpent,

RC6,MARS,CAST,IDEA,GOST,

MQV,DH,EC-DH,EC-ElGamal,

終了,

フィリピンパブ
アミューズメント企画はお任せ
資産運用はお任せ
メール お問い合わせ お問い合わせ メール メール メール メール メール メール