[English/Japanese]

『はじめてのアルゴリズム』の補足ページ

Cover

本ページは

の補足ページです．

訂正表

現在わかっているミスは今のところ，以下のとおりです．

章
ページ
場所
間違い
訂正
 言い訳
発見者
発見日
はじめに
ii
5-6行目
 このセリフを最初に言ったのは，Paul Erdősではない． 最初に言ったのはAlfréd Rényi． ポール・エルデシュの英語版のWikipediaに 詳しく載っています．エルデシュが言ったとして引用されることが多いそうですが， 正しくはAlfréd Rényiが言ったそうです．
岡本吉央
2013年11月12日
はじめに
i
14-16行目
 2000倍×475000倍は約100億倍ではない． 正しくは約10億倍 単純な計算ミス．
大舘陽太
2017年10月06日
1章
5ページ
7行目
 書き込むいった 書き込むといった typo
飯野玲
2013年11月6日
1章
18ページ
アルゴリズム4
 if...then...else...end 初出なのに説明がない 説明を追加します： 行3から行7に書かれたif，then，else，endは合わせて if文と呼ばれる．形式としては， if（条件）then（条件が満たされたときに実行される命令文） else（条件が満たされないときに実行される命令文）endとい う形式で記述される．上記のアルゴリズムの場合は変数aの値が変数bの値よりも大きい場合は 変数aの値が出力され，それ以外の場合（a=bの場合も含めて）変数bの値が出力されることになる．
上原隆平
2013年9月24日
1章
20ページ
アルゴリズム5,6
 変数iとjの値がnとmまで 変数iとjの値がn-1とm-1まで typo
飯野玲
2013年11月6日
1章
42ページ
下から6行目
 N[i] N(i) typo
上原隆平
2015年8月31日
2章
48ページ
下から8行目
 すべての円盤を 3以外のすべての円盤を より明確に
飯野玲
2013年11月6日
2章
53ページ
図2.4
 解放 開放 本文に合わせて
飯野玲
2013年11月6日
2章
58ページ
16行目
 -0.118034… -0.61803… typo
飯野玲
2013年11月6日
3章
68ページ
下から4行目
 T(1) TB(1) typo
飯野玲
2013年11月12日
3章
82ページ
図中上から三つ目の配列の中
 8,9 18,29 typo
飯野玲
2013年11月12日
4章
96ページ
アルゴリズム26
 DFS-main DFS-main(A) typo
飯野玲
2013年11月12日
4章
96ページ
アルゴリズム26
 入力のデータi 不要 typo
飯野玲
2013年11月12日
4章
101ページ
図4.3
 図4.1(1)のグラフとは頂点のラベルが違うi 図4.1(1)のグラフとは違うグラフだと思って下さい 図の変更による齟齬 ;-)
飯野玲
2013年11月12日
4章
101ページ
最後の段落
 もちろんここで挙げたもう一つのアイデア，つまり深さ0の根の探索 のあとは，まず深さ1の頂点の探索をすべて終わらせるというアイデアも 間違いではない． 深さは探索によって決まるので，この説明はおかしい． 説明を変更します： もちろんここで挙げたもう一つのアイデア， つまり深さ0の根の探索のあとは，まず根に隣接する頂点を， 深さ1の頂点としてすべて探索するというアイデアも間違いではない．
上原隆平
2013年9月24日
4章
104ページ
図4.4
 図4.1(1)のグラフとは頂点のラベルが違うi 図4.1(1)のグラフとは違うグラフだと思って下さい 図の変更による齟齬 ;-)
飯野玲
2013年11月12日
4章
105ページ
アルゴリズム28
 BFS-main BFS-main(A) typo
飯野玲
2013年11月12日
4章
105ページ
アルゴリズム28
 入力のデータi 不要 typo
飯野玲
2013年11月12日
4章
113ページ
アルゴリズム30の4行目
 for j=1,...,di do for j=A[i,1],...,A[i,di] do 頂点iの隣接頂点を走査するときに，添字だけ動かしていた．要するにバグ．
上原隆平
2016年9月18日
4章
114ページ
アルゴリズム31の入力，3行目，4行目
 大文字の配列S[] 小文字の配列s[] 集合Sを表現するのに小文字の配列s[]を使っていたのに対する不統一．
上原隆平
2016年9月18日
5章
121ページ
アルゴリズム32の3行前
 サブルーチンの名前をQueenSub(i) サブルーチンの名前をQueenSub(B,i) パラメータが一つ欠落．
上原隆平
2016年9月18日
5章
131ページ
アルゴリズム35の2行目
 n=35 p=35 typo
上原隆平
2016年9月18日
8章
155ページ
アルゴリズム42
 S[t+1] S[t] 勘違い
武本和久
2016年4月14日
8章
164ページ
下から8行目
 中央の+ - typo
飯野玲
2013年11月6日
8章
171ページ
下から5行目
 距離k 距離k+1 typo
飯野玲
2013年11月12日

プログラム

本書で言及しているアルゴリズムは，一通り試しました．プログラムは gcc で書いてあります． 上原の作業環境はあまり一般的でなく，細かいプログラムを公開する予定は特にありません． 特にプログラミングについて，上原から助言できることはありません． もしどうしても疑問点などがある人は，個別に連絡下さい．以下， 特に入力が大変だったものを中心に公開しておきます．

騎士の巡回問題でk=6の場合
これはデータの整合性がなかなか合わなくて，データのデバッグに苦労したので公開しておきます． 6knight.c
騎士の巡回問題でk=8の場合
これはk=6の場合で苦労したので，確実に間違えるだろうと判断して， 下半分のデータは上半分のコピーを計算して，手間を半分にしました．詳細は本文を参考にして下さい． これもデータのデバッグが意外と面倒なので，そこを楽にするために公開しておきます． 8knight.c
Last modified: Sat Apr 25 23:26:41 JST 2015
by Ryuhei Uehara (uehara@jaist.ac.jp) 		Valid HTML 4.0!