2016年度後期:単位修得予定者

微分積分/演習 平均65点
1518008
1518012
1518020
1518025
1518039
1518047
1518052
1518059
1518068
1518071
1518079
1518092
1518100
1518101
1518103
以上

情報数学基礎(幸谷クラス) 平均75点
1518004
1518008
1518012
1518016
1518020
1518024
1518028
1518032
1518036
1518040
1518044
1518048
1518052
1518056
1518060
1518064
1518068
1518072
1518084
1518088
1518092
1518096
1518104
1518108
1518112
以上

「効率的な手順とは?」 : 2/1 裾野高校模擬講義

1.初めに
 世の中にはいろいろな「作業」があります。楽しい作業,苦しい作業,大変な作業,楽な作業・・・傍から見ているのと実際にその作業を行ってみるのでは全く異なる感想を持つ,なんてことはよくあることです。「計算」なんてその最たるものでしょう。数学と聞くともう数式を見るのも嫌い!,という人は多いですが,小学校の時に習った四則演算(足し算,引き算,掛算,割算)であれば,楽しかったかどうかはともかく,少ない桁数の自然数どうしでしたらそれほど時間をかけることなく実行できるはずです。例えば\[2\times 2\times 2\times 2\times 2 = 2^5 = 32\]なんて計算ができないという人はまずいないでしょう。

 さて「作業」にもイロイロありますが,ここではその開始から終了までに要する「時間」を考えてみたいと思います。作業に要する時間は,どのぐらいの手間がかかるのか,つまり,その作業を行うために必要となる最も簡単かつ短時間で終わる小作業の回数をカウントすることで大体の見積もりを取ることができます。先に挙げた\(2^5\)を計算する作業は,2を掛けるという小作業を4回繰り返すことで32という結果を得て完了することができました。従って,これが\(2^6\), \(2^7\), …, \(2^n\)であっても,掛算をそれぞれ5回,6回,…, \(n\)回実行すれば,計算結果を得ることができ,作業を完了することができるわけです。

 しかしもっとこの作業を効率的にできないものでしょうか? 同じ作業を実行するにしても,初めて経験する人よりは,普通は,その作業を経験したことのある人の方が「効率的」=「短い時間で済む」=「少ない小作業の回数で済ませる」ことができますよね? それは同じ作業を繰り返すことで,「この小作業は不要,ここでこの小作業をすることで効率的になる」ということに気が付くからです。現在はどんな工場でも,どんな事務所でも,どんな会社でも,短い時間で効率的に作業を行うことが求められます。これができないとどうなるか? そう,同じ仕事量でも完了までにいたずらに時間がかかり,いつまでたっても帰れない「ブラック企業」と言われることになってしまうわけです。サービス残業させられて残業代も出ないようなら,短い時間で済ませてさっさと定時退社した方がいいですよね?

 さて,先ほど実行した\(2^n\)の計算ですが,もっと効率的に実行する方法がありますよね? そう,掛算の回数を減らすことはそんなに難しくないですよね? まぁ電卓が手元にあれば,という前提で考えてもらうと,例えば\[2^5 = (2\times 2)^2 \times 2 = 32\]という手順であれば,3回の掛算で済むことになります。\(2^6\)ですと,\[ (2\times 2)^3 = (4\times 4) \times 4 = 64\] となってこれも3回で済みます。・・・と考えていくと,一般に\(2^n\)の場合,\(n\)の2進表記が\(n = (p_k p_{k-1} \cdots p_1 p_0)_2\)であれば,\[2^n = 2^{2^k\cdot p_k} \times 2^{2^{k-1}p_{k-1}} \times \cdots \times 2^{2{p_1}}\times 2^{p_0} \]という手順で済むことが分かります。つまり\(2^{100}\)であれば,99回の掛算が必要になるところを,\(100 = (110010)_2\)より,\[ 2^{100} = 2^{2^6+2^5+2^2} = 2^{64 + 32 + 4} = 2^{64}\times 2^{32} \times 2^4 \]となり,\[ 2^{64} = (((((2^2)^2)^2)^2)^2)^2 \] ですから6回の掛算で済み,この途中結果を覚えておくとすると自動的に\(2^{32}\)と\(2^4\)が得られますので,合計8回の掛算で済むわけです。ちなみに答えは\[\begin{split} 2^{100} &= 18446744073709551616\times 4294967296\times 16\\ &= 1267650600228229401496703205376\end{split} \] となります。

 単純な掛算でも計算回数を減らすことができるわけです。これが膨大な数の掛算を行うとなると,効率的な「手順」=「アルゴリズム」を使わない手はありません。

2.ハノイの塔問題
 ではもう少しゲーム的な「作業」を行ってみましょう。アルゴリズムを考えるときには必ず題材になる有名なパズル「ハノイの塔」というものです。
 次のような積木があるとします。

hanoi_3units

 この積木を一番端の棒に移動させて下さい。但し次の条件を必ず守って下さい。

  • 円盤は1枚ずつしか移動できません。移動先は必ず他の棒になります。
  • 小さい円盤の上に大きな円盤を載せてはいけません。
  • 作業は全ての円盤が一番端の棒に,大きさ順に刺さったところで完了します。

 さて,ではこの3枚のハノイの塔問題を,なるべく「効率的」に解いて下さい。

 解答は下記のYouTube動画にあります。

3.トランプの並べ替え:クイックソート
 日常的に良くある作業として「並べ替え」があります。これを効率的にできないものでしょうか?

 例えばジョーカーの入っていない52枚のトランプをスペード,クローバー,ハート,ダイヤモンドの組に分け,それぞれ番号の小さい順に並べ替える問題を考えてみます。どうすればなるべく早くに並べ替えが完了するでしょうか?

 例えば,下記のYouTube動画に示す「クイックソート」という手順は如何でしょうか?

4.おわりに
 コンピューターは人間と違って莫大なデータ量(ビッグデータ)を扱うために使用されます。従ってちょっとでも非効率的なアルゴリズムを使うと途端に膨大な時間を無駄にすることになりかねません。効率的な手順を考えることは,コンピューターを効率的に使うことにもつながります。作業が早く完了すればそれだけ電気代が節約できますからね。
 我々コンピューターの専門家はこのような「効率的」なアルゴリズムを考えることが重要な仕事の一つなのです。

卒研メモ:JavaScript + Canvasでフラクタル図形描画

 ”JavaScript Fractal”で検索すると色々なサンプルスクリプトが出てきますが,トップに出てくるこのサイトのものが一番アプリケーションとして出来が良いようです。

Canvas Fractals

「高性能計算研究室」という看板を出している以上は,これに対して何らかの改良を施したいところです。定番の工夫としては

  • 並列化して高速化・・・Node.js環境下だとParallel.jsというのがあるらしい。以前はFirefoxネイティブにRiverTrailというIntel提供のプロジェクトがあったのですが,最近はOpenCL対応にしたとかでよく分からないことになっている。
  • 高精度化・・・手っ取り早く4倍精度化(double-double)化するというのが定番。調べたところではJavaScript実装はまだない模様(任意精度対応のBigDecimal.jsというのは存在)

というところかと。

 まずCanvasにお絵かきするためにjCanvasの勉強から始めて倍精度計算でJulia集合を描き,それを利用して4倍精度化を図る・・・という感じかしら。誰かやりません?

 

2016年明けました

 明けましておめでとうございます。
 三年生は自由製作を、四年生は卒研を頑張って完成させて下さい。

 2016年もよろしくお願い致します。