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

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に書かれたifthenelseendは合わせて if文と呼ばれる.形式としては, if(条件)then(条件が満たされたときに実行される命令文) else(条件が満たされないときに実行される命令文)endとい う形式で記述される.上記のアルゴリズムの場合は変数aの値が変数bの値よりも大きい場合は 変数aの値が出力され,それ以外の場合(a=bの場合も含めて)変数bの値が出力されることになる.
上原隆平
2013年9月24日
1章
20ページ
アルゴリズム5,6
変数ijの値がnmまで 変数ijの値が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!