アルゴリズムをめぐる冒険–勇敢な所学者のためのPythonアドベンチャー
著者：Bradford Tuckfield
訳者：竹川文則、川上悦子、高柳愼一
発行所：共立出版(株)
印象に残ったこと：
アルゴリズムで問題解決
外野手問題：解析的解法とアルゴリズム的解法の全く異なる解法がある
ボールが着地する場所を人間が正確に知る方法
解析的解法：ガリレオモデル
風と空気抵抗がないと仮定し、ボールが地面から放たれた時、このボールの時間tにおける水平方向の位置xは、x方向（水平方向）の初速度をv1とすると、以下の公式で与えられる
x = v1 * t
ボールの高さyは、y方向（垂直方向）の初速度をv2とするとき、下記のようになる
y = v2 * t + ( α * t ** 2) /２
上記より、y = (v2 / vi) * x + (α * x ** 2) / ( α * x ** 2) / (2 * vi ** 2)
時間tのおける水平方向の位置xは、下記の公式で与えらえれる
x = -b ± sqrt((b**2 - 4 * a * c）／（2 *a）
アルゴリズム的解法：チャップマンアルゴリズム（自分の首で考える）
1.地面とボールへの視線が作る角度のタンジェントの加速度を観察する※
2.もし加速度が正なら、後ろに下がる
3.もし加速度が負なら、前にすすむ
4.ボールが目の前に車でステップ1～3を繰り返す
5.ボールをキャッチする
※ボールを目で追うために首を後ろに方向けるたびに生じる首間接の加速度を感じることで、角速度が確認できる
この解法を使えば、風による軌道の変化やボールのバウンドにも動的に対応できる
このプロセスには解析的方法のように、xを解く戦略や明示的な方程式が一切必要ない
たった一つの入力（首を傾ける動きが加速する感覚）しか必要とせずに、定められたゴール（ボールをキャッチすること）を達成する
「アルゴリズム」という言葉は、先に紹介した偉大なアル=フワーリズムミの名前からとられている
アルゴリズムとは、明確に定義された結果を実現するための指示の集合
われわれ人間は生まれながらにしてアルゴリズムの世界で生きている
歴史上のアルゴリズム
ロシア農民の掛け算
Pythonによるプログラム例１：（本には記載されていない方法）
print(“n1とn2の掛け算を行います。”)
n1 = int(input(“n1 =”))
n2 = int(input(“n2 =”))
n4 = 0
print(“\n通常の掛け算による計算：”)
print(“n1 * n2 =”,n1 * n2)
print(“\nロシア農民の掛け算による計算：”)
print(f'{“n1”:^10}{“n2”:^10}{“n1が奇数:1 “:^20}’)
while(n1 >= 1):
n3 = n1 % 2
n4 = n4 + n3 * n2
print(f'{n1:>10}{n2:>10}{n3:^20}’)
n1 //= 2
n2 *= 2
print(“n1 * n2 =”,n4)
実行例１：
n1とn2の掛け算を行います。
n1 =89
n2 =18
通常の掛け算による計算：
n1 * n2 = 1602
ロシア農民の掛け算による計算：
n1 n2 n1が奇数:1
89 18 1
44 36 0
22 72 0
11 144 1
5 288 1
2 576 0
1 1152 1
n1 * n2 = 1602
Pythonによるプログラム例２：（本に記載されている方法）
n1 = 89
n2 = 18
print(n1 * n2)
halving = []
doubling = []
while(n1 >= 1):
halving.append(n1)
n1 //= 2
doubling.append(n2)
n2 *= 2
print(halving)
print(doubling)
import pandas as pd
half_double = pd.DataFrame(zip(halving,doubling))
half_double = half_double.loc[half_double[0]%2 == 1,:]
answer = sum(half_double.loc[:,1])
print(answer)
ユークリッドの互除法:2つの数の最大公約数を見つけるための方法
Pythonによるプログラム例：（本に記載されている方法をベースにアレンジ）
def qcd2(x,y):
larger = max(x,y)
smaller = min(x,y)
remainder = larger % smaller
if(remainder == 0):
return(smaller)
felse:
return(qcd2(smaller,remainder))
実行例：qcd(8,12)
結果：4
関数の丘と谷－最大化と最小化-
勾配上昇法、勾配降下法：関数の最大値や最小値を効率的に見つけるためのシンプルだが効果的な手法
曲線に対する勾配ということで，微分値である「接線の傾き」に沿って解を探索し続ける（移動の方向を購買の計算により求める）ことにより最大値や最小値を求める方法
1回の条件を解くことで関数の最大値を求めるアルゴリズム
1.最大値を求めたい関数の導関数を計算する
2.導関数を0とおく
3.ステップ2の方程式を解いて導関数が0となる点を求める
4.ステップ3で求めた点が最小値ではなく最大値であることを確認する
※導関数の解を見つけることが難しく、時には不可能な場合がある
勾配法に関しては、下記がわかりやすく説明されているので参考になる
勾配法の仕組みを具体例でわかりやすく解
極値の問題
最大値や最小値を求めるすべてのアルゴリズムは、非常に深刻な潜在的問題を抱えている
極地（局所的最大値と局所的最小値）に関する問題である
勾配上昇法は正しく実行できたとしても、最終的に到達できた頂点が「ローカル」な頂点に過ぎない可能性がある
勾配上昇法の素朴な「戦略」では、グローバルな最大値（真の頂点）「に到達できない
アルゴリズムを使うべきでない場合
アルゴリズムを学ぶことで、強力なパワーを手に入れた感覚で満たされることがある
アルゴリズムを知って亥いることよりも、いつそれをつかうべきでないかを知っていることの方が大事になることがある
手もとの問題に対し、アルゴリズムはどんなときに不適切あるいは不十分なのか、どんなときに他のより良い方法があってそれを代わりに試すべきなのかを知っていることが大切である
アルゴリズムは実用的な目的の達成に非常に役に立つ、
アルゴリズムはゴールを効率的に達成できる一方で、そもそのどの目標に追求する価値があるのかを決めるという、より哲学的なタスクにはあまり向いていない
アルゴリズムはわれわれを利口にしてくれるが、賢くしてはくれない
アルゴリズムの優れた能力は、間違った目的に使用された場合は役にたたない、もしくは有害にもなりうる
（第1章～第3章から）
以上
