米田優峻:問題解決のための「アルゴリズム×数学」が基礎からしっかり身につく本

作成日 : 2023-07-19
最終更新日 :

概要

「はじめに」から引用する。

本書は、「数学に苦手意識があるけれど、この機に数学とアルゴリズムを学び、プログラミングなどに応用できるようにしたい」 「数学は苦手ではないが、これまでに学んだ数学の知識を元にして、応用可能な形でアルゴリズムを理解したい」という両方の目的で利用できる内容となっています。

感想

オールカラーなのがいい。私にはわからなくても、図面を見ているだけで心がなごむ。

最短経路

p.127 の節末問題にある、問題 3.7.3 を引用する。体裁は多少変更している。

下図の碁盤目状道路において、スタート（S）からゴール（G）まで最短経路で行く方法は何通りありますか。ただし×印は通れない交差点を示しています。

G S

本書サポートページである github には動的計画法を使って得られた値として 126 通りという解答が出ている。 私は数学で計算して求めることにした。以下はその解である。

まず、通れない交差点を無視すると、S から G まで行く方法は `{::}_10C_5 = (10*9*8*7*6)/(5*4*3*2*1) = 252` 通りある。
次に、通れない交差点を経由する方法を数える。まず左にある通れない交差点を経由する方法は、`{::}_4C_2 * {::}_6C_3 * = (4*3)/(2*1) * (6*5*4)/(3*2*1)= 6 * 5 * 4 = 120` 通りある。 そして、右にある通れない交差点を経由する方法は、`{::}_6C_1 * {::}_1C_1= 6` 通りある。これら 2 つの通れない交差点をどちらも経由する方法はないので、 求める方法は `252 - 120 - 6 = 126` 通りとなる。

近似値

p.152 の節末問題にある、問題 4.3.4 を引用する。

四則演算のみを使って `10^0.3` の近似値を計算するプログラムを作成してください。pow 関数や sqrt 関数など、四則演算ではないものは使ってはなりません。 なお、ニュートン法を使わなくても構いません。

本書サポートページには解法のヒントはあるが、プログラムそのものはない。ヒントの解法は２つあり、ひとつはニュートン法を使うもの（p.151 の 4.3.6 を参照）、 もう一つは二分探索法を使うものである。ところで、`10^0.3` をプログラムを書かずに近似値を求めよ、と言われたらどうするだろうか。私だったら慌てる。 慌てない人は、次のように考えるのだろう。

`10^0.3 = 10^(3/10) = (10^3)^(1/10) = 1000^(1/10)` である。`a = 1000^(1/10)` とすれば、`a^10 = 1000` ということである。すると、コンピュータ屋ならば、2 のべき乗をずらずら並べていくのが得意だから、 `2^10= 1024` であることは思い出せるだろう。1024 は 1000 より少し多いから、きっと `a` は 2 よりわずかに小さい値であるはずだ。 では 2 よりわずかに小さいはずの値を計算機を使わずに得るにはどうすればよいか。一般化２項定理を使えばなんとかなるだろう。`x` の絶対値が 1 に対して十分小さいとき、複素数 `alpha` に対して

`(1+x)^alpha = 1 + alphax + (alpha(alpha-1))/(2!)x^2 +(alpha(alpha-1)(alpha-2))/(3!)x^3 + cdots`
というやつである。この式を適用できるようにしてみよう。
`10^0.3 = 1000^(1/10) = (1024-24)^(1/10) = (2^10(1-24/1024))^(1/10) = 2(1-3/128)^(1/10) ~= 2(1- 3/1280)`
この上の右辺の、`a` の近似値を `hat(a)` とする。ここで 3/1280 を計算するのが少し骨だが、頑張れば 0.00234375 が得られる。この値から `hat(a) = 1.9953125` であることがわかる。 一方真の値は、https://keisan.casio.jp/calculator で `1000^0.1` を計算させると、`a=1.99526231496887960135cdots` であることがわかる。 したがって、`hat(a)` は `a` と小数第3位まで等しい、まあまあの近似値になっている。`10^0.3` という数値は、 このような計算がしやすいように選ばれているのかもしれない。

p.161 の節末問題にある、問題 4.4.2 を引用する。

以下の定積分の近似値を求めてください。プログラムを書いて計算しても構いません。GitHubに掲載されている「実際の解」との絶対誤差が 10^-12 以下であることが望ましいです。

`int_0^1 2^(x^2) dx`

これはプログラムを書いて計算しても構いません。とあるが、実際には手計算で解く方法はなく、プログラムを書いて計算するしかない問題である（積分の数表があるのかもしれないが）。 WolframAlpha によれば、この不定積分は `1/2 sqrt(pi/(log(2))) "erfi"(xsqrt(log(2)))` (`"erfi"` は虚数誤差関数) である。本書のサポートページの解答を見ると、 （被積分関数を `f(x)` とすると） `f(x)=2^(x^2)` の場合は `f(x)` が複雑であるため、厳密な答えを計算するのは非常に難しいです。としている。

数式

数式には MathJax を用いている。

書誌情報

書名 問題解決のための「アルゴリズム×数学」が基礎からしっかり身につく本
著者 米田優峻
発行日 2022 年 3 月 23 日 初版 第 5 刷発行
発行元 技術評論社
定価 2680 円（本体）
サイズ
ISBN 978-4-297-12521-9
その他 越谷市立図書館で借りて読む

まりんきょ学問所 ＞ コンピュータの本 ＞ アルゴリズム ＞ 米田優峻:問題解決のための「アルゴリズム×数学」が基礎からしっかり身につく本

MARUYAMA Satosi