[場所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 件のコメント:
コメントを投稿