2019-12-30

CS6.006 Problem Set 7を解く

今回で最後のPSet。

問題はこちら意訳が間違っていたらご指摘ください。

7-1

DPを実装する問題。漸化式が与えられているので境界条件に注意してコードする。また、遷移した親のアドレスも保持する必要がある。

7-2

会社の株価の過去データが与えられている。 1991年に買い、2011年に売るとして、もっとも儲けられる組み合わせを探す。

会社	株価(1991)	株価(2011)
Dale	12	39
JCN	10	13
Macroware	18	47
Pear	15	45

(a): 20ドルもっていた場合の最適な買い方は？

複数の株を同時に買うお金がないので、どれか一つ買えばよい。

Dale: 39 + (20 - 12) = 47
JCN: 13 + (20 - 10) = 23
Macroware: 47 + (20-18) = 49
Pear: 45 + (20 - 15) = 50

よってPearを一つ買えばok→正解。

(b): 30ドルもっていた場合の最適な買い方は？

複数の株を同時に変えるので組み合わせが多くなる。気をつける。以下の場合がある。

(Dale, Dale): 39 + 39 + (30 - 12 - 12) = 84
(Dale, JCN): 39 + 13 + (30 - 12 - 10) = 60
(Dale, Macro): 39 + 47 + (30 - 12 - 18) = 86
(Dale, Pear): 39 + 45 + (30 - 12 - 15) = 87
(JCN, JCN, JCN): 39 + (30 - 10 - 10 - 10) = 39
(JCN, Macro): 13 + 47 + (30 - 10 - 18) = 62
(JCN, Pear): 13 + 45 + (30 - 10 - 15) = 63
(Pear, Pear): 45 + 45 + (30 - 15 - 15) = 90

よってPearを二つかえばok→正解。

(c): 120ドルもっていた場合の最適な買い方は？

組み合わせを全部考えると大変なことになるので、サボる。 (b)から、30ドル買った時の最適な買い方はPearを二つ買うことなので、Pearを8つ買えば良さそうに見えるが、倍率的にDaleがもっとも高いので、現金が余らずに買えるときはDaleをなるべく買えば良いことがわかる。よって、 Daleを10株買えば良い。儲けはPearを8つ買うより、390 - 45 * 8 = 30多い。→正解。

次に、codingに関する条件が加わる。用意される変数は以下の通り。

変数	役割
total	持ち金
count	会社の数
start	1911年の株価が入っている配列
end	2011年の株価が入っている配列

以下ではナップザック問題との違いを考える設問が続く。ナップザック問題の変数は以下の通り。

変数	役割
items	アイテムの数
size	各アイテムの大きさが入っている配列
value	各アイテムの価値
capacity	ナップザックの容量

(d): この問題の変数であるtotalに対応するナップザック問題の変数は？

capacity→正解。

(e): この問題の変数であるcountに対応するナップザック問題の変数は？

items→正解。

(f): この問題の変数であるstartに対応するナップザック問題の変数は？

size→正解。

(g): この問題の変数であるendに対応するナップザック問題の変数は？

(最大化したいので)value→正解。

(h): ナップザック問題がこの問題にそのまま適用できない理由としてTrue/Falseを答えよ。

まず騙されたと思ってナップザックが使えると考えてみて、漸化式を作ると、

dp[i][j]: i番目の株までみて、残りj円である時の最大利益 dp[i+1][j] = max(dp[i][j], dp[i][j+start[i]] + end[i])

ここで、株は一個以上買うこともできるので、何個買ったかの情報も欲しい。また、実際の最大利益は、値上がり後の株価(end)だけじゃなく、余ったお金も足さないといけない。

問題の選択肢に戻る。以下は選択肢と自分の判断根拠。

1: この問題では、買う時と売る時の間に時間差があるから。

→時間差は現実的にはあるが、問題と関係ない。というかナップザックもつめたアイテムを後で売ると考えれば時間差がある。

2: この問題で扱う数字はintegerであるが、ナップザック問題におけるvalueの数字はintegerではないから。

→ 数が大きいだけなら配列の大きさを適切に大きくすれば良いだけなので理由にならない。

3: この問題では、余ったお金も利益に考慮しなければならないので、答えが無限大となる可能性がある。ナップザック問題にはこのような欠点を扱う概念がない。

余ったお金も利益に足していると、漸化式が計算されるたびに残金が加算されていくので、無限大になる可能性がある。よって理由として正しい。

4: ナップザック問題でいうsizeにあたる変数がこの問題にはない。

→: 購入時の価格がsizeにあたるので理由として間違っている。

5:この問題では二つ以上の株が買えるから

→: ナップザック問題でも二つ以上のitemが入れられる場合を考慮できるので、理由として間違っている。と思ったが、シンプルなナップザック問題のアルゴリズムが適用できない理由としては正しいのでは。

6: この問題では、買った株を全て売る必要がある。ナップザック問題ではそのようなことをする必要がないから。

→: endは2011年の株価だが、これからstartを引いて利益分だけ表す配列にすれば対応できる。よって理由にはならない。

→正解。(3と5がonly valid reasonと書いてある)

以下では、この問題を解くプログラムが与えられる。このプログラムは2つの関数からなり、1つ目の関数の実装として2通り、2つ目の関数の実装として3通りが考えられる。合計で5種類の関数が与えられる。(一つ一つの関数が長いので詳細はPDFを参照してください。)

stock-table-A (dpテーブルを埋めている)
stock-table-B (同上) -stock-result-A -stock-result-B -stock-result-C

以下では時間計算量を答える。

(i): stock-table-Aの最悪時間計算量は？

purchase[cash][stock]: 残金cashでstockが与えられている時、買うか買わないかを表す(True/False)。

$\Theta(count*total)$ →正解。

(j): stock-table-Bの最悪時間計算量は？

一つ前の設問と同じ。 $\Theta(count*total)$ →正解。

(k): stock-result-Aの最悪時間計算量は？

$\Theta(count)$ →正解。

(l): stock-result-Bの最悪時間計算量は？

$\Theta(count)$ →正解。

(m): stock-result-Cの最悪時間計算量は？

$\Theta(count + total)$

(n): stock-table-Aで行われる計算を式で書くと？

9-14行目の内容を式一つで表せば良い。

profit[cash, stock] = max(profit[cash, stock-1], profit[cash-start[stock], stock] + end(stock))

一番これっぽい選択肢は、5番目の選択肢。→正解。

(o): stock-table-Bで行われる計算を式で書くと？

profit[cash, stock] = max(profit[cash, stock-1], profit[cash-start[stock], stock-1] + end(stock))

一番これっぽい選択肢は、2番目の選択肢。→正解。

stock-table-Aとstock-table-Bの漸化式は、わずかに違うが、Aは同じ株を複数回買える時の漸化式で、Bは株が一度しか買えない場合の漸化式となっていて、全く違う。

設問(n): なぜこうなるか？

同じ株を何回も買えるという要素を含めて漸化式を書くところから始まる。

dp[i][j] = max(dp[i-1][j - ks[i]] + kend[i]) ... (j - k*s[i] >= 0となるような全てのk)

つまり、s[i]を0個, 1個, ..., ○個買う場合を考えて、その中から最大値を取ってくる操作である。こっちの漸化式は理解しやすいと思う。で、これをそのまま実装するとk回のforループが回り効率が悪いので、なんとか時間短縮する為に、この漸化式を簡単にする必要がある。ここで、dp[i][j-S[i]]は、dp[i][j]よりも先に計算されることに注目する。

dp[i][j-s[i]] = max(dp[i-1][j-ms[i]] + mend[i]) ... (j - m * s[i] >= 0となるような全てのm)

先ほど、dp[i][j]の更新でk = 0, 1, 2, ...と試す、という記述をした。つまりdp[i-1][j], dp[i-1][j-1s[i]], dp[i-1][j-2s[i]], ...の状態をみている。このうち、二つ目以降であるdp[i-1][j-1s[i]], dp[i-1][j-2s[i]], ...の部分は、dp[i][j-s[i]]の更新において、m=1, 2, ..., の状態をみることに等しい。つまり、dp[i][j-s[i]]は、dp[i-1][j-1s[i]], dp[i-1][j-2s[i]], ...の最大値がすでに計算されているのだ。

なので、dp[i][j]は、dp[i][j-s[i]]と、足りてないdp[i-1][j]のうち大きい方を取ることで正しく計算できる。これを表したのが、設問nのような式である。

以上。

(p) 5つのアルゴリズムの組み合わせのうち、どの組み合わせがナップザック問題への正しいプログラムになるか？

stock-table-Bは同じ商品を一度しか選ばない漸化式に基づいている。また、stock-result-Aも同じである。よって, stock-table-Bとstock-result-Aの組み合わせが正しい。

→不正解。stock-table-Bとstock-result-Bの組み合わせが正しい。 stock-result-Aはpurchaseの値をそのまま株数に加算していて、integerとして扱っているが、実際に計算されるpurchase配列にはbooleanの値が入っている。よってpurchaseの中身をintegerではなくbooleanとして扱っているstock-result-Bが適切とのこと。自分の不注意で間違えた。(Pythonならstock-result-Aもちゃんと動くと思うので自分の選択肢でも間違ってないと思うが。。。)

(q) 5つのアルゴリズムの組み合わせのうち、どの組み合わせがこの株価問題への正しいプログラムになるか？

stock-table-Aは同じ商品を複数回買える漸化式に基づいている。また、stock-result-Cのみが同じ商品を複数回買えることを表している。よって、stock-table-Aとstock-result-Cの組み合わせが正しい。→正解。

設問(r)以降は、新たな制約が加わる。各株に買える上限数が設定されている。

会社	株価(1991)	株価(2011)	上限
Dale	12	39	3
JCN	10	13	無限
Macroware	18	47	2
Pear	15	45	1

(r): 30ドルもっていた場合の最適な買い方は？

設問(b)でやったのと同じことを考える。Pearは2つも買えないので、DaleとPearを一つずつ買えば良い。→正解。

(s): 120ドルもっていた場合の最適な買い方は？

無限に買えるJCNは利益率が一番低いので、まず他の株を買えるだけ買って、余ったお金でJCNを買うのが良い。

Dale3株: 36ドル
Macroware2株: 36ドル
Pear1株: 15ドル

合計して、87ドル。余ったお金は120-87=33ドル。このお金でJCNを3つ買う。→正解。

(t): 買える株の数に制約がある場合のアルゴリズムの擬似コードを書け。時間計算量も記せ。justificationも記せ。入出力は以下である。

入力

total: 持っているお金

count: 株の種類数

start: 1991年時点での株価の配列

end: 2011年時点での株価の配列

limit: 株ごとの買える株数の配列

出力

儲けの最大値

stock-table-Aの擬似コードにおいて、profitにあたる配列だけ計算すれば良いので、(purchase配列は必要ない)擬似コードをなるべく真似する。 limit配列を作って、株を買うたびにlimit配列の数値をデクリメントし、if文で買えるかどうか判断すればよいのでは。 limit配列はdpの配列に載せることで、各状態(cashとstock)に対する残り株数がわかるようにする。

create table profit
for cash=0 to total
  profit[cash, total] = (cash, limit)
  for stock = 1 to count
    profit[cash, stock] = profit[cash, stock-1]
    current_limit = profit[cash, stock][1]
    if start[stock] <= cash and current_limit[stock]:
      leftover = cash - start[stock]
      current = end[stock] + profit[leftover, stock][0]
      if profit[cash, stock][0] < current:
        current_limit[stock] -= 1
        profit[cash, stock] = (current, current_limit)

justificationとしては、上に述べた漸化式

limitに関する部分はO(1)で計算できるので、時間計算量は、 $O(total*count)$

解答は、漸化式を簡単にしない形で各株を0, 1, ..., k個買うことをそれぞれ調べている。よって解答のアルゴリズムの計算量は[tex:O(totalcountcount)]である。上に書いたアルゴリズムの場合、k回調べることをしなくて良いので、こっちのが早いと思うが、確かめる術がない。あと、解答を読んでいて思ったが、自分のアルゴリズムはlimit配列をまるごとdp配列に埋めているが、該当する株の残量だけ、つまりlimit[stock]だけ渡していけば良い。注目している株を買う数量を選ぶときに、他の株の残量は関係ないので。

以上、Problem Setを解き終わった。講義の課題としてナメてかかっていて、たくさん間違えることも多くて難しかった。 MITの講義のレベルはさすがに高いという感じ。まだざっと一周しただけなので、解き直しをしっかりやりたい。（解き直ししたら過去の記事にも追記します）

2019-12-29

CS6.006 Problem Set 6を解く

CS 6.006 Problem Set

問題はこちら意訳が間違っていたらご指摘ください。

6-1

Renbookという架空の(Facebookのパクリ)webサイトの友達ランク計算の話。

$ER(u, v)\in[0, 1$ ]はuがvに興味を持った度合いを表す。
ユーザ同士の関係は有向グラフによって表される。友達同士はエッジで結ばれている。
「自分( $u_0$ とする)」と、「自分の友達( $u_1$ )の友達( $u_2$ )の...友達( $u_k$ )」との関連度の強さ(教材中ではstrngthと呼ばれている)は、 $S(p)$ で表される。（計算式は教材参照）
上の例で、 $u_0$ と $u_k$ について、 $k$ はvaguenessと呼ばれる。(k-1回友達を挟むことで $u_k$ にたどり着けるというイメージ)

また、

V: ユーザ数
E: 友達ペアの数(エッジの数)

とする。

このような状況において、ユーザ $s$ について、vaguenessが $k$ 以下である全てのユーザの関連度(strength)の中で、最も高いものを $O(kE+V)$ で計算するプログラムを記述せよ、という問題。

幅優先探索をすればよいのでは？自分の考えたpseudo-codeを書く。

def find_highest_strength(user = s、k):
  queue = []
  answer = 0
  seen = set()
  queue.append((user, 1, 0))
  while queue: 
    cur_user, strength, vagueness = queue.pop(0) # (1)
    seen.add(cur_user)
    if vagueness > k:
      break
    friends = get_friends(cur_user)
    for friend in friends: # (2)
      if friend in seen:
        continue
      new_strength = strength * ER(cur_user, friend)
      new_vagueness = vagueness + 1
      answer = max(answer, new_vagueness)
      queue.append((friend, new_strength, new_vagueness))

一見してO(1)で終わらなそうな箇所は(1), (2)である。 (1)はpythonのdequeueを使えばO(1)でできるので、コードを改良することは簡単である。 (pythonのリストの先頭を削除すると、先頭より後ろの要素を全て一つ前にずらす処理が行われるため、O(N)かかる(N:リストの長さ)ので、それを回避するためのdequeueというライブラリがある。)

(2)は各友達に対してループを回すので、cur_userのもつ友達の数だけループが実行される。トータルでは全ての友達の数だけループが実行されるので、 $O(E+V)$ の実行時間がかかる。 $O(kE+V)$ としている理由がわからない。。。

解答

全然違った。解答pdfからのスクショ。以下のような場合で、BがAより先に探索された場合、Aの距離は(1ではなく)2としてカウントされてしまい、 $k=2$ としたときに、tが拾えなくなる可能性がある。 f:id:hisyatokaku:20191216122501p:plain

ポイントは、startからendまでのコストだけでなく、pathの長さ(何本の辺を渡ったか)もk以下であるという制約を気にする必要がある。

どうすれば良いかというと、 - ベルマンフォードのイテレーション(iterとする)を|V|-1回の代わりにk回まわす。 - ベルマンフォードの更新式(d[v] = d[u] + w(u, v)のところ)で、前回のiterの値のみを使う。

二点目について詳しく言うと、i番目のiterで、例えばe1, e2, ..., eMという順で更新するとする。e4を更新するときに、i番目のe1, e2, e3の更新の結果ではなく、i-1番目のe1, e2, e3の更新の結果を使う必要があるということ。こうしないと、長さがk以上の解が見つかってしまうらしい。(解答PDF参照)

6-2

(a)

ライブラリの依存性解決の問題。ライブラリの数が全部でVだけあり、それぞれがどれか別のライブラリに依存しており、そのような依存関係がEだけあるとする。 $O(V+E)$ でどのような順番でライブラリを入れていけば良いかを答える。

問題文が示す通り、循環依存はないので、DAGである。つまり閉路がない有向グラフ。これはトポロジカルソートできるので、トポロジカルソートすると、末尾のノードが最初に依存されているノードになるので、末尾からインストールしていけばよい。

(b)

上の問題において、V個あるライブラリのうち(V-P)個がすでにインストールされている場合、 $O(P+PD)$ でライブラリのインストール順を答えろという問題。ここで、一つのライブラリは最大でもD個のライブラリにのみ依存しているとする。トポロジカルソートは、あるノードについて子供がすべて探索済みになったらそのノードをソート済みリストに追加するという考えで行えるため、深さ優先探索を行う。 pythonコードは以下。

L = [] #ソート済みリスト
visited = set()
def topological_sort(lib):
  depends = get_dependency(lib)
  visited.add(lib)
  for dep in depends: # 高々D回のループ
    if dep in visited:
      continue
    topological_sort(dep)
  L = [lib] + L

for lib in libraries:
  if installed(lib):
    continue # V-P回実行される。
  topological_sort(lib) # この時点でlibの子供は再帰的に探索し終わっているはずなので、このタイミングでソート済みリストに加えれば良い。P回実行される。

時間計算量について。 - 全てのノードを見る必要があるので、topological_sortは最大でP回実行される。 - 全てのエッジを見る必要があるので、topological_sortの中にある高々D回のループはP回実行されうる。よって時間は $O(PD)$ かかる。

以上から $O(P + PD)$

補足：O(P+PD) = O(PD)じゃないか？と思ったが、例えば実はDがゼロだったときを考えるとよい。依存関係が全くない状況だが、全てのノードについて依存関係を調べなくてはいけないので、topological_sort()内のvisited.add()部分のみが実行される。このとき、O(PD)にD=0を代入するとO(0)になってしまうので間違い。

解答

自分の回答では、depにinstallされているものがあった場合も探索してしまうので間違いな気がする。解答例の計算量がP+PDとなる理由がよくわからない。。。

6-3

2×2のルービックキューブを深さ優先探索(BFS)で解く問題。 startの状態とendの状態を受け取り、startからendに到るまでの最短道筋を返す。

Speeding Up Dijkstraにも紹介されているように、startから素直に幅優先していくのではなく、startとendの両方から交互に幅優先探索していくという実装が必要。

理由：

ルービックキューブは一つの盤面に対し6通りの動かし方がある
→ $i$ 回動かしたあとの状態が[tex:6ⁱ]通りある。
→ 2×2のルービックキューブは最大で14回で揃えられる（らしい）ため、最大で[tex:6¹⁴=78,364,164,096]、つまりだいたい[tex:10⁹]通りの状態数がある。

これらを全部探索するのは時間がかかるが、終わりの状態に注目すると、終わりの状態の一個前の状態は $6$ 通り。i個前の状態は[tex:6ⁱ]通りである。

つまり、始まりと終わりそれぞれの方向から探索していくと、最悪でも、始まりから7回動かしたあたりで、終わりから7回動かした状態と合流する。合流した状態を介してstartからendまで一本のルートがつながるので、そのルートが答えである。このとき、[tex:6⁷ = 279,936]、だいたい[tex:10⁵]なので、探索する状態は10000分の1で済む。

これを実装すればよい。普通のBFSでは、

visited: 訪れた状態を覚えておく変数。
queue: まだ訪れてなくて、次に訪れるべき状態を入れるキュー。
state: queueにつっこむ中身。盤面はもちろん、１つ前の盤面からの動きを保持する必要がある。

が必要。最初の思考では、

forward_visited
backward_visited
forward_queue
backward_queue
state

が必要だと思ったが、queue = [(start_state), (end_state)]として前からの状態と後ろからの状態を交互に入れれば、queueは一つで済む。また、難しかったのは、前後それぞれ7回ずつ探索して答えがみつからなかったら、探索を打ち切るということ。解答の実装では、以下のように、Noneをappendして、i回動かした状態とi+1回動かした状態の間に区切りをいれている。

for i in range(7)
  queue = [(start_state), (end_state), None]
  while True:
    state = queue.popleft()
    if not state:
      queue.append(None)
      break
   else:
      ...探索部分...

また、余談だが、aがNoneかどうか調べる時は、a==Noneよりa is Noneを使う。'=='は__eq__メソッドにより書き換え可能なので、人が書いたコードにバグがあった場合、意図せぬ結果となる。isはオブジェクトが一致するかどうか比較しているので、唯一のオブジェクトであるNoneに対して比較することができる。

6-4

ダイクストラ法を実装する。ヘルパ関数が用意されているのでそれを活用すればいいのだが、うまくできなかった。結局解答を見た。

総じて、あまりできなかったので解き直す必要あり。

2019-11-30

Atcoder Educational DP Contest M Candies を解く（解けなかった）

CS6.006で習ったことだし、DPに強くなりたい。

問題は以下。 atcoder.jp

状態遷移図を書く。
遷移図
一つのノードから分岐する全てのノードを網羅できるようなサブ問題を考える。ここでは、根ノードとそこからわかれる二つのノードを網羅する例を考えている。

3.境界条件も考える。 f:id:hisyatokaku:20191130161244j:plain

4.定式化する。 f:id:hisyatokaku:20191130161246j:plain

5.普通は漸化式ができれば万歳なのだが、今回はO(NK²)で間に合わないので、式を簡略化する。 f:id:hisyatokaku:20191130161822j:plain

アとア'、ウとウ’は同じなので、以下のように簡略化できる。 f:id:hisyatokaku:20191130161255j:plain

6.for文の回し方を考える。 f:id:hisyatokaku:20191130162622j:plain

iは大きい方から小さい方向(Nから0) kは小さい方から大きい方向(0からK)へ回す必要がある。

実際に書いたコードがこれ。サンプルケースは全て通るが、ジャッジに通らない。よくわからないので保留。

#include "bits/stdc++.h"
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
#define MOD 1000000007
using namespace std;

int main(){
    int N, K;
    cin >> N >> K;
    int a[101];
    rep(i, 0, N) cin >> a[i];
    int** dp = new int*[102];
    rep(i, 0, 102){
        dp[i] = new int[100001];
    }
    rep(k, 1, 100001) dp[N][k] = 0;
    rep(i, 0, 102) dp[i][0] = 1;

    for(int k=0; k<=K; k++){
        for(int i=N; i>=0; i--){
            if(k - a[i] < 0){
                dp[i][k+1] = (dp[i][k] + dp[i+1][k+1]) % MOD;
            } else{
                dp[i][k+1] = (dp[i][k] + dp[i+1][k+1] - dp[i+1][k-a[i]])%MOD;
            }
        }
    }

    cout << dp[0][K] << endl;
    rep(i, 0, 102) delete[] dp[i];
    delete[] dp;
    return 0;
}

2019-11-23

CS 6.006 Lecture 21 DP III: Parenthesization, Edit Distance, Knapsack を見る

CS 6.006 Lecture

わかったこと

文字列系のDPでよく使われるsub-problem

prefix
suffix
substring

当然といわれれば当然。prefixとsuffixをどちらも使いそうな時はつまりsubstringである。

pseudo polynomial

ナップザック問題：

ナップザックに、重さ $w_i$ 、価値 $v_i$ の品物 $i$ を入れるか入れないか選ぶ。品物が全部でN個、ナップザックに入れられる重さは最大Wまでのとき、価値の最大値は？

という問題。重さをSとして、以下のような漸化式を使って解く場合を考える。

$DP(i, S) = max(DP(i+1, S), DP(i+1, S-w_i ) + v_i)$

時間計算量は、 $O(NS)$ である。これは、(inputに関して)polynomial-timeではない。 Sが非常に大きい場合があるからである。

講義では、「SがWordに収まらない場合」と表現されている。 Wordとは、複数のバイトをまとめたデータ単位である。コンピュータの実装によって異なるらしいが、1ワード = 2バイト(= 16ビット)だろうか？つまり、-2¹⁵から2¹⁵ - 1までの数である。(smallint)

SがWordに収まらない場合、入力のサイズはO(nlogS)であるらしい。 S = exp(logS)なので、入力に関して指数時間かかってしまう。よってこのときはpolynomial-timeではないらしい。入力のサイズがO(nlogS)である理由がよくわからないので調べる必要がある。

2019-11-04

CS 6.006 を見る

CS 6.006 Lecture

ふと、まとまった時間でアルゴリズムを学び直したいと思った。

いつ転職しても(させられても)いいように。

MITのCS 6.006という講座がある。2011年の秋学期にMITで行われたアルゴリズムの授業であり、ほぼ全てのリソースが無料で公開されている。 G社に内定した友人からオススメされたので、良いものだと思う。基本的に全部英語だが、字幕がついているので読み書きができれば進めていけると思う。

講義ページ

主にLecture + Recitation + Assignments + Quizからなり、基礎的なアルゴリズムとデータ構造（ソート、ハッシュ表、深さ・幅優先探索, 動的計画法）の講義が行われる。

Lecture: 1時間、教授がアルゴリズムについて講義する。全24回。
Recitation: 1時間で、TAと思われる人がLectureで説明しきれなかったところや、学生がわからなかったところを解説する。全24回。
Assignments: Problem Setと呼ばれる問題群を解く。要は課題。全8回。
Quiz: 試験。全2回？

教授陣の解説はわかりやすく、プログラミング課題も答えも用意されており、これだけのクオリティのものが無料で公開されているのは大変貴重だと思う。暇な時にLecture, Recitation, Assignmentsを解いて感想を載せていきます。

Lecture, Assignmentsの動画は公式ページで見てもいいけど、youtubeで見た方が早送り・巻き戻しなど使い勝手が良い。

2019-11-04

CS6.006 Problem Set 5を解く

CS 6.006 Problem Set

問題はこちら意訳が間違っていたらご指摘ください。

フォーマットの説明

問題文

思考方法→答え

の順で書いています。

Problem 5-1

base = 256、つまり256進数で表された整数の計算をするプログラムについて。 base = 256なので、我々が普段使う10種類の0-9の文字だけでなく、"#"とか"$"とか含む256種類の文字を使って数を表すことに注意。我々の世界の足し算は10進数なので、例えば425+43 = ?みたいな足し算が普通だが、 256進数の場合は5#*&2 + 6S1$); = ?みたいなものが定義できる。いかにも宇宙人の足し算のようなイメージ（だと自分は思う）だが、彼らが256進数を使っているだけと思えばこれは大したことはない。

まずはA+Bについて。問題文中のアルゴリズムに各行の計算量をつけたものを下に載せる。

ADD(A, B, N)
  C = ZERO(N+1)...O(1)
  carry = 0...O(1)
  for i=1 to N...O(N)
    digit = WORD(A[i]) + WORD(B[i]) + WORD(carry)...O(1)
    C[i] = digit % 256...O(1)
    carry = digit / 256...O(1)
  C[N+1] = carry...O(1)
  return C...O(1)

(a) ADD の time-complexityは?

$\Theta(N)$ →正解。

(b) ADDのoutputのsizeは?

$\Theta(N)$ →正解。

(c) ADD’s output size suggests an easy lower bound for the subroutine. Does the running time of ADD match this lower bound?

(b)より、outputのsizeはO(N)で、少なくともNのsubroutineがあるといえる。(for文のループ1回をsubroutineと考えたらいえる)よって、1. Yes→正解。

次はA・Bの掛け算のプログラムについて。

MULTIPLY(A, B, N)
  C=ZERO(2N) ...O(1)
  for i= 1 to N ...O(N)
  carry=0 ...O(1)
    for j= 1 to N...O(N)
      digit=A[i]·B[j] +WORD(C[i+j−1]) +WORD(carry)...O(A[i]・B[j])
      C[i+j−1] =LSB(digit)...O(1)
      carry=MSB(digit)...O(1)
    C[i+N] =carry...O(1)
  return C

(d) MULTIPLYのtime-complexityは?

$\Theta(N^{2})$ →正解。

(e) MULTIPLYのoutputのサイズは?

$\Theta(N)$ →正解。

(f) MULTIPLY’s output size suggests an easy lower bound for the subroutine.Does the running time of MULTIPLYmatch this lower bound?

(c)とちがって、サイズとtime-complexityが一致していないので、2.No→正解。

次はA / BとA%Bを同時に行うプログラムについて。

DIVMOD(A, B, N)
  Q = ZERO(N) ...O(1)
  R = COPY(A, N) ...O(N)
  S0 = COPY(B, N) ...O(N)
  i = 0 ...O(N)
  repeat ...O(N)
    i = i + 1 ... O(1)
    Si = ADD(Si-1, Si-1, N) ...O(1)
  until Si[N+1] > 0 or CMP(Si, A, N) == GREATER ...O(N)
  for j = i - 1 downto 0 ...O(N)
    Q = ADD(Q, Q, N) ...O(1)
    if CMP(R, Sj, N) != SMALLER ...O(N)
      R = SUBTRACT(R, Sj, N) ...O(1)
      Q[0] = Q[0] || 1 ...O(1)
  return (Q, R)

ざっと何をやっているかについて考える。まず、前提知識としてビットシフトが必要。説明すると以下のようになります。

ビットシフトとは、数を左または右にずらす操作。

左ビットシフトは、101010という数を、1010100にする操作。

右ビットシフトは、101010という数を、0101010にする操作。

左ビットシフトは数を2倍することに相当し、右ビットシフトは数を2で割ることに相当する。(17とかを2進数に直してビットシフトして10進数に直して確認すればわかります)

さて、DIVMODについて。

DIVMOD(A, B, N)...Aは割られる数、Bは割る数
  Q = ZERO(N) ...商を入れる変数
  R = COPY(A, N) ...余りを入れる変数
  S0 = COPY(B, N) ...S_iはB*(2^i)つまりBをi回左にビットシフトした数
  i = 0 
  repeat ...O(N)
    i = i + 1 
    Si = ADD(Si-1, Si-1, N) ...S_iを2倍している。つまりS_iを１回左にビットシフトしている
  until Si[N+1] > 0 or CMP(Si, A, N) == GREATER ...S_iがAより大きくなった時点でrepeat以下を止める
  // ここで例えばi=3でrepeatから抜け出したとすると、Aは、(Bを2回ビットシフトした数)で割れるが、(Bを3回ビットシフトした数)では割れない、ということになる
  for j = i - 1 downto 0 ...商を計算する。
    Q = ADD(Q, Q, N) ...Qを2倍している。つまりQを左にビットシフトする。
    if CMP(R, Sj, N) != SMALLER 
      R = SUBTRACT(R, Sj, N) ... R が S_jより大きいなら、RからS_jを引く。
      Q[0] = Q[0] || 1 ...RからS-jを引いた時にQの最下位ビット(下一桁)を1にする。
  return (Q, R)

(g) CMP(A, B, N)はAとBの大きさを比較してGREATER, SAMLLER, EQUALを返す。CMPが最適な場合のtime-complexityは?

ADD(A, -B)の結果を比べると考えれば、ADDの計算量に依るので、

$\Theta(N)$ →正解。

(h) SUBTRACT(A, B, N) はA-Bを計算する。最適な場合のtime-complexitは？

上と同様に、

$\Theta(N)$ →正解。

(i) DIVMODのtime-complexityは？

CMPがN回、iは最大でN回行われるので、

[tex:\Theta(N²)]→正解。

次は、Newton法を使ってより効率よく割り算を計算するDIVについて。（DIVは前の問で述べたサブルーチンに基づいているらしいが、どのサブルーチンなのかわからない。一問前に出てきたDIVMODを使うとその時点でNewton法ではなくなるし。。。）

(j) DIVはMULTIPLYを何回呼ぶ？

わからない。→Lecture note 12に載っているNewton法をもとに答えれば良い。

(k) MODのtime-complexityは？

わからない。→同上。英語の読解力がなかった。

次は、 B^E mod M

を計算するアルゴリズムについて。入力はN桁。

POWMOD(B, E, M, N)
  R=ONE(N)//result
  X=COPY(B, N)//multiplier
  for i= 1 to N ...O(N)
    mask= 1 ...O(1)
    for bit = 1 to 8 ...O(1)
    if E[i] & mask! =0 ...O(1)
      R=MOD(MULTIPLY(R, X, N), M,2N) ...O(N^2)
      X=MOD(MULTIPLY(X, X, N), M,2N) ...O(N^2)
      mask=LSB(mask·2) ...O(1)
      return R

(l) POWMODのtime-complexityは？

$\Theta(N^{3})$ →正解。

ここで、MULTIPLYを、karatsubaアルゴリズムで書き換える。 Karatsubaは、N桁同士の掛け算を $O(Nlog_{2}{3})$ で行える。

(m) karatsubaのtime-complexityは?

$\Theta(N^{log_{2}{3}})$ →正解。

(n) karatsubaを使った場合のMODは？ MODは、 $A-B(A / B)$ で計算できるので、karatsubaによるmultiplyと同じ計算量でできる。

$\Theta(N^{log_{2}{3}})$ →正解。

(o) karatsubaを使った場合のPOWMODのtime-complexityは？

$\Theta(N*N^{log_{2}{3}})$

= $\Theta(N^{log_{2}{6}})$

→正解。

(p) Aのk乗根の整数部分を、二分探索を使って求める擬似コードを書け。time-complexityはN^{2 + log3}である。

今までのPOWMODとか関数を使うのかなと予想し、考えてみる。

$\sqrt[K]{A}$ $\leq$ $x$ < $\sqrt[K]{A}+1$

を満たす $x$ が求まれば、 $x$ の整数部分が答えである。

これらをK乗すると、

$A$ $\leq$ $x^{K}$ < $(\sqrt[K]{A} + 1)^{K}$

が得られる。だから、これを満たした時点で終了するようなwhileループを書いて二分探索を行えばよい？実際には、上限の $(\sqrt[K]{A} + 1)^{K}$ はAのK乗根を知らないと計算できないので、 $A+1$ を上限として抑えればよい。通常の二分探索のコードをアレンジしたものが以下。

left = 0
right = A + 1
middle = left + (right - left) / 2
while ( abs(POW(middle, K) - A) < 1 ){
  if ( POW(middle, K) < A ){
    left = middle
  }
  else {
    right = middle
  }
  middle = left +(right - left) / 2
}

time-complexityは、 whileループがlog(N)回実行され、その中でPOW(middle, K)は、先ほどのPOWDIVを使うとして

$\Theta(N^{log_{2}{6}})$

の時間がかかるので、

$\Theta(log{N}*N^{log_{2}{6}})$

が答え？？だがこれは問題設定に合わない。諦める。→

答えの概要：[tex:2ⁱ]のK乗がAを超えるような最小の $i$ を計算し、 $j=i-1$ から $0$ までiterateし、[tex:R + 2^j]のK乗がAを超えない場合のみ[tex:R=R+2^j]へとRを更新する。こうしていくと、RはAのK乗根の直前のintegerに近づいていく。 2のi乗を足していく操作をすることで、ビットシフトとbitwise-ORだけで足し算が実現できるのでこちらの方が早い。そのうち詳しく記事にしたい。

Problem 5-2

次は、RSA暗号の問題。文中から読み取れるRSA暗号の仕組みをまとめると以下のようになる。数字eとして、65537を選ぶのがよくあるらしい。(そこそこ大きくて素数だから？)

f:id:hisyatokaku:20191103145949p:plain — 自分の鍵を公開する様子

f:id:hisyatokaku:20191103150034p:plain — サーバがユーザからもらった鍵を利用して安全に数字を伝える様子

(a) 復号の部分の計算、つまりe^d mod mのtime-complexityは?

先ほどのPOWMODをそのまま使えば良い。ので、

$\Theta(N^{log_{2}{6}})$ →正解。

次に、RSAの応用例の話。問題設定は、自分がKeg standをしている写真を暗号化して送りたい状況。

Keg standの例。狂っている。 www.google.com

効率の悪い方法の紹介から始まる。これは、画像をN-1バイトずつに切り分けて、(端っこはN-1バイトにならなかったら、N-1バイトになるまで0をつける) それぞれのブロックをRSA暗号で暗号化する。画像を青で表すと以下のようなイメージ。

f:id:hisyatokaku:20191103151005p:plain — 問題で紹介されている、非効率な暗号化の方法

(b) R×Cの画像をブロックにわけて暗号化する。RSA暗号化の関数をE(n)とすると、これは何回呼ばれるか？

問題文から、画像のバイト数は全部で、3 × R × Cバイト(3はRGBそれぞれでの数字を保管する分)。 3×Cの画像領域をN-1バイトのブロックに切り分ける操作をR回行うので、できるブロックの数は、

$RC/(N-1)$

Big-O記法では定数は無視するので、

$RC/N$ が答え。→正解。

(c) (b)のように暗号化した画像を復号するtime-complexityは？

復号には、POWMODを呼ぶ必要がある。これは、(a)より計算量がわかっている。このPOWMODはブロックの数だけ呼ばれるので、

$\Theta(\frac{RC}{N}N^{log_{2}{6}})$

つまり、

$\Theta(RCN^{log_{2}{3}})$ →正解。

(d) RSA暗号で暗号化されない数をfixed pointと呼ぶ。つまり、E(n) = n mod mとなる数nのことである。以下の数はfixed pointか？：0, 1, 2, 3, m-1, m-2

E(n) = n^e mod m = n mod mとなる数がfixed pointである。0, 1はe乗されても結果が変わらないのでmodも変わらない。2, 3, m-1, m-2は変わる。→

$m-1 \equiv -1$ mod mで、[tex:(-1)^e = -1]（eは奇数）であるので、0, 1, m-1が正解。

(e) RSA暗号の弱点を表すものとして正しい式を以下から選べ。

mは素数の積であればよいので m = 3 * 5 = 15として
eは(3-1)*(5-1) = 8と互いに素であればよいのでe=3として
nはなんでもよいのでn=2として

一個一個代入して確かめれば良い。反例があれば正しくないといえる。

$E(-n)\equiv -E(n) mod m$ → 左辺：(-2)³ mod 15 = -8 mod 15 = 7, 右辺：-(2³) mod 15 = 7 なので一致。

証明： f:id:hisyatokaku:20191103162144j:plain →正解。

$E(n_1)+E(n_2) \equiv E(n_1 + n_2) mod m$ → n_1, n_2を1, 2として、左辺：(E(1) + E(2)) mod 15 = 9 mod 15 = 9, 右辺：E(1 + 2) mod 15 = 27 mod 15 = 12なので不一致。 →正解。
$E(n_1)-E(n_2) \equiv E(n_1 - n_2) mod m$ → n_1, n_2を2, 1として、左辺：(E(2) - E(1)) mod 15 = 7 mod 15 = 7, 右辺：E(2-1) mod 15 = 1 mod 15 = 1なので不一致。 →正解。
$E(n_1)×E(n_2) \equiv E(n_1×n_2) mod m$ → n_1, n_2を1, 2として、左辺：(E(1) × E(2)) mod 15 = 8 mod 15 = 8, 右辺：E(1×2) mod 15 = 8 mod 15 = 8なので一致。

証明： f:id:hisyatokaku:20191103162202j:plain →正解。

$E(n_1)^{n_2} \equiv E(n_1^{n_2}) mod m$ → n_1, n_2を2,3として、左辺：E(2)³ mod 15 = 2^3e mod 15= 512 mod 15 = 2, 右辺：E(2³) mod 15 = 8^e mod 15 = 2なので一致。

証明： f:id:hisyatokaku:20191103162217j:plain →正解。

次に、RSAの応用例について。会社Aは、新製品ができる日より前は、NOというメッセージを暗号化し、会社Bに毎日伝えつづけ、新製品ができたら、YESというメッセージを暗号化し、会社Bに伝える。しかしこれには欠点があり、他者が暗号を解読できなくても、NOというメッセージからYESというメッセージに変わったことだけはわかるので、新製品ができた事実がバレる可能性があるというもの。(なお、暗号化は会社Bのe, mを使って行われるものとする。)

(f) この解決策として有効なものを以下から選べ。

一定の長いメッセージを送りたいメッセージの最後尾に追加し、メッセージをとても長くする。→ 毎日同じメッセージを送ることに変わりないので、有効でない。
固定長のrandomな数字をメッセージに貼り付ける。→毎回暗号化された値が変わるので良い。また、固定長の数字であれば、受信した側は復号した後に出てきたrandom数字を除去すればよいので、有効である。
会社Aは、自分のe, mを毎回生成し、毎回異なるe, mでメッセージを送る。復号に必要な鍵dは、会社Bのe, mを用いて送る。→ これも毎回暗号化された値が変わる。また、解読に必要な鍵自体も暗号化されているので、漏洩しても会社Bの復号用の鍵dがバレていなければ、解読される心配がない。よって有効である。
一般的でない文字エンコーディングで文字を変換する。→暗号化された値は毎回変わらないので、有効でない。
会社Aと会社Bが秘密の復号用の鍵をシェアする。→暗号化された値は毎回変わらないので、有効でない。

→正解。

Problem 5-3

プログラミング課題。省略。

2019-10-07

CS6.006 Problem Set 4を解く

CS 6.006 Problem Set

問題はこちら意訳が間違っていたらご指摘ください。

大問1

(a) 文字列の文字コードの和(のmod)をハッシュ値として使った場合、 $O(1)$ を達成できるか？
1. Yes, 文字列の長さに基づいて均等にハッシュ値がばらける
2. Yes, 文字列中の文字に基づいて均等にハッシュ値がばらける
3. No, 文字を並べ替えた場合は同じハッシュ値になってしまう
4. No, Simple uniform Hashingの前提にある、independence conditionが崩れてしまうから。

文字並び替えても同じハッシュ値になってしまうので、Simple Uniform Hashingになっていない。3と4が答え?

答え: 3

なんで4が答えに入っていないのか？文字コードによるハッシュ値は、すでにハッシュ表に入っている要素に関係なく文字によってのみ決まるので、independence conditionは保たれていると解釈できるからなのか？

(b)
1. Dynamic resizingはcorrectnessとperformanceを保証する。
2. Dynamic resizingはcorrectnessだけ保証する。
3. Collision resolutionはperformanceだけ保証する。
4. Dynamic resizingとCollision resolutionは二つ揃ってはじめてcorrectnessとperformanceを保証する。

correctnessとperformanceという、二つのプロパティについて。 - correctness: キーに対応する値を正しく返せるかどうか。 - performance: O(1)で値を返せるかどうか。

4が答え？

答え: 4

合ってた。

(c) $n$ 個の要素が入ったハッシュ表のサイズを $m$ から $m'$ に拡張する時にかかる最良計算量は？

$m+m'$ の表を一から作って、そこに $n$ 個の要素を移し替えるので、 $\Theta(m+m'+n) = \Theta(m' + n)$ (拡張時なので $m \lt m'$ としてよい)

7が答え？

答え: 7

合ってた。

(d) ハッシュ表の拡張はサイズを2倍にするように行うのが通常だが、定数倍増やすように行ってもよいかどうか？

n個の要素を一つづつ挿入し、ハッシュ表が埋まったら拡張するケースの、合計計算量を考える。 - 定数倍増やしていく場合( $m$ → $m+k$ ): [tex:O(n²)] - 倍づつにしていく場合( $m$ → $2m$ ): $O(n)$ という計算結果になった。

実際にはメモリを2倍とった時に無駄になるメモリの数は大したことがないので、倍ずつとったほうがよいのではないか。

答え: amortized costでO(n)かかる(つまり合計だと[tex:O(n²)])。これは、 $O(n)$ の操作を $O(1)$ ごとに行なっているからである。
また、2倍にしていく方法はビットシフトだけで数字が計算できるし、メモリサイズも2の倍数なので確保しやすいから、この方法が多く採られる。

大問2

(a)
1. dictionaryを作成し、大量の挿入があった後、検索の用途で主に使われる
2. dictionaryを作成し、対流の挿入があった後、検索のみに使われる
3. 挿入、削除、検索を同じぐらいの回数で行うために使われる
4. 挿入だけ、削除だけ、検索だけの操作の塊が代わる代わる行われるために使われる

Created once and then rarely changes.

とか

Many calls to __contains__() or has_key().

に当てはまるものは, 1だと思う。

答え: 1

合ってた。

(b) Membership Testingに特化したハッシュ表の実装をするなら、どれが適切か?
1. 開始時のサイズが大きく、足りなくなったら2倍に拡張する
2. 開始時のサイズが小さく、足りなくなったら2倍に拡張する
3. 開始時のサイズが大きく、足りなくなったら4倍に拡張する
4. 開始時のサイズが小さく、足りなくなったら4倍に拡張する

これは、

Any size of dict

と書いてあるし、サイズ関係ないのではと思ったが、クラスのメンバ関数などはいくつあるかわからないので、なるべく大きくとったほうがいいと思う。また、多くのメンバ関数がある可能性があるので、拡張の回数は少ないほうがいい。よって3が答え?

答え: 3

大問3

DNAを表す文字列([tex:O(10⁶)]の長さ)が二つ与えられた時、部分文字列の一致度合いを求める問題。 dnaseq.pyを編集する。

for文で実装すると、長いテキストをメモリに収める必要があり、非効率になってしまう。これを回避するために、next()で1文字ずつ読み込む文字列シーケンスのクラスが与えられており、これを使って実装する。

詳細は略。