Mae向きなブログ

Mae向きな情報発信を続けていきたいと思います。

ビットコインはどのようにして動いているのか？ 数学を使わずに理解するビットコインの動作原理

Book

ビットコインという単語は以前から耳にしていたものの、なんとなく後ろめたいものなのではというイメージを持ってしまったことから、近づかないようにしていたように思います。ところが最近では新聞などでも話題になっており、どんなものなのか興味が出てきました。まずは本を読んでみようと思ったのですが、本書を選んだのは、本書がビットコインの動作原理について解説してある本であり、儲ける方法を解説した本ではなかったからです。

読み始めてみると、誤字とか脱字とか、漢字の使い方などに気が散ってしまうところがあったのですが、読み終えてみると満足感を得られる本でした。以前、『暗号技術入門 第3版　秘密の国のアリス』を読んでいたことが本書を読み進める上で役に立ったと思います。電子署名、ハッシュ関数などの昔からある技術をうまく組み合わせて新しい仕組みが出来上がってるんですね。

ビットコインの話の中では「マイニング（採掘）」という言葉もよく聞きますが、ビットコインを掘るとは??という疑問も本書を読んで解消することができました。

本書の最終章に、

例えば、誰から誰に何を渡すといった、所有権の移動であれば、多くの場合がビットコインのようなブロックチェーンとProof of Work(発掘）の仕組みで実現できます

とあります。ビットコインの仕組みが仮想通貨だけではなく、社会を大きく変える可能性を秘めているということも理解できたように思います。

ビットコインはどのようにして動いているのか？ 数学を使わずに理解するビットコインの動作原理

ビットコインはどのようにして動いているのか？ 数学を使わずに理解するビットコインの動作原理

数学ガールの秘密ノート/積分を見つめて

Book

受験勉強のために公式を学び何度も練習した積分がこんなに面白いものだったなんて! というのが本書を読み終えた直後の率直な感想です。区分求積法という言葉には聞き覚えはありますが、第2章を読んだときに感じたようなワクワクした感覚を高校生のときに感じなかったのは、やはり受験で点を取るためだけの学習しかしてこなかったからかもしれません。

この2乗和の

\displaystyle \sum_{k=1}^{N}k^2 = \frac{N(N+1)(2N+1)}{6}

公式も覚えた記憶はありますが、導出過程から学んでいれば大いに親しみを持って暗記できたような気がします。

なぜ、

\displaystyle (e^x)' = e^x

なのか、

なぜ、部分積分は以下のように書けるのか。

\displaystyle \int f(x)g'(x) dx = f(x)g(x) - \int f'(x)g(x) dx + C

単なる暗記に頼らない勉強をすると面白さがどんどん広がっていくような気がしますね。受験勉強というと、点が取れればいいというような考えに陥りがちですが、せっかくやるなら驚きとか楽しさとか、そんな感覚を味わえるようなものであって欲しいなと思います。

f:id:rahaema:20170701122413j:plain:w350

数学ガールの秘密ノート/積分を見つめて (数学ガールの秘密ノートシリーズ)

数学ガールの秘密ノート/積分を見つめて (数学ガールの秘密ノートシリーズ)

平成21年度秋期応用情報午後問2

Ruby 情報処理技術者試験

平成21年度秋期 応用情報技術者試験(AP)の午後問題2は文字列照合に関する問題でした。

文字列照合といったら、遥か昔、学生時代に

といったアルゴリズムがあるということは習って知っていましたが、パターン文字列の情報を利用して効率よくスキップするということ位しか理解できていませんでしたので、今回はいい学習の機会となりました。

h21a_ap_pm2.rb

実行結果

問題では、以下の2種類が示されています。

  • 方法1は、単純な照合方法
  • 方法2は、効率的な照合方法(クヌース–モリス–プラット法)

今回は、

  • 方法3として、効率的な照合方法(ボイヤー-ムーア法)

も加えて速度比較を行って見ました。

英大文字、小文字から長さ100万のランダムなテキストを生成し、パターンは生成したテキストの末尾300文字を設定しています。

実行結果は以下の通りです。方法1の単純な照合方法の遅さも際立っていますが、方法2に比して、方法3のボイヤー-ムーア法の効率の良さも際立つ結果となりました。

$ ruby h21a_ap_pm2.rb
                           user     system      total        real
Naive                999700
  0.720000   0.010000   0.730000 (  0.729970)
Knuth–Morris–Pratt   999700
  0.190000   0.000000   0.190000 (  0.187722)
Boyer-Moore          999700
  0.010000   0.000000   0.010000 (  0.011079)

参考

平成23年度特別試験応用情報午後問2

Ruby 情報処理技術者試験

平成23年度特別試験 応用情報技術者試験(AP)の午後問題2は集計表(CSV)をHTMLに変換して出力するプログラムに関する問題でした。

h23tokubetsu_ap_pm2.rb

input.csv

東京都,千代田店,23500
東京都,中央店,33500
東京都,港店,18500
埼玉県,川口店,28000
埼玉県,蕨店,9500

実行結果

$ ruby h23tokubetsu_ap_pm2.rb input.csv > output.html

簡単な問題だと油断して最初に得られた結果が以下です。

f:id:rahaema:20170624103331p:plain:w350

間違いを修正して実行したのが以下です。実際に自分で手を動かして作ってみると間違いにすぐに気付くことができますが、ただ紙上で解くだけだと模範解答を見るまで気づけなかったかもしれないなと思います。

f:id:rahaema:20170624103544p:plain:w350

平成25年度春季応用情報午後問2

Ruby 情報処理技術者試験

平成25年度春季 応用情報技術者試験(AP)の午後問題2は逆ポーランド記法に関する問題でした。

h25h_ap_pm2.rb

実行結果

$ ruby h25h_ap_pm2.rb
1 2 3 * +
2 3 + 4 *

参考

Unity5入門

Book

Unityという言葉は少し前から聞いたことがあったのですが、とうとう必要に迫られてUnityについて勉強し始めました。Web上にも有用な情報はたくさんありそうですが、まずは本を読みながらUnityの概要や基本のキについて身につけたいところです。なかなか高機能なのでどこまで学べばゴールになるのでしょうか。ゴールの設定が難しそうです。

Unity5入門　最新開発環境による簡単3D＆2Dゲーム制作

Unity5入門　最新開発環境による簡単3D＆2Dゲーム制作

参考URL

平成26年度春季応用情報午後問3

Ruby 情報処理技術者試験

平成26年度春季 応用情報技術者試験(AP)の午後問題3はフロイドの循環検出法の問題でした。循環小数の循環節を検出する問題…。なんか以前出会ったことがあるなと過去を振り返ってみると、Project EulerのProblem 26でした。そのときは、割った余りをハッシュに格納していき、再び同じ余りに出会ったら循環節検出という単純な方法で解いています。せっかくフロイドの循環検出法について解いてみたので、両者を速度比較してみました。

h26h_ap_pm3.rb

実行結果

実行結果は以下のようになりました。フロイドの循環検出法は、ウサギがカメに追いついたとき、ウサギはスタート地点に戻され、再び一歩ずつ進むなど、なんとなく遅いイメージがあるのですが、実際に実行してみるとフロイドの循環検出法が早いという意外な結果となりました。不思議です。

$ ruby h26h_ap_pm3.rb
                 user     system      total        real
ウサギとカメ     14939
  2.390000   0.000000   2.390000 (  2.404701)
単純な方法      14939
  3.410000   0.120000   3.530000 (  3.537377)

参考