質問＜３６７０＞２００８年１月１４日from=小豆「コンピュータープログラム（十進BASIC）」
４次正方行列A，Bの積をと表すが
この定義をと変更したときの行列の積
を計算するプログラムを作成せよ。
行列の積を求めるMATは使えるようになりましたが、
積の定義を変更するには,どうすれば良いのですか？
教えて下さい。宜しくお願いします。
★希望★完全解答★
初めて見ると「ギョ」っとする問題ですね(笑)。
 | ←初めてこの問題を見た時の亀田の心境(笑) |
全く何のこっちゃ分からない(苦笑)。
しかも整合性が取れるようにも思えんし(笑)。
しかし、よくよく読んでみると、僕が言うのも何なんですが、「非常に良く出来た数学の問題」だと思います。はい。
ちょっと次の問題を考えてみましょう。
自動車は道路の左側を走ります。
これは確かに正しいですよね。逆を走れば警察に捕まります(笑)。何故なら、法律でそうしろ、と定義されているから、ですよね。
では何で車は左側を走らなきゃなんないのよ?と訊かれるとこれに答えるのは難しい。まあ、歴史的経緯とか色々あるんでしょうが、結局のトコ便宜上そう定義されているだけで、例えばこれは「神が決めた」と言ったような真実である、とか無い、とか言うのとは全然関係ない話なんです。
事実、
自動車は道路の右側を走ります。
と決めてる国もありますよね。例えばアメリカとか。ところ変われば品変わる、とは良く言ったモンです。
さて、数学に目を移すと、実は同じような構造を含んでいます。つまり、
計算が出来るのは計算方法が定義されているからだ
って事なんです。
んじゃあ、一体誰が定義したのか?と言うと「人間が」です。上の例と同じように実は数学ではその殆どが「自然発生的に」計算方法が確立したワケでは無くって、「人間が整合性があるように計算方法を定義した」ってのがホントのトコなんです。「人間が決めた約束事に従って」計算する。ここがポイントなんですね。
この問題の面白いトコは「では勝手に決めた規則だったらどうなるか?」って辺りなんですよ(笑)。
行列の計算なんてのはこの「恣意性」の最たるモノだと思います。確かに連立一次方程式の解法をどうする?と言う歴史的な課題があって成立した分野なのは事実なんですが、反面、単なる括弧に括られた要素の並び、と考えてみた時、あまりにも不自然な計算法を確立してますよね(笑)。僕も高校生くらいの時、行列は苦手で嫌いだったんで
「何じゃこりゃ?何でこんな計算せなアカンの?」
とぶーたれてました(笑)。
そう言う恨みがこの問題を作ったんでしょうか(笑)。発想が面白いです(笑)。
「勝手に定義するから勝手な方法で計算させてくれ!!!」
と言うのは、受験数学では許されませんが、実はかなりの部分で数学の本質的な部分じゃないかな、と思います。そして、そう言う「発想の切り替え」と言うのがこの問題のポイントなんです。
つまり、「勝手に作った規則に則って動くプログラムを書け」と言うのが、この問題の大意です。
なお、残念ながら亀田は全然BASICは書けないんで、要点だけ挙げておきます。親切な人がいたら「BASIC化」してくれるかもしれません(笑)。
注:もっと言っちゃうとBASICは難しくてメンド臭くてヤです(笑)。ハッキリ言うと「Fortranをそのうち学びたい」とでも思わない限り、BASICを習う必然性ってのはあんま無いと思っています。
- ４次正方行列A，Bの積を
と表す
今までの流れで見てきてもうお分かりでしょうが、実はこの一文は基本的には全く問題としては関係ありません。ただの前フリです(笑)。
が、行列Aのどの要素と行列Bのどの要素が計算対象になるのか示唆してはいるんで、一応基本をおさえておきましょう。
例えば次の行列A、行列B、行列Cがあるとします。
そうすると、普通の数学上の数列の積の定義では、C=A×Bだとすれば、例えば行列Cの要素の一つ、は次のように書き表せます。
同様に、は次のように書き表せます。
この様に、aの添字の2つ目とbの添字の1つ目は必ず数値が一致します。
従って、行列Cの要素を一般化して記述すると、
となりますね。
ここで重要なのは、上の「数学上の数列の積の定義」が大事なんじゃなくって、以降の「勝手に決めた数列の積の定義に於いて」数列Aのどの要素と数列Bのどの要素を計算に用いるのか。その示唆だけが重要なんです。 - この定義を
と変更したときの行列の積
ここから「勝手に決めた数列の積の定義」が登場します。
ところで、argminと言うのは、ある複数の要素(計算結果)が出た場合、「その中から最小の値を選べ」と言う意味です。あまりポピュラーではない書き方なんですが、たまに見かけますね(笑)。
ここでちょっと具体的に見てみましょう。
例えば次のような行列Aと行列Bがあったとします。
さて、ここで「勝手に作った行列の積」を利用して行列Cを計算してみます。
定義
に従うと、例えば行列Cの要素
4つの要素の中で一番小さい数は4です。従って、
が答えとなります。
つまり、配列を利用して最小値を探す関数(min)を用いて成分を返せ、と言ってるワケです。 - 行列の積を求めるMATは使えるようになりました
と言うワケで、十進BASICで定義されている行列の積を求めるMATを使う必要はありません(と言うか使えないでしょう)。
DEF文等を使って新しく関数を作る必要性があります。 - 積の定義を変更するには,どうすれば良いのですか？
もう一度言いますが、元々十進BASICで定義されている積の定義を変更する必要性はありません。単に新しい関数なりサブ・ルーティンを設計すれば題意を満たします。
調べてみた限り、十進BASICはGPL(General Public License)で配布されているようなんで、ソースコード自体を変更する事は可能です。
そして、十進BASIC自体はPascalで記述されているそうで、別にPascalの知識があれば、ソースコードを改変してコンパイルしなおす事は出来るでしょう。
ただし、それをこの問題でやれ、って言ってるワケじゃないんです(かつ、それをやっちゃったら後でまた直すのが大変な作業になります・笑)。
大事なのは、- 行列を配列として読み込み、
- 対応する配列の要素を読み込み、
- それらを計算規則に則って和を取り、新たな配列に入れ、
- その中から最小値を探しだし、
- それらをまた配列として4行4列の行列として返す。
ような手続きなり関数を定義しろ、と言ってるワケです。
以上です。
参考までにSchemeで書いた「新しく定義した行列の積」を計算するプログラム、weird-mul(ヘンな掛け算、の意)を挙げておきます。
なお、本来だったら、Schemeで定義されているデータ型であるvector(C言語やBASICで言う配列)を使うべきかもしれませんが、メンド臭いんでリストを使います(笑)。本質的にはリストであろうとvectorであろうと変わらないんですが、若干vectorの方が含まれる要素へのアクセススピードが速いんで、このテの行列計算ではvectorの方が好まれるらしいです。
ちなみに、MaximaはSchemeの親戚であるCommon Lispで記述されていますが、アチラは多分vectorを用いて計算規則を記述しているでしょう。興味のある人はMaximaのソースコードでも読んでみてください。
註:ここで特にプログラミング言語Schemeを取り上げている理由の一つは、上にも書きましたが、Maximaと言うソフトウェアは基本的にSchemeの親戚であるCommon Lispと言う言語で書かれているから、です。また、Maximaは十進BASICと同様にGPLで配布されていて、その規定に依ると、誰でもソースコードを読もうと思えば読めるから、なんです。つまり、「仕組みを知りたい」と思えば仕組みを知る事が可能です。その辺がMicorosoft等が販売しているような商業用ソフトウェアと違う辺りです(オブジェクトコード＝Windowsで言うトコの.exeファイルはリバースエンジニアリング、と言う技術を使わないとソースの復元性は無い、と言われていますし、また、それはライセンスで禁止されています)。
つまり、ある程度Schemeが分かればMaximaの仕組みが(完全じゃないにせよ)ある程度分かるようになるでしょう。プログラムを真剣に勉強しよう、と言う人にとってはこのテのオープンソースのソフトウェアと言うものは「参考書/実例集」として非常に優秀なのです。
もっとも、Common LispはSchemeに比べればかなり複雑なんですが、それでも概要を知ろうと思えば知る事が出来る、と言う辺りが魅力です。
(そして亀田はMaximaのソースは読んだことありません・笑。がプロを目指してるのなら読んでみてもイイだろう、って事です)
なお、最初に約束事を定義しておきます。
実際問題、行列をリスト、ないしは配列を用いて表現するのは(見た目)難しいのですが、原理的には次のようにして大体のトコ表現します。
例えば、本文中に現れるような行列A、
は大体のトコロ「入れ子」で表現します。つまり、Schemeだったら、
'((1 0 2 0) (0 1 0 2) (2 0 1 0) (0 2 0 1))
のように書きますね。つまり、「リストのリスト」にしちゃうんです。BASICだったら「配列の配列」ですか。出来るかどうかは知りませんが(そして、これが出来ないとなると「難しい」でしょうねえ・笑)。
同様に、行列B
は
'((16 3 2 3) (5 10 11 8) (9 6 7 12) (4 15 14 1))
のように表現します。
では、取りあえずチャッチャとSchemeで書いたソースコードを紹介します。
なお、恐らく「プログラミング」として考えた場合、当初の「数学の」発想はさておき、かなり難しい問題ではあるんですよね。
Schemeでも少々てこずったんで、BASICではなおさらなんじゃないか、とは思います。
(恐らくBASICではループ文を入れ子にしないと書けないでしょう。Schemeの再帰定義の簡潔さとBASICのループ文の複雑さとの差に付いては＜質問3628＞参照。)
また、Scheme等のLisp系言語族で書く時の心構えなんですが、「なるべく短くソースを」書くのを目標とする為に、少々複雑なテクニックを投入しています。ただし、形式的には「普通の再帰的定義」の範疇に納めるようにトライしてみました(と言うことは、同じ内容の事柄をBASICで再現するとなるとコード量はかなり増えるでしょう)。
(define (weird-mul matA matB) ;関数weird-mulを引数matA、matBとして定義する。
(let loop ((ls0 matA) ;ls0の初期値はmatA
(ls1 matB) ;ls1の初期値はmatB
(ls2 ()) ;ls2の初期値は空リスト
(ls3 ())) ;ls3の初期値も空リスト
(cond ((null? ls0) ;ls0が空になったら?
(reverse ls3)) ;ls3を反転させて返す
((null? (car ls1)) ;ls1の先頭が空だったら?
(loop (cdr ls0) ;先頭を除外したls0
matB ;matBを呼び出す
() ;空リスト
(cons (map (lambda (ls) (apply min ls)) (reverse ls2)) ls3)))
(else ;それ以外の場合は
(loop ls0 ;ls0のまま
(map cdr ls1) ;ls1にcdrを写像
(cons (map + (car ls0) (map car ls1)) ls2)
ls3))))) ;ls3のまま
基本的な構文は＜質問3643＞で扱ったような「名前付きlet」構文を用いた組み立てです。要するに、局所関数loopを定義して、それを「再帰的に呼び出す」枠組みで書いています(BASICで言うと、＜質問3628＞で扱われていたような、DO〜LOOP構文ですね。)
今回は配列(リスト)の計算過程が少々複雑で、分岐して行くので、通常は
(let ＜局所関数名＞ (＜引数定義＞
(if ＜条件＞ ＜結果＞ ＜局所関数の再帰呼び出し＞)))
と単純なリストでif〜then構文を使って表現するトコロなんですが、ifの代わりに＜質問3590＞で扱ったcond文を用いて
(let ＜局所関数名＞ (＜引数定義＞
(cond (＜条件1＞ ＜結果＞)
(＜条件2＞ ＜局所関数の再帰呼び出し1＞)
(else ＜局所関数の再帰呼び出し2＞))))
と処理を三股に分けています。再帰呼び出しが2つ並列に行われている、って事ですね。
まあ、大まかに言うとそこが注意点なんですが、細かいポイントは後回しにしておいて、まずは擬似コードを書いてみます。
一応ソースにはコメントは付けていますが、意味がまだハッキリしないでしょうし、対応関係を掴みながら読んでみてください。
註:そして「そのまま」BASICで書けるかどうかはさておき、基本的な「考え方」はBASICでも同じ、と言うより「全てのプログラミング言語で同じ」筈です。色々な細かいテクニックは別として、「考え方」をどうやってBASICに翻訳しようか、と集中して下さい。その為に「疑似コード」と言われる「手続き(プロシージャ)の概要」が存在するんです。
- 関数weird-mulを引数matA(行列A)、matB(行列B)として定義する。
- 名前付きlet構文で局所関数loopを定義する。それの引数の初期値は
- リスト番号0(ls0)はmatA
- リスト番号1(ls1)はmatB
- リスト番号2(ls2)は空リスト
- リスト番号3(ls3)は空リスト
とする。なお、リスト番号2は計算途中で生じたリストを突っ込むスペース、最終的な計算結果はリスト番号3(ls3)とする。 - ls0(つまりmatA)が無くなったとき、ls3を反転させて結果を返す。
註:と言うのもls3は逆順の計算結果を返すから。後の計算を参照。 - ls1(matB)の先頭要素(car)が空リストの時、局所関数loopをその引数を以下の条件で再帰呼び出しする。
- ls0:その時、行列A(matA)の1行目を用いた計算が終わった事を示すので、次の計算対象は行列Aの2行目以降にならなければいけない。
そこで、ls0は(cdr ls0)に書き換えられる。 - ls1:その時、行列B(matB)は最終列まで計算が終わった事を示すので、行列Aがまだ残っていれば再び行列Bの1列目が計算対象とならなければならない。その為、ls1ではmatBを呼び戻す。
- ls2:行列A(matA)の1行目を用いた計算が終わった結果を突っ込むスペースがls2なので、計算が終わった以上ここは空リストへと戻す。それまでの計算結果はls3へと受け渡す。
- ls3:途中経過の計算結果、ls2の中から最小要素を抜きだし(map (lambda (ls) (apply min ls)) (reverse ls2))、それをls3の先頭に突っ込む(cons 計算結果 ls3)。
- ls0:その時、行列A(matA)の1行目を用いた計算が終わった事を示すので、次の計算対象は行列Aの2行目以降にならなければいけない。
- それ以外の場合は局所関数loopをその引数を以下の条件として再帰呼び出しする。
- ls0:行列Aの1行目に関する計算結果が終わっていないので、ここはそのままls0とする。
- ls1:行列Bの1列目の処理は終わっているので、残りの列が計算対象とならなければならない。その為、写像関数(map)を用い、ls1に含まれる全ての要素であるリストの最初を削除して残りを返す(map cdr ls1)。
- ls2:計算途中をls2の先頭に突っ込む(cons 計算途中 ls2)。それは行列A(ls0)の一行目(car ls0)を行列Bの1列目に適用したモノである。そのロジックは基本的には(map + (行列Aの一行目) (行列Bの一列目))として可算(+)をそれぞれのリストの要素順に適用する。なお、ここでも行列Bを処理して全ての要素の1つ目を取り出す為に写像関数(map)を用いて(map car ls1)と書く。
- ls3:行列Aの1行目に関する計算は終わってないので、ここは弄らずにそのままls3となる。
ちょっと文章で説明するとややこしいんですが、お分かりでしょうか?上記の「擬似コード」を良く読んで、数学的な説明と対比し、そして繰り返し計算を吟味すると、キチンと問題が「解ける」事が分かると思います。まあ、ここを理解するのが踏ん張りどころでしょうね。
なお、新規に出てきた関数で、多用しているのが写像関数mapです。これは原理的には＜質問3643＞で出てきた高階関数の一種です。これは別の関数を引数に取り、それを別の引数であるリストの要素に適用する(まさしく写像)する為の関数です。
ちょっと例を挙げてみましょう。
例えば、関数carはリストを引数に取り、次のような計算結果を返します。
(car '(4 4 3 1))
=>4
何故ならcarはリストの先頭要素を返す関数だからですよね。
ところが、今回は、相手が行列、つまりリストのリストです。
例えば次のようなリスト、
'((16 3 2 3) (5 10 11 8) (9 6 7 12) (4 15 14 1))
があった場合、リストの要素がリストであって、その内側にあるそれぞれのリストの先頭要素を返したい場合どうするのか?こう言う時に使うのがmapと言う関数なのです。
例えば
(map car '((16 3 2 3) (5 10 11 8) (9 6 7 12) (4 15 14 1)))
=>(16 5 9 4)
と返してくれます。各要素のリストの先頭要素がキチンと返っているのがお分かりでしょうか?
これをヒントに「map絡み」は読みといてください。→mapに付いてはコチラ!!!
また、applyってのも似たような作用があります。今回はminと言う最小値を返す関数を用いて記述していますが、これも要素である各リストの最小値を探す為の書き方ですね。まあ、この辺は端折ります。この辺でも参考にして下さい。
なお、上のプログラムを本文の行列A、行列Bを対象にして実行すると、
(weird-mul '((1 0 2 0) (0 1 0 2) (2 0 1 0) (0 2 0 1))
'((16 3 2 3) (5 10 11 8) (9 6 7 12) (4 15 14 1)))
=>((4 4 3 1) (6 3 2 3) (4 5 4 1) (5 3 2 2))
と言う答えが返ってきます。
すなわち、
となるようです。
確かめてみてください。
追加です。
某所で全く同じ問題があって、BASICによる回答が提示されていました。
INPUT N
DIM X(n,n)
DIM Y(n,n)
DIM Z(n,n)
MAT INPUT X
MAT INPUT Y
FOR i = 1 TO n
FOR j = 1 TO n
LET Z(i,j) = X(i,1) + Y(1,j)
FOR k = 2 TO n
IF Z(i,j) > X(i,k) + Y(k,j) THEN LET Z(i,j) = X(i,k) + Y(k,j)
NEXT k
NEXT j
NEXT i
MAT PRINT Z
END
Schemeだと再帰で済む辺りがFOR文の入れ子で書かれています。
参考にして下さい。
投稿
