[場所1E501（月曜日5限）]
HPに行く
manabaに行く
今日は前回残った問題とLangのLinear algebra とMatousekの33-Miniaturesの
Miniature 1を読みました。
Linear algebra
以下のような文章がありました。
このorderというのは規律だとか命令、注文などの他に数学では順番(順序)という
文脈でよく使われます。数学では他に、群の位数(群の集合としての数と一つの元
が持つ単位元になるまでの最小の正の数という場合もある)という意味で用いられることも
あります。
本文に戻ります。
ベクトル空間において足し算は、厳密には２つの和が定義されているだけなので、一気に例えば４つを足すという操作は定義されていません。なので、便宜的に、まず、u+v をし、さらにそれに w を足し、さらにそれに、z を足してとりあえず定義しなさいと言っています。つまり、
しかし、ベクトル空間のベクトル同士の足し算は結合律と、可換性があるので、足し合わせ方を便宜的に定めたが、実はどのような順番に足しても同じになります。
ちなみに
VS1 は、(u+v)+w=u+(v+w)
VS4 は、u+v=v+u
です。
この２つのルールだけを使えば、４つに限らず、どんなに多くの数の元を
足すことも、その順番によらないことが示されます。
これは厳密に証明がいります。
少し脱線して、例えば、4つのベクトルを足し算する方法がいくつあるのかを
数えてみます。
足し算の形式としては以下の２種類が考えられます。
ただし、可換性を使ってU+V=V+Uを仮定しておきます。
最初に２つを足し、そのあとに、その他の１つを足し、最後に残りの１つを足す
という方法(上の本文に書いてあった方法)と、
最初に２つを足し、残りの２つ同士も足し、できた２つの元どうしを足す
という方法です。
かっこのつけ方で言えば、
((*+*)+*)+*
と
(*+*)+(*+*)
です。
最初の形式では、((a+b)+*)+*
の a,b を選ぶ方法は、{}_4C_2=6 通り。
のこりを並べる方法は２通りなので、全部で１２通り。
２番目の形式であれば、４つを２つのグループに分ける方法の数ですが、
まず、４つのうち２つを取る方法の数は {}_4C_2=6 。
そのうち、４つの残りの２つをとる方法も同時に数えてしまっているので、
その分を割って 6/2=3 通りとなります。
(もしくは、どれか一つを固定して考える。それと一緒になる元をどれか選べば
２つのグループに分けることができるその相手の探しかたはのこりの３つの
どれかだから3通り)
よって、全部で 12+3=15 通りとなります。
Fibonacci Numbers, Quickly
の部分を読みました。内容としてはそれほど問題はなかったかと思います。
フィボナッチ数とは F_0=0, F_1=1, F_{n+2}=F_{n+1}+F_n なる漸化式を満たす
数列 F_n のことです。すぐわかることですが、全て自然数を値とする数列です。
この数列をいかに速く求めるか？という問題の内容です。普通に考えれば、
F_n の値を求めるには、この漸化式を使って、n 回くらい計算をすれば
求められるはずですが、実はもっと手早く計算する方法があるということです。
フィボナッチ数列の漸化式の行列表示
まず、フィボナッチ数列の漸化式を下のように、
\begin{pmatrix}F_{n+2}\\F_{n+1}\end{pmatrix}=M\begin{pmatrix}F_{n+1}\\F_n\end{pmatrix}
M=\begin{pmatrix}1&1\\1&0\end{pmatrix}
２進法とその応用
次に２進法を使います。
任意の自然数は、
n=2^{k_1}+2^{k_2}+\cdots+2^{k_t} (0\le k_1<k_2<\cdots<k_t) のように
２進展開をすることができます。
２進展開を用いれば、上の行列の n 乗は
M^n=M^{2^{k_1}}\cdots M^{2^{k_t}}
となります。
例えば、M^{2^m} を求めるには、
M,\ M^2,\ (M^2)^2=M^4=M^{2^2},\ (M^{2^2})^2=M^{2^3},\cdots
から、m 回計算をすれば済むことがわかります。
一般の自然数 n において F_n を求める計算にしても、
M^n=M^{2^{k_1}}\cdots M^{2^{k_t}}
HPに行く
manabaに行く
今日は前回残った問題とLangのLinear algebra とMatousekの33-Miniaturesの
Miniature 1を読みました。
Linear algebra
以下のような文章がありました。
It is possible to add several elements of a vector space. Suppose we wish to add four elements, say u, v, w, z. We first add any two of them, then a third, and finally a fourth. Using the rules VS1 and VS4, we see that it does not matter in which order we perform the additions.
ベクトル空間のいくらかの元を付け加えることができます。４つの元を付け加えたいとします。たとえば、u, v, w, zとしましょう。まず、それらの任意の２つを足し、それから３つめを足し、最後に、４つ目を足します。規則VS1とVS4使えば、足し算をする順番には問題がないことがわかります。
このorderというのは規律だとか命令、注文などの他に数学では順番(順序)という
文脈でよく使われます。数学では他に、群の位数(群の集合としての数と一つの元
が持つ単位元になるまでの最小の正の数という場合もある)という意味で用いられることも
あります。
本文に戻ります。
ベクトル空間において足し算は、厳密には２つの和が定義されているだけなので、一気に例えば４つを足すという操作は定義されていません。なので、便宜的に、まず、u+v をし、さらにそれに w を足し、さらにそれに、z を足してとりあえず定義しなさいと言っています。つまり、
((u+v)+z)+w
ということです。しかし、ベクトル空間のベクトル同士の足し算は結合律と、可換性があるので、足し合わせ方を便宜的に定めたが、実はどのような順番に足しても同じになります。
ちなみに
VS1 は、(u+v)+w=u+(v+w)
VS4 は、u+v=v+u
です。
この２つのルールだけを使えば、４つに限らず、どんなに多くの数の元を
足すことも、その順番によらないことが示されます。
これは厳密に証明がいります。
少し脱線して、例えば、4つのベクトルを足し算する方法がいくつあるのかを
数えてみます。
足し算の形式としては以下の２種類が考えられます。
ただし、可換性を使ってU+V=V+Uを仮定しておきます。
最初に２つを足し、そのあとに、その他の１つを足し、最後に残りの１つを足す
という方法(上の本文に書いてあった方法)と、
最初に２つを足し、残りの２つ同士も足し、できた２つの元どうしを足す
という方法です。
かっこのつけ方で言えば、
((*+*)+*)+*
と
(*+*)+(*+*)
です。
の a,b を選ぶ方法は、{}_4C_2=6 通り。
のこりを並べる方法は２通りなので、全部で１２通り。
２番目の形式であれば、４つを２つのグループに分ける方法の数ですが、
まず、４つのうち２つを取る方法の数は {}_4C_2=6 。
そのうち、４つの残りの２つをとる方法も同時に数えてしまっているので、
その分を割って 6/2=3 通りとなります。
(もしくは、どれか一つを固定して考える。それと一緒になる元をどれか選べば
２つのグループに分けることができるその相手の探しかたはのこりの３つの
どれかだから3通り)
よって、全部で 12+3=15 通りとなります。
Fibonacci Numbers, Quickly
の部分を読みました。内容としてはそれほど問題はなかったかと思います。
フィボナッチ数とは F_0=0, F_1=1, F_{n+2}=F_{n+1}+F_n なる漸化式を満たす
数列 F_n のことです。すぐわかることですが、全て自然数を値とする数列です。
この数列をいかに速く求めるか？という問題の内容です。普通に考えれば、
F_n の値を求めるには、この漸化式を使って、n 回くらい計算をすれば
求められるはずですが、実はもっと手早く計算する方法があるということです。
フィボナッチ数列の漸化式の行列表示
まず、フィボナッチ数列の漸化式を下のように、
\begin{pmatrix}F_{n+2}\\F_{n+1}\end{pmatrix}=M\begin{pmatrix}F_{n+1}\\F_n\end{pmatrix}
M=\begin{pmatrix}1&1\\1&0\end{pmatrix}
として、書き直しておけば、次のフィボナッチ数を求めるのに、足し算の漸化式
ではなく、行列 M を掛け算をすることでも得られることがわかります。
これを繰り返せば、任意のフィボナッチ数は、
\begin{pmatrix}F_{n+1}\\F_{n}\end{pmatrix}=M^n\begin{pmatrix}F_{1}\\F_0\end{pmatrix}
のように得られることがわかります。
ではなく、行列 M を掛け算をすることでも得られることがわかります。
これを繰り返せば、任意のフィボナッチ数は、
\begin{pmatrix}F_{n+1}\\F_{n}\end{pmatrix}=M^n\begin{pmatrix}F_{1}\\F_0\end{pmatrix}
のように得られることがわかります。
２進法とその応用
次に２進法を使います。
任意の自然数は、
n=2^{k_1}+2^{k_2}+\cdots+2^{k_t} (0\le k_1<k_2<\cdots<k_t) のように
２進展開をすることができます。
２進展開を用いれば、上の行列の n 乗は
M^n=M^{2^{k_1}}\cdots M^{2^{k_t}}
となります。
例えば、M^{2^m} を求めるには、
M,\ M^2,\ (M^2)^2=M^4=M^{2^2},\ (M^{2^2})^2=M^{2^3},\cdots
から、m 回計算をすれば済むことがわかります。
一般の自然数 n において F_n を求める計算にしても、
M^n=M^{2^{k_1}}\cdots M^{2^{k_t}}
ですが、2乗を繰り返す操作を k_t 回繰り返せば、それまでに M^{2^{k_i}} も同時に
求めていることになるので、それぞれの成分 M^{2^{k_1}} は k_t 回計算すれば全て得られます。さらにその成分同士を t 回かける操作がありますので、
厳密には t+k_t だけ計算すればよいことになります。
しかし、t\le k_t であるので大体、2k_t くらい計算すればよいということになります。
また、掛け算といっても、行列を求めるには、本当は行列の成分の４倍くらい
計算しなければなりませんが、それを数えたとしても 8k_t くらいです。
計算しなければなりませんが、それを数えたとしても 8k_t くらいです。
M^n が計算できたとすれば、実はその (2,1) 成分がちょうど F_{n} ですので、
高々 2k_t (計算の量を 8k_t と数えてもよい)くらいの計算量で求められるという
ことになります。
k_t\le \log_2n
なので、係数が２でも８でも高々、n の \log のオーダー(order)くらいの計算量で済むということになります。(このオーダーも上の使い方とも異なります。)
結論として、フィボナッチ数列を計算する計算量を n から \log n まで節約(手早く)できたというこになります。
0 件のコメント:
コメントを投稿