計算とアルゴリズム 5.1～5.4

計算とアルゴリズム 4.2～4.3。慣らし計算量の意味で良いアルゴリズム。実用性は微妙な感じ。アッカーマン関数は良く分からない。 コルメンの日本語訳が欲しいがお金が無い。

計算とアルゴリズム 4.1。赤黒木は難しくはないけどパターンが多く複雑でお勉強が嫌になるタイプのやつだね。でもこういうの最初に考える人は賢いなぁ。

計算とアルゴリズム 3.4～3.6 土日に殆どできなかったので反省。

計算とアルゴリズム 3.2～3.3 特になし。

計算とアルゴリズム 2.1～3.1。マージソート、クイックソート、ラディックスソート、2分探索と2倍探索。 2.4のソーティングの計算量の下界について。 入力要素数をn、ソートに対応した2分決定木の深さをhとすると これより となり、Ω(nlogn)が示される。 さ…

計算とアルゴリズム テキスト1.4～1.5。1章の演習問題全て。再帰法とグラフ。 1.4.1で扱われているユークリッドの互除法の計算回数について調べた。 ラメの定理 a,b∈自然数(0を含む), a>b, mをbの桁数, nをユークリッドの互除法で余りを求めた回数とする。こ…

計算とアルゴリズム 1.1～1.3と演習問題1-8。計算量の話。基本。演習問題1-8は2SATがO(m+n)で解けることを示す問題。解答では最大独立集合を求める問題に帰着し、構成したグラフの特殊性から最大独立集合を求める問題はO(m+n)と言っている。しかし証明が載っ…