1/28 - 壊れた計算機

ドラクエ6もう発売してたのか・・・

ゲノム Chapter 1

ゲノム・トランスクリプトーム・プロテオーム

論述式問題 1.4

「トランスクリプトーム」・「プロテオーム」という単語は包括的な意味合いを持つので、ゲノム発現を細胞全体を系として見て理解するときに便利だ。
この本の定義だと(P.5) 、トランスクリプトームはタンパク質をコードする遺伝子に由来を持つ必要があるので、ncRNAのうちゲノム発現を大きく左右する物がトランスクリプトームに含まれないかもしれない。

An Introduction to Algorithms / アルゴリズムイントロダクション Chapter 2

ソートアルゴリズム、計算量イントロダクション
教科書の配列のインデクスが1から始まることに気づいていなかったので、練習問題はインデクスが0からの配列を仮定して擬似コードや証明を書いてしまった

Exercise 2.1-1

(31 41 59 26 41 58)
...
(26 31 41 59 41 58)
(26 31 41 41 59 58)
(26 31 41 41 58 59)

Exercise 2.1-2

不等号を逆にする

Exercise 2.1-3

def LinearSearch (A v)
   loop for i from 0 below A.length
      if A[i] == v
         return i
   return nil

loop中A[0 .. i-1]にはvがない事を示せばよい

Exercise 2.1-4

def Add (A B)
   C <- MakeArray( A.length + 1 )
   carry <- 0
   loop for i from A.length - 1 to 0
      C[i+1] <- ( carry + A[i] + B[i] ) % 2
      carry <- ( carry + A[i] + B[i] ) / 2
   C[0] <- carry
   return C

Exercise 2.2-1

$\Theta(n^3)$

Exercise 2.2-2

def SelectionSort ( A )
   loop for i from 0 below A.length - 1
      min <- i
      loop for j from i below A.length
         if A[j] < A[min]
            min <- j
      swap( A i min )

iについてのloopは、A[0 .. i-1]が、「sort済み」 & 「A[i ..]のどの要素より小さい要素からなる」という性質を保つ
A.length-1までループすれば、A[0 .. A.length - 2]はA[A.length - 1]より小さい要素からなるのでAはソート済みとなる

Best	Worst
$\Theta(n^2)$	$\Theta(n^2)$

Exercise 2.2-3

Average	Worst
$n/2, \Theta(n)$	$n, \Theta(n)$

Exercise 2.2-4

ランダムな選び方をする。
ソートならボゴソート
探索なら当てずっぽ探索

Exercise 2.3-1

<3,41,52,26,38,57,9,49>
<3,41,52,26> <38,57,9,49>
<3,41> <52,26> <38,57> <9,49>
<3> <41> <52> <26> <38> <57> <9> <49>
<3,41> <26,52> <38,57> <9,49>
<3,26,41,52> <9,38,49,57>
<3,9,26,38,41,49,52,57>

Exercise 2.3-2

問題文の通りにやる

Exercise 2.3-3

$T(2^k) = n\lg n$
をkに関する帰納法で示す
$k=1 \Rightarrow T(2^k) = T(2) = 2 = 2\lg 2$
$T(2^k) = 2^k \lg 2^k = k 2^k \Rightarrow T(2^{k+1}) = 2T(2^k) + 2^{k+1} = 2k2^k + 2^k+1 = (k + 1)2^{k+1} = 2^{k+1} \lg 2^{k+1}$
示した。

Exercise 2.3-4

$T(n) = \Theta(1) \hspace{10} if \hspace{10} n = 1$
$T(n) = T(n-1) + \Theta(n) \hspace{10} if \hspace{10} n > 1$

Exercise 2.3-4

def BinarySearch (A v)
   def BinarySearchSub (min max)
      pivot <- ( min + max ) / 2
      if A[pivot] == v
         return pivot
      else if min >= max
         return nil
      else if A[pivot] < v
         return BinarySearchSub( pivot + 1, max )
      else if A[pivot] > v
         return BinarySearchSub( min, pivot + 1 )
   return BinarySearchSub( 0, A.length - 1 )

Exercise 2.3-6

できない　なぜならばインサートしたあと右側の配列を一つずらしてコピーする必要があり、それにO(n)だけかかるから

Exercise 2.3-7

loop for i from 0 below A.length
   if BinarySearch( A[i+1 ... A.length], x - A[i] )
      return true
return false

Problems 2-1

a 最悪k^2の計算をn/k回するので、計算量は $\Theta(k^2) * \Theta(\frac{n}{k}) = \Theta(nk)$
b 配列の長さを毎回kと比較し、kより短い場合はInsertionSortをし、kより長い場合はMergeSortをする
c $\lg n$
d 定数項を吟味して決める。

Problems 2-2

a 元の配列と要素が同じことを証明する
b A[j]はA[j ..]の最小値である。証明略
c A[1..i-1]はソート済みである。証明略
d $\Theta(n^2)$

Problems 2-3

a $\Theta(n)$
b 毎回 $x^n$ を計算すると $\Theta(n^2)$ になる
c $y = \sum^{n-(i+1)}_{k=0}a_{k+i+1}x^k \Rightarrow y^' = a_i + xy = a_i + x\sum^{n-(i+1)}_{k=0}a_{k+i+1}x^k = \sum^{n-i}_{k=0}a_{k+i}x^k$
d cより明らか

Problems 2-4

a (2,1) (3,1) (8,6) (8,1) (6,1)
b 逆にソートされた配列
c 配列をずらす長さの合計はinversionの数と等しくなるので、inversionの回数をmとおくと計算量は $\Theta(n) + \Theta(m)$ となる。
d 二つのリストをMergeするとき、右のリストから数を取るたびに左側のリストの長さを足してゆく。