有限数列上の変換について [無断転載禁止]©2ch.net

[過去ﾛｸﾞ] 有限数列上の変換について [無断転載禁止]©2ch.net (84ﾚｽ)
上下前次1-新
抽出解除必死ﾁｪｯｶｰ(本家) (べ) 自ID ﾚｽ栞あぼーん

このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索歴削→次ｽﾚ栞削→次ｽﾚ過去ﾛｸﾞﾒﾆｭｰ

1: 片山博文MZ ◆T6xkBnTXz7B0 2016/01/22(金)13:44 ID:1Sc2IHo8(1/43)調 AAS
このスレッドでは、有限数列から有限数列への変換器について考えよう。
【議題１】どのような変換器が存在し、数学的にどのように表記できるか？
【議題２】変換器はどのようにいくつかの変換器に分解可能か？
【議題３】変換器Cに対する逆変換器C^(-1)の存在可能性について。

2: 片山博文MZ ◆T6xkBnTXz7B0 2016/01/22(金)14:30 ID:1Sc2IHo8(2/43)調 AAS
【定義１】a_1, a_2, ..., a_nという有限数列を(a_i)_{i=1}^nと表す。
【定義２】a_*(i)＝a_iとする。

3: 片山博文MZ ◆T6xkBnTXz7B0 2016/01/22(金)14:36 ID:1Sc2IHo8(3/43)調 AAS
【定義３】空数列を()で表す。すなわち()＝(a_i)_{i=1}^0である。

4: 片山博文MZ ◆T6xkBnTXz7B0 2016/01/22(金)14:44 ID:1Sc2IHo8(4/43)調 AAS
【定義４】数列Xのサイズ、すなわち項の数を#(X)と表す。k≦hのとき、
#((a_i)_{i=k}^h)＝h-k+1
となる。

5: 片山博文MZ ◆T6xkBnTXz7B0 2016/01/22(金)14:52 ID:1Sc2IHo8(5/43)調 AAS
【定義５】数列X＝(f(i))_{i=0}^nについて、関数fを数列Xの特性関数と呼ぶことにする。

6(1): 片山博文MZ ◆T6xkBnTXz7B0 2016/01/22(金)15:55 ID:1Sc2IHo8(6/43)調 AAS
条件分岐のための記号を導入する。これは単に場合分けを表すために用いる。
【定義５】「x ||_A y」は、条件Aが満たされるときxに等しく、その他のときyに等しい。
「||_A」を「条件Aの壁」と呼ぶことにする。
条件の壁は左結合である。すなわち x ||_A y ||_B z ＝ (x ||_A y) ||_B zである。

7: 片山博文MZ ◆T6xkBnTXz7B0 2016/01/22(金)15:58 ID:1Sc2IHo8(7/43)調 AAS
>>6の発言を撤回する。
【定義６】「x ||_A y」は、条件Aが満たされるときyに等しく、その他のときxに等しい。
「||_A」を「条件Aの壁」と呼ぶことにする。
条件の壁は左結合である。すなわち x ||_A y ||_B z ＝ (x ||_A y) ||_B zである。

8: 片山博文MZ ◆T6xkBnTXz7B0 2016/01/22(金)16:21 ID:1Sc2IHo8(8/43)調 AAS
【定義７】数列Xの第k項をX[k-1]と表す。
【定義８】数列XからX[h]を取り除いた数列をERASE(X, h)と表す。
【定義９】数列XからX[h]からX[k]までを取り除いた数列をERASE(X, h, k)と表す。

9: 片山博文MZ ◆T6xkBnTXz7B0 2016/01/22(金)16:24 ID:1Sc2IHo8(9/43)調 AAS
【定義10】数列Xの中のX[i]の前に項xを挿入した数列をINSERT(X, i, x)と表す。
【定義11】数列Xの中のX[i]の前に数列Yを挿入した数列をINSERT(X, i, Y)と表す。

10: 片山博文MZ ◆T6xkBnTXz7B0 2016/01/22(金)16:27 ID:1Sc2IHo8(10/43)調 AAS
【定義12】数列Xの最後に項xを追加した数列をAPPEND(X, x)と表す。
【定義13】数列Xの最後に数列Yの項を順番に挿入した数列をAPPEND(X, Y)と表す。

11: 片山博文MZ ◆T6xkBnTXz7B0 2016/01/22(金)16:31 ID:1Sc2IHo8(11/43)調 AAS
【定義14】数列Xについて、X[h]以降の項を並べた数列をSUB(X, h)と表す。
【定義15】数列Xについて、X[h]以降のm個の項を並べた数列をSUB(X, h, m)と表す。

12: 片山博文MZ ◆T6xkBnTXz7B0 2016/01/22(金)16:36 ID:1Sc2IHo8(12/43)調 AAS
【定義17】数列Xについて項X[h]を項yで置き換えた数列をREPLACE(X, h, y)と表す。
【定義18】数列XについてX[h]以降のm個の項を数列Yで置き換えた数列を
REPLACE(X, h, m, Y)と表す。

13: 片山博文MZ ◆T6xkBnTXz7B0 2016/01/22(金)16:40 ID:1Sc2IHo8(13/43)調 AAS
【定義19】#(X)＝nである数列Xと、自然数m(≦n)について、
Xの先頭からm個の項を順番に取り出したサイズmの数列を
SHRINK(X, m)と表す。

14: 片山博文MZ ◆T6xkBnTXz7B0 2016/01/22(金)17:08 ID:1Sc2IHo8(14/43)調 AAS
(f(i))_{i=h}^kという形の数列について、
これは(f(i+h))_{i=0}^{k-h}という形に変形できる。
よって(f(i))_{i=0}^nのような、添字がゼロベースの数列を考えるだけで充分である。

15: 片山博文MZ ◆T6xkBnTXz7B0 2016/01/22(金)17:19 ID:1Sc2IHo8(15/43)調 AAS
明らかに
ERASE(X, h)＝ERASE(X, h, h)
である。
明らかに
ERASE(X, 0, #(X)-1)＝()
である。

16: 片山博文MZ ◆T6xkBnTXz7B0 2016/01/22(金)17:21 ID:1Sc2IHo8(16/43)調 AAS
明らかに
APPEND(X, y)＝INSERT(X, #(X), y)
であり、
APPEND(X, Y)＝INSERT(X, #(X), Y)
である。

17: 片山博文MZ ◆T6xkBnTXz7B0 2016/01/22(金)17:24 ID:1Sc2IHo8(17/43)調 AAS
明らかに
APPEND(X, APPEND(Y, Z))＝APPEND(APPEND(X, Y), Z)
である。

18: 片山博文MZ ◆T6xkBnTXz7B0 2016/01/22(金)17:32 ID:1Sc2IHo8(18/43)調 AAS
ERASE((f(i))_{i=0}^n, h)＝(f(i) ||_{i≧h} f(i+1))_{i=0}^{n-1}
である。ここに「||_{i≧h}」は条件i≧hの壁である。

19: 片山博文MZ ◆T6xkBnTXz7B0 2016/01/22(金)17:40 ID:1Sc2IHo8(19/43)調 AAS
明らかに
APPEND(X, Y)＝(X[i] ||_{#(X)≦i} Y[i-#(X)])_{i=0}^{#(X)+#(Y)-1}
である。

20: 片山博文MZ ◆T6xkBnTXz7B0 2016/01/22(金)17:43 ID:1Sc2IHo8(20/43)調 AAS
明らかに
INSERT(X, 0, Y)＝APPEND(Y, X)
である。

21: 片山博文MZ ◆T6xkBnTXz7B0 2016/01/22(金)17:52 ID:1Sc2IHo8(21/43)調 AAS
明らかに
INSERT(INSERT(X, h, Y), h, Z)＝INSERT(X, h, APPEND(Z, Y))
である。

22: 片山博文MZ ◆T6xkBnTXz7B0 2016/01/22(金)18:52 ID:1Sc2IHo8(22/43)調 AAS
【定義20】数列X中のX[h]からm個の項を取り除いた数列をERASE2(X, h, m)と表す。
明らかにERASE(X, h, k)＝ERASE2(X, h, k-h+1)である。

23: 片山博文MZ ◆T6xkBnTXz7B0 2016/01/22(金)18:57 ID:1Sc2IHo8(23/43)調 AAS
【定義21】数列Xの先頭からm個の項を並べた数列をFRONT(X, m)と表す。
【定義22】数列Xの先頭の項をFRONT(X)と表す。
【定義23】数列Xの最後のm個の項を並べた数列をBACK(X, m)と表す。
【定義24】数列Xの最後の項をBACK(X)と表す。

24: 片山博文MZ ◆T6xkBnTXz7B0 2016/01/22(金)19:06 ID:1Sc2IHo8(24/43)調 AAS
ここまでの関数の定義について、定義域と値域を確認しよう。
【定義25】すべての数列の全体集合をSeqと表す。また、サイズnの数列の全体集合をSeq(n)と表す。
【定義26】x以上y未満の整数の集合をI(x,y)と表す。

25: 片山博文MZ ◆T6xkBnTXz7B0 2016/01/22(金)19:25 ID:1Sc2IHo8(25/43)調 AAS
Ｎ＝{0,1,2,3,...}とする。
#(X)のXはSeqに属する。
X[h]のhはI(0,#(X))に属する。
ERASE(X,h)のhはI(0,#(X))に属し、Xはサイズ1以上の数列である。
ERASE2(X,h,m)のhはI(0,#(X)+1)に属し、mはI(0,#(X)-h+1)に属し、Xはサイズm以上の数列である。
INSERT(X,h,Y)のhはI(0,#(X)+1)に属し、X,YはSeqに属する。

26: 片山博文MZ ◆T6xkBnTXz7B0 2016/01/22(金)20:06 ID:1Sc2IHo8(26/43)調 AAS
APPEND(X,Y)のX,Yは数列であり、これ以外の制限はない。
これは２通りの見方がある。Xの最後にYを追加するか、Yの先頭にXを挿入するか。
Z＝APPEND(*,Y)の値域はSUB(Z,#(Z)-#(Y),#(Y))＝YとするZの集合である。
Z＝APPEND(X,*)の値域はSUB(Z,0,#(X))＝XとするZの集合である。

27: 片山博文MZ ◆T6xkBnTXz7B0 2016/01/22(金)20:11 ID:1Sc2IHo8(27/43)調 AAS
逆変換器を考えるときで、機械が正常に動作しているか確認する必要があるとき、
元の変換器の値域を考慮する必要がある。

28: 片山博文MZ ◆T6xkBnTXz7B0 2016/01/22(金)20:23 ID:1Sc2IHo8(28/43)調 AAS
変換器Z＝APPEND(X,Y)のXに関する逆変換器は、X＝FRONT(Z,#(Z)-#(Y))となる。
ここにBACK(Z,#(Y))＝Yでなければならない。

29: 片山博文MZ ◆T6xkBnTXz7B0 2016/01/22(金)20:25 ID:1Sc2IHo8(29/43)調 AAS
変換器Z＝APPEND(X,Y)のYに関する逆変換器は、Y＝BACK(Z,#(Z)-#(X))となる。
ここにFRONT(Z,#(X))＝Xでなければならない。

31: 片山博文MZ ◆T6xkBnTXz7B0 2016/01/22(金)20:50 ID:1Sc2IHo8(30/43)調 AAS
変換器Z＝ERASE(X,h)のXに関する逆変換器はX＝INSERT(Z,h,X[h])である。
ここに0≦h＜#(X)かつ#(X)-1＝#(Z)≧0でなければならない。

32(1): 片山博文MZ ◆T6xkBnTXz7B0 2016/01/22(金)20:57 ID:1Sc2IHo8(31/43)調 AAS
変換器Z＝INSERT(X,h,m,Y)のXに関する逆変換器はX＝ERASE2(Z,h,m)である。
ここに0≦h≦h+m≦#(Z)＝#(X)+#(Y)でなければならない。また、SUB(Z,h,m)＝Yである。

33: 片山博文MZ ◆T6xkBnTXz7B0 2016/01/22(金)21:05 ID:1Sc2IHo8(32/43)調 AAS
一般に関数f:X→Y、g:Y→Zについて、それぞれの逆関数f^{-1},g^{-1}が
存在すれば、y＝g(f(x))の逆関数はx＝f^{-1}(g^{-1}(y))である。
このことを確認したい。

34: 片山博文MZ ◆T6xkBnTXz7B0 2016/01/22(金)21:27 ID:1Sc2IHo8(33/43)調 AAS
>>30
コンピュータ様は、明確に記述しないと数学的概念を理解してくれないらしい。

35: 片山博文MZ ◆T6xkBnTXz7B0 2016/01/22(金)21:34 ID:1Sc2IHo8(34/43)調 AAS
APPENDは結合則を満たす。よって、X,Y,Zをこの順で結合したものを
APPEND(X,Y,Z)と書いてもいい。

36: 片山博文MZ ◆T6xkBnTXz7B0 2016/01/22(金)21:57 ID:1Sc2IHo8(35/43)調 AAS
数列の第2項を削除し、先頭にxを追加する変換器C_1は、
Z＝INSERT(ERASE(X,1),0,x)と書ける。
Y＝ERASE(X,1)＝ERASE2(X,1,1)の逆変換器はX＝INSERT(Y,1,X[1])であり、
Z＝INSERT(Y,0,x)の逆変換器はY＝ERASE(Z,0)と書ける。
よってC_1の逆変換器はX＝INSERT(ERASE(Z,0),1,X[1])と書ける。これは直感的に正しい。
X[1]は未知数となる。

37: 片山博文MZ ◆T6xkBnTXz7B0 2016/01/22(金)22:13 ID:1Sc2IHo8(36/43)調 AAS
【定義27】Z＝FOREACH(X,f)のFOREACHを次のように定義する。
Z[i]＝f(X[i]) (0≦i＜#(X))
かつ#(Z)＝#(X).

38: 片山博文MZ ◆T6xkBnTXz7B0 2016/01/22(金)22:15 ID:1Sc2IHo8(37/43)調 AAS
明らかに変換器Z＝FOREACH(X,f)の逆変換器は
X＝FOREACH(Z,f^(-1))である。

39: 片山博文MZ ◆T6xkBnTXz7B0 2016/01/22(金)22:26 ID:1Sc2IHo8(38/43)調 AAS
【定義28】２項演算子「+」と#(X)＝#(Y)を満たすX,Yについて、
Z＝EACHOTHER(+,X,Y)を次のように定義する。
Z[i]＝X[i]+Y[i] (0≦i＜#(X))
かつ#(Z)＝#(X).

40: 片山博文MZ ◆T6xkBnTXz7B0 2016/01/22(金)22:30 ID:1Sc2IHo8(39/43)調 AAS
明らかにZ＝EACHOTHER(+,X,Y)の逆変換器はX＝EACHOTHER(-,Z,Y)である。

41(2): 片山博文MZ ◆T6xkBnTXz7B0 2016/01/22(金)22:48 ID:1Sc2IHo8(40/43)調 AAS
変換器Cが全単射であることと、Cの逆変換器が存在することは同値である。
全単射でなければ逆変換に未知数が発生して逆変換器は一意にならない。

42: 片山博文MZ ◆T6xkBnTXz7B0 2016/01/22(金)23:16 ID:1Sc2IHo8(41/43)調 AAS
戦略としては、変換器Cを細かい変換器c_1, c_2, ..., c_nに分解して、
それらがすべて全単射ならば、Cは全単射と言える。

44: 片山博文MZ ◆T6xkBnTXz7B0 2016/01/22(金)23:48 ID:1Sc2IHo8(42/43)調 AAS
Z＝REPLACE(X,h,y)の逆変換器はX＝REPLACE(Z,h,X[h])である。
ここにX[h]は未知数である。

45: 片山博文MZ ◆T6xkBnTXz7B0 2016/01/22(金)23:55 ID:1Sc2IHo8(43/43)調 AAS
Z＝REPLACE(X,h,m,Y)の逆変換器はX＝REPLACE(Z,h,#(Y),SUB(X,h,m))である。
ここにSUB(X,h,m)は未知数となるが、長さはmであることが確定している。

上下前次1-新書関写板覧索設栞歴

ｽﾚ情報赤ﾚｽ抽出画像ﾚｽ抽出歴の未読ｽﾚ AAｻﾑﾈｲﾙ

ぬこの手ぬこTOP 0.682s*