アルゴリズムイントロダクション
15.2.1 ノートに書いた
15.2.2
MATRIX-CHAIN-MULTIPLY(A,s,i,j)
if i=j
then return Ai
else X ← MATRIX-CHAIN-MULTIPLY(A,s,i,s[i,j])
Y ← MATRIX-CHAIN-MULTIPLY(A,s,s[i,j]+1,j)
return MATRIX-MULTIPLY(X,Y)
15.2.3
P(n)=ΣP(k)P(n-k)に対して最初と最後だけ取り出してP(n)>=P(1)P(n-1)+P(n-1)P(1)という関係式を作ればよい。あとは普通の置き換え法
15.2.4
i=n-l+1,k=l-1を利用。さらにm[i,j]を求めるときにはm[i,k]とm[k+1,j]の二つを参照する必要がある。以上からΣ(n-l+1)(l-1)*2を計算すればよい。
15.2.5
数学的帰納法により（）の数を帰納的に証明。
コンピュータの構成と設計
・性能を比べるなら同じプログラムでのCPU実行時間の比較
・CPI＝命令あたりの平均クロックサイクル数
・CPU時間＝（実行命令数）*（CPI）/（クロック周波数）