|
2005年01月13日
このページは、２００４年度のアルゴリズムの授業、およびテキストに関するページです。主に、テキストの修正情報などを掲載予定です。
「アルゴリズム入門」 修正情報
テキストの間違いを指摘してくれた学生諸君に謝意を表します。
P.10 下から２行目
「nに関する簡単な関数f(n)とp(n)」 → 「nに関する簡単な関数f(n)とg(n)」に修正
P.12
「f(n)=a+nb+(n-1)(c+a)+d=(a+b+c)n-c+d」 →
「f(n)=a+(n-1)(b+c+a)+d=(a+b+c)n-b-c+d」に修正
P.44 表2.13
頂点に接続する辺の表で、要素番号2で辺番号3の欄を「3」から「2」に修正
P.45 表2.14
頂点に接続する辺の表で、要素番号3で辺番号2の欄に「2」を加える
P.46 2.4節１行目
「回路（ループ）のなものを、木という」→「回路（ループ）のないものを、木という」
P.69 アルゴリズム4.2
手続き3.1で、c = [ l + r ] / 2 を c = [ (l + r) /2 ] に修正。（ただし、[ ] は、floorを表すものとする）
P.69 図4.4
「キー値と要素番号cの値を比較し、同じであれば．．．」という説明のところで、「r=c」を「r=c-1」に、「l=c」を「l=c+1」に修正
P.72 図4.8
前の部分から推測できるかもしれませんが、この図は「13で割った余り」を用いて作成されたものです。
P.80 Hanoi(2,i,j)
一番下の行
「move(k,i); // ピンkの円盤をピンiに移す」
を、
「move(k,j); // ピンkの円盤をピンjに移す」
に修正。
P.94
「アルゴリズム 6.4 クイックソート」のしたから３行目
「5.4 pl <= prであれば4.1へ、そうでなければ6.へ」を、
「5.4 pl <=
prであれば5.1へ、そうでなければ5.へ」 に修正
P.105
アルゴリズム７．１の注）
「深さ優先の探索とおなり、入れ物Bにキューを」→「深さ優先の探索となり、入れ物Aにキューを」
P.106 図７．３
「A（スタック）」 → 「Ａ（キュー）」に訂正
P.115 下から１行目
「iが3(=n-2)になるまで行う」 → 「iが2(=n-3)になるまで行う」に修正
P.116 アルゴリズム７．４
「3. i = 0,1,...,n-2に対して次の処理を行う」 → 「3. i = 0,1,...,n-3に対して次の処理を行う」に訂正
＃上の修正がなくても、アルゴリズムとしては正常に機能しますが、余分な処理が一つ加わってしまいます。
P.116 表７．３
i=0のときのd3を4から７に、d4を7から4に修正
i=1のときのd3を3から７に、d4を7から3に修正
i=2のときのSを{0,1,2,3}から{0,1,2,4}に、vを3から4に、d3を3から4に、d4を4から3に修正
i=3の行を削除。
テキストに関して気づいた点がありましたら、lecture@ylab.ka.cit.nihon-u.ac.jpまで連絡してください。
|
