象牙の塔4階2号室

アスペとADHDの高専生によるブログ(不定期更新)

December 23th 冬休み0日目

 お年玉プレゼントということで新年の抱負を語ろうというのが、はてなブログの「お題」に追加されてる。やろうかな?

 タイトル、本来なら学校がある日だったというのもあって今日は冬休み0日目。

日記

 9時辺りに起床。10時に朝食。16時に昼食。19時に夕食。そしてその後風呂。その間にAOJにて

早起きは三文の得...

 この頃ショートスリーパーに憧れているのだが、千里の道も一歩からということで先ずは現行の7時間半から1時間半早く起きることを拘ろうと思っている。因みにショートスリーパーは遺伝と言われることもあるが個人的にはある程度はなんとでもなると思いたいし、日課のブログ更新をし忘れたときに夜中にも関わらず起きることができる程度の能力はあるので無視する。

 この拘りの根拠として人間の睡眠におけるレム睡眠ノンレム睡眠の周期が1時間半であることがある。レム睡眠のときは覚醒状態に近いので起きやすいらしい。

 そんで今日は、生活リズムに脳がバグったのか散らかった部屋にクラスメートが来ているという悪夢を見て混乱したものの目覚ましなしで、6時間と少しの睡眠時間で起きることができた。しかし体力の低下と眠気を一日中感じており先行き不安に陥っている。

競プロリハビリ(動的計画法)

 さて、そのようにして出来た冴えない頭を以て動的計画法を用いたプログラミングの問題を1問解いた。しかしやはり脳が冴えないのと、今回は昨日書き始めたばかりのとある言語で書く縛りを設けているので一つの問題に時間をかけすぎた。(動的計画法についてはあまり踏み込まない。)

 今回の問題は行列の積を計算する際に発生するスカラー積の計算を最小にするように、与えられた行列を順に全部掛けたときのそのスカラー積の計算回数を求めるというものだ。因みに入力は行列の個数の後に行列の行数と列数がその行列の個数分だけ渡されるという具合。これにおいてわざわざ行列の中身を考える必要はない。

行列の積の計算回数
 \begin{pmatrix}
a_{11}&a_{12}&a_{13}\\
a_{21}&a_{22}&a_{23}
\end{pmatrix}
\begin{pmatrix}
b_{11}&b_{12}&b_{13}&b_{14}\\
b_{21}&b_{22}&b_{23}&b_{24}\\
b_{31}&b_{32}&b_{33}&b_{34}
\end{pmatrix}
=
\begin{pmatrix}
a_{11}b_{11}+a_{12}b_{21}+a_{13}b_{31}&a_{11}b_{12}+a_{12}b_{22}+a_{13}b_{32}&a_{11}b_{13}+a_{12}b_{23}+a_{13}b_{33}&a_{11}b_{14}+a_{12}b_{24}+a_{13}b_{34}\\
a_{21}b_{11}+a_{22}b_{21}+a_{23}b_{31}&a_{21}b_{12}+a_{22}b_{22}+a_{23}b_{32}&a_{21}b_{13}+a_{22}b_{23}+a_{23}b_{33}&a_{21}b_{14}+a_{22}b_{24}+a_{23}b_{34}
\end{pmatrix}

 例えば上記の例は2\times 3行列と3\times 4行列の積だが、これのスカラー積は2\times 3\times 4=24個ある(関係ないけど\timesの記号、紛らわしいよね...。)

 一般にa\times m行列とm\times b行列の積においてamb個のスカラー積が発生する。

考え方

 行列を大文字で表記する。

 3個の行列A_0, A_1, A_2を考える。この時、考慮すべき計算は(A_0A_1)A_2A_0(A_1A_2)の二通りある。この二通りの計算によって上記に示したスカラー積の個数は変わってくるのでうまく組み合わせろというのが問題の本質。

 先ほどの行列にもう一個、A_3を追加して考える。この時、考慮すべき計算は ( ( A_0A_1 ) A_2 ) A_3 ( A_0 ( A_1A_2 ) ) A_3 ( A_0A_1 ) ( A_2A_3 )  ( A_0 ( ( A_1A_2 ) A_3 )  ( A_0 ( A_1 ( A_2A_3 ) ) の五通りがある。

 このうち、前二つの計算結果は3つの場合で考えたときのそれを流用できる。あとの3つも同じように部分的な計算をあらかじめ行った後に評価するという方法で解くことができる。これを可能とするのが動的計画法である(余談だが軍事施設でこの手法が研究された当時、数学嫌いの大統領に配慮してこの名前(Dynamic Programming(動的計画法))になったそう。)

vs.問題

 この問題はAOJ(会津大学の公開しているサービス)に載っていたものだ。これは「アルゴリズムとデータ構造」の授業内でお世話になっているもので、だれでも使うことができる。

onlinejudge.u-aizu.ac.jp

 さて、今回の問題に関して私は愛用のJavaや授業で扱ったC言語およびC++ではなく、「Ruby」を用いて解いた。それも学習開始が一日前。

 「Ruby」というのは日本産のプログラミング言語で、サーバサイドにて用いられているらしい。またオブジェクト指向なのが特徴で、それもJavaでいうオブジェクトではない、プリミティブ型にあたるものもオブジェクトとして扱えてしまう。

 ちなみに採用理由は「言語自体への興味」。サーバとか考えてない。

成果

 時間は数時間もかかってしまったが解けた。

課題

レポート0 Webサーバの脆弱性

 やってない

レポート2 交流回路の周波数特性

 やってない

レポート8 ソートアルゴリズムの比較

 やってない

レポート7 Raspberry Piを用いたLED制御

 やってない

レポート4,5 コンピュータ設計演習

 やってない

英語CⅡ Workbook Lesson7

 やってない

英語CⅡ Workbook Lesson8

 やってない

計測工学Ⅱ レポート

 やってない

計測工学Ⅱ 演習問題

 やってない

現代社会 レポート

 やってない