# Algorithms with PDFs
1.1-1
ソートを必要とする実社会での応用あるいは凸包を必要とする実社会での応用を説明せよ。
ソートはまあいいとして、凸包は初めて聞きました。
凸包-wikipedia
ダウンロード.png
こんな感じで与えられた要素(画像の場合は点)を全て内包する最小の凸多角形のことらしいです。
これらの点が釘の場合、輪ゴムを引っ掛けると凸包の形になります。
回答
ソート-図書館の本の陳列
凸包-CG処理(ポリゴングラフィック)
昔の3Dゲームのグラフィックは3次元の凸包の組み合わせで表現されているように見えます。
(FF7の戦闘シーンとか、そんな感じ)
ソートは色んな所で使われている気がしますが、例で出した図書館で言うと、本とかがソートされずにどこにあるかわかんない！ってなったら借りるほうも困るし、図書館で本を管理する人たちも困りますよね。
1.1-2
実社会の枠組みの中で用いられる計算速度以外の効率の尺度をあげよ。
回答
メモリ使用量、データ転送量
省メモリなアルゴリズム
無駄なI/Oのないアルゴリズムを心がけたいです。
1.1-3
以前に見たことのあるデータ構造についてその長所と短所を挙げよ
回答
データ構造-配列
長所-検索が高速。O(1)
短所-要素の挿入、削除が遅い。挿入or削除した分、メモリのアドレスをずらさなければならない。
逆に連結リストの場合は
長所-検索が遅い。1番目に格納されているデータからポインタをたどる必要がある
短所-要素の挿入、削除が高速。挿入、削除した前後のデータのポインタを変更すれば良い。
1.1-4
最短経路問題、巡回セールスマン問題の類似点と違いについて述べよ。
巡回セールスマン問題-wikipedia
最短経路問題-wikipedia
回答
複数のルートから距離が最短となるものを選択する、という点が類似点。
違いは巡回セールスマン問題は全てのノードを通る必要があるが、
最短経路問題はスタートとゴールのみが決められていて、他のノードは必ずしも通る必要がない。
1.1-5
最適解しか意味を持たない実社会の問題を示せ。また近似解で意味を持つ場合の問題も示せ。
回答
電子商取引の暗号化複合化は最適解でないと意味がない。(暗証番号盗まれたなどのアルゴリズム以外の原因を除いて、本人だと証明出来なければ意味がない。)
トラックのドライバーが荷物を運ぶ最短ルートを計算する問題は現実的な計算時間で、ある程度効率的なルートが判明するのであれば問題ない。
1.2-1
アプリケーション層でアルゴリズムが必要になる応用の例を挙げ、必要とされるアルゴリズムの機能を議論せよ。
書籍では地図アプリの最短経路探索を紹介されていましたね。
回答
例えばオセロのゲームアプリを例に挙げてみます。
専門家ではないので、予想になりますが、
盤面の評価関数に基づき、n手先までの盤面を評価し、最も有利な手を選択するという手法を用いると思います。
n手先まで予想する場合、およそnの累乗のような形で実現し得る盤面が存在します。
（序盤や終盤はおける場所が限られているので底は小さいが、中盤は底が大きな値を取る。）
もちろんなるべく先の手順まで読んだほうが強くなりそうなので、nは大きな値を取りたいですが、
計算時間が増え過ぎるのはユーザー体験として良くないでしょう。
探索のアルゴリズムを効率的にすることにより、限られたリソースで最も良い手を選択することができると思います。（小並感）
1.2-1
同じ計算機上で挿入ソートとマージソートの実現を比較する。サイズnnの入力に対し、挿入ソートの実行には8n28n2ステップかかり、一方、マージソートの実行には64nlog2n64nlog2nステップかかるとする。挿入ソートがマージソートに優るnnの値を調べよ。
回答
これ普通に高校数学で方程式解けるんでしたっけ？(汗)
まあ、サイズを整数として扱えば計算していけばわかります。
調べよとのことなのでpythonに調べてもらいました。
```1.2-2.py
# -*- coding: utf-8 -*-
import math
import numpy as np
from matplotlib import pyplot
def main():
x = np.linspace(1, 100, 100)
y1 = 8 * (x ** 2)
y2 = 64 * x * np.log2(x)
pyplot.plot(x, y1, label="insertion sort")
pyplot.plot(x, y2, label="merge sort")
pyplot.legend()
pyplot.xlabel("X-axis")
pyplot.ylabel("Y-axis")
filename = "1.2-2.png"
pyplot.savefig(filename)
if __name__ == '__main__':
main()
```
およそ43くらいですかね。
nnはサイズなので整数として扱います。43前後の整数をいくつか実際に計算して調べましょう。
対話モードで検証します。compare関数で計算時間の小さい方のアルゴリズムを出力します。
```
>>> def insertion(x):
... return 8 * (x ** 2)
...
>>> import numpy as np
>>> def merge(x):
... return 64 * x * np.log2(x)
...
>>> def compare(x):
... return 'merge' if merge(x) < insertion(x) else 'insertion'
...
>>> compare(42)
'insertion'
>>> compare(43)
'insertion'
>>> compare(44)
'merge'
>>> compare(45)
'merge'
```
上記の通り、サイズ43までは挿入ソートが優り、サイズ44以上はマージソートに軍配があがります。
1.2-3
同じ計算機上で、実行時間が100n2100n2のアルゴリズムが、実行時間が2n2nのアルゴリズムより高速に実行できる最小のnnの値を調べよ。
回答
```1.2-3.py
# -*- coding: utf-8 -*-
import math
import numpy as np
from matplotlib import pyplot
def main():
x = np.linspace(1, 100, 100)
y1 = 100 * (x ** 2)
y2 = np.power(2, x)
pyplot.plot(x, y1, label="100n^2")
pyplot.plot(x, y2, label="2^n")
pyplot.legend()
pyplot.xlabel("X-axis")
pyplot.ylabel("Y-axis")
pyplot.yscale("log")
filename = "1.2-3.png"
pyplot.savefig(filename)
if __name__ == '__main__':
main()
```
だいたい13～14くらいかな。
これも調べてみましょう。
```1.2-3.sch
(define (min_n n)
(if (< (y1 n) (y2 n))
(- n 1)
(min_n (+ n 1))))
(define (y1 n)
(* 100 (expt n 2)))
(define (y2 n)
(expt 2 n))
(print (min_n 1))
>14
```
唐突のscheme。
2n2nの方が大きくなったときの一個前のnを返却するmin_n関数により14と求められました。
めでたしめでたし。
2.1-1 挿入ソートの手順
2.1-2 挿入ソート手続きは非減少順でソートする。これを書き換えて非増加順でソートするようにせよ。
```
INSERT-SORT(A)
for j=2 to A.length
key = A[j]
i = j-1
while i>0 かつ A[i]<key
A[i+1] = A[i]
i = i-1
A[i+1] = key
```
2.1-3 探索問題; input/`len(A) = n の数列Aとある数字v` output/`v = A[i] となる添字i、またはvがAの中に存在しないときはNil`
```
LINEAR-SEARCH(v, A)
i = Nil
for j=1 to A.length
if v == A[j]
i = j
break
return i
```
2.1-4 2つのn要素配列A,Bに蓄えられた2つのnビットの2進数のワを求める問題を考える。この2つの整数の和は2進数として(n+1)要素配列Cに蓄える。このときの疑似コードは？
```
CALC-BITS(A, B)
n = A.length
for i=1 to n+1
C[i] = 0
for i=1 to n
v = A[i] + B[i] + C[i]
C[i] = v % 2
if v >= 2:
C[i+1] = 1
return C
```
2.2-1
Θ(N^3)
2.2-2 配列Aに蓄えられたn個の数を選択ソートで並べ替える。
```
SELECT-MIN-POS(A, left, right)
min_pos = left
for i=left to right
if A[i] < A[min_pos]
min_pos = i
return min_pos
SELECTION-SORT(A)
for i=1 to A.length-1
min_pos = SELECT-MIN-POS(A, i, A.length)
tmp = A[i]
A[i] = A[min_pos]
A[min_pos] = tmp
```
なぜA[n-1]まででよいのか。→ 勝手に大きいのが後ろに来るから
最良→Θ(n), 最悪Θ(n!)
2.2-3
最悪 Θ(N) 平均 Θ(N/2)
2.2-4
増加率が大きい項のオーダーが下がるようにする。
2.3-1 マージソート
2.3-2 MERGEを番兵を使わないように記せ。ただし全ての要素がAに戻ってしまった場合はAに書き戻せ
```
MERGE(A, p, q, r)
n1 = p - q + 1
n2 = r - q
L[1..n1+1] と R[1...n2+1]を２つの新しい配列とする
for i=1 to n1
L[i] = A[p+i-1]
for j=1 to n2
R[j] = A[q+j]
i = 1
j = 1
for k = p to r
if i > n₁
A[k] = R[j]
j = j + 1
else if j > n₂
A[k] = L[i]
i = i + 1
else if L[i] ≤ R[j]
A[k] = L[i]
i = i + 1
else
A[k] = R[j]
j = j + 1
```
2.3-3 nが2のべき乗の時、漸化式
T(n) = 2 (n=2) or 2T(n/2) + n (n=2のk乗)
の解がT(n) = nlg(n)で有ることを数学的帰納法で示せ
2.3-4 A[n-1]までをソートしたやつにA[n]につなげて再帰的にやれば実質挿入ソート
n=1 then T(n) = Θ(1) n>1 then T(n) = T(n-1) + C(n-1) C(n)は挿入するための計算量
2.3-5 2分探索の疑似コード
```
BINARY-SEARCH(v, A)
i = Nil
left = 1
right = A.length
while left < right
mid = (left + ritht)/2
if A[mid] == v
i = mid
break
if A[mid] < v
right = mid + 1
else
left = mid - 1
return i
```
T(n) = T(n-1) + c
2.3-6 挿入ソートの順次探索を2分探索にしたら最悪実行時間はΘ(nlg(n))に改善するか。
改善しない。 ２分木探索したところで、挿入する数を入れ替える処理は行わなければならない。
2.3-7 n個の整数の集合Sととある整数xが与えられた時、Sの中の2個の要素で。それらの和がちょうどxになるものが存在するかどうかを判別するΘ(nlog(n))時間のアルゴリズムは?
```
BINARY-SEARCH(v, A)
i = Nil
left = 1
right = A.length
while left < right
mid = (left + ritht)/2
if A[mid] == v
i = mid
break
if A[mid] < v
right = mid + 1
else
left = mid - 1
return i
EXISTS-PAIR(S)
A = MERGE-SORT(S, 0, S.length)
for i = 1 to S.length
if BINARY-SEARCH(x - S[i], A) != NIL
return true
return false
```
3.1-1 f(n),g(n)を漸近的な非負の関数とするΘ記法の基本的な定義を用いてmax(f(n),g(n))=Θ(f(n)+g(n))を証明せよ
3.1-2
```
## b乗根を取る？
(n+a)^b = Θ(n^b)
であるためには、ある正の定数 c1, c2, n0 が存在して、すべての n >= n0 に対して
0 <= c1*n^b <= (n+a)^b <= c2*n^b
を満たす。
ここで
n+a <= n+|a| <= 2*n, n >= |a|
また
n+a >= n-[a] >= 1/2*n, 1/2*n >= |a|
n>=2|a|の時、
0 <= (1/2)*n <= n+a <= 2n
とすると、
0 <= (1/2*n)^b <= (n+a)^b <= (2*n)^b
0 <= (1/2)^b*n^b <= (n+a)^b <= 2^b*n^b
なので、
c1 = (1/2)^b, c2 = 2^b, n0 = 2|a|
をとると
0 <= c1*n^b <= (n+a)^b <= c2*n^b
を満たす。
```
3.1-3
O記法は上界を示し、下界を示すものではないので、
少なくとも O(n^2) である
という表現自体が誤り。
3.1-4
先に解答を書くと
- 2^(n+1) = O(n^2)は成立する。
- 2^2n = O(n^2)は成立しない。
2^(n+1) = O(n^2)の証明
```
2^(n+1) = 2*(2^n)
なので、ある正の定数 c1, n0 が存在して、全ての n>=n0>0に対して
0 <= 2^n <= c1*2^n
は、この場合 c1=2 なので、n0=1 の時満たす。
```
2^2n != O(n^2)の証明
```
2^2n = 2^n * 2^n
なので、ある正の定数 c1, n0 が存在して、全ての n>=n0>0に対して
0 <= 2^n <= c1*2^n
は、c1=2^n なので、どういった条件でもこれを満たすことはできない。
```
4.1-1
負の数のみであっても、最大部分配列の総和となる数。 値は負の数。
4.1-2
```
FIND-MAXIMUM-SUBARRAY(A, low, hight)
sum = -∞
left = 0
right = 0
for i=low to hight
curr_sum = A[i]
for j=i+1 to hight
curr_sum = curr_sum + A[j]
if sum < curr_sum
sum = curr_sum
left = i
rigth = j
return (left, right, sum)
```
4.1-3
再帰版
```
def find_max_crossing_subarray(A, low, mid, hight):
total = 0
left_total = None
max_left = None
for i in xrange(mid, low-1, -1):
total = total + A[i]
if total > left_total:
left_total = total
max_left = i
total = 0
right_total = None
max_right = None
for j in xrange(mid+1, hight+1):
total = total + A[j]
if total > right_total:
right_total = total
max_right = j
return max_left, max_right, left_total+right_total
def find_maximum_subarray(A, low, hight):
"""
>>> A = [13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7]
>>> find_maximum_subarray(A, 0, len(A)-1)
(7, 10, 43)
"""
if hight == low:
return (low, hight, A[low])
mid = (low + hight) // 2
left_low, left_hight, left_total = find_maximum_subarray(A, low, mid)
right_low, right_hight, right_total = find_maximum_subarray(A, low, mid)
cross_low, cross_hight, cross_total = find_max_crossing_subarray(A, low, mid, hight)
if left_total >= right_total and left_total >= cross_total:
return left_low, left_hight, left_total
if right_total >= right_total and right_total >= cross_total:
return right_low, right_hight, right_total
return cross_low, cross_hight, cross_total
```
総当り版
```
def find_maximum_subarray_by_brute_force(A, low, hight):
"""
>>> A = [13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7]
>>> find_maximum_subarray_by_brute_force(A, 0, len(A)-1)
(7, 10, 43)
"""
total = None
left = 0
right = 0
for i in xrange(low, hight):
curr_sum = A[i]
for j in xrange(i+1, hight):
curr_sum = curr_sum + A[j]
if total < curr_sum:
total = curr_sum
left = i
right = j
return left, right, total
```
n0 は下記を実行して、だいたい59くらい。
```
def calc_n0():
import timeit
n0 = 10
while True:
setupSt = 'from find_maximum_subarray import find_maximum_subarray, ' \
'find_maximum_subarray_by_brute_force; import random; ' \
'A=[random.randrange(-9999, 9999) for i in xrange(%d)]' % n0
t1 = timeit.timeit('find_maximum_subarray(A, 0, len(A)-1)',
number=100, setup=setupSt)
t2 = timeit.timeit(
'find_maximum_subarray_by_brute_force(A, 0, len(A)-1)',
number=100, setup=setupSt)
if t1 < t2:
break
n0 = n0 + 1
return n0
```
それぞれを計測した結果 左から順に、再帰、総当り、ミックス。
```
>>> from find_maximum_subarray import calc_time
>>> calc_time(58)
(0.017922163009643555, 0.020307064056396484, 0.019782066345214844)
>>> calc_time(1000)
(0.34097981452941895, 4.765131950378418, 0.33513402938842773)
```
4.1-4
空の部分配列を解として許すということは、マイナスになる場合のこと。
再帰版だったら、下記の２箇所で、
```
FIND-MAX-CROSSING-SUBARRAY
FIND-MAXIMUM-SUBARRAYの最初の処理
```
Sign in with Wallet
Connect another wallet