正誤表

伊藤大雄 著「データ構造とアルゴリズム（コンピュータサイエンス教科書シリーズ ２）」コロナ社，２０１７．

最終更新日: 2025.12.17

第２刷に以下の誤りが見つかっております。ご迷惑をおかけして申し訳ありません。

• P96 補題5.1の証明のL3:「ln」→「lg」
• 付録 P5 L↑3:「ln」→「lg」

初刷に以下の誤りが見つかっております。第２刷ではこれらは修正されております。

• 目次 P. x, 5.3.3: 「競合化」→「競合比」
• P8 定義1.2の次の行: 「g(n)) 」 →「g(n)」（２箇所）
• P12 L11: 「∨∨」 → 「∨」 （「¥lor ¥lor」→ 「¥lor」）
• P13 L↑6: 「多項式時間を」→「多項式時間アルゴリズムを」
• P14 L6: 「多項式（線形関数）」→「多項式（線形）関数」
• P15 脚注 L3: 「方積問題」→「倍積問題」
• P15 脚注 L3--4: 「５次方程式の解の公式の不存在性を」→「定規とコンパスを用いて求められる長さは二次以下の方程式の解の列として得られるものに限られることを」
• P16 L↑3: 「Πを」→「 I_Aを」（「＼Piを」→「 I_Aを」） <---- * 2025.08.28 修正 *
• P18 L3: 左側のΣの下の「i \in B」→「i \in B'」
• P18 定義1.6 L1: 「B ∈ P」→「B ∈ NP」 （「B ¥in P」→「B ¥in NP」）
• P18 定義1.6 L3: 「A ∈ P」→「A ∈ NP」 （「A ¥in P」→「A ¥in NP」
• P25 図2.7: ポインタ「top」の位置を$k$番目のデータ$a_k$の真下へ。
• P26 図2.9: ポインタ「front」の位置を3番目のデータ$a_1$の真下へ。
• P26 図2.9: ポインタ「rear」の位置を6番目のデータ$a_4$の真下へ。
• P27 L↑4: 「hight」→「height」
• P31 L 1: 「考量」→「考慮」
• P32 L 11: 「e_G(U,W):=|E_G(U,W)|は」→「E_G(U,V-U)は」
• P33 L ↑10: 「節点」→「頂点」
• P33 L ↑4: 「節点」→「頂点」
• P36 図2.17 (a): 辺が１本足りない。（右の上の頂点から下の左の頂点へ）
• P46 L6: 「W≧2」 → 「|W|≧2」
• P48 3.3.2 L1: 「MergeToOne」 → 「MergeTwoToOne」
• P48 3.3.2 L3: 「長さn/2^kの長さの列」 →「長さn/2^kの列」
• P49 L↑6: 「W≧2」 → 「|W|≧2」
• P78 L3: 「互いに疎な」 → 「互いに素な」
• P79 4.4.3の最後の文: 「Union命令は全体で ... O(logn)時間となる」→ 「したがって、すべての併合に要する計算時間はO(nlogn)時間となり、Union命令は全体で...あることを考え合わせると、１回当りの平均はO(logn)時間となる。」
• P89 L↑7: 「key(v)=r」→「key(v)=a」
• P89 L↑5: 「key(v)<r」→「key(v)<a」
• P89 L↑3: 「key(v)>r」→「key(v)>a」
  
• P102 L1: 「xをw'の右の子」→「xをwの右の子」 <---- * 2023.10.25 修正 *
• P102 L1: 「uをw'の左の子」→「uをwの左の子」
• P102 L3〜4: 「5.2.3項の二色木における削除」→「5.2.2項の二色木における挿入」
• P103 図5.18: 二つあるv_{k-1}のうち、上側のv_{k-1}をv_{k-2}に変更。  
• P111 L6: 「２回移転操作」→「２回回転操作」
• P113 L↑5: 「競合化」→「競合比」
• P117 5.4.2 L2: <4,2,3> →<8,4,2,3>
• P130 図3(a)の凡例: T^*の凡例が太点線と細点線となっているが、これを太点線と太実線に変更 <---- * 2025.01.07 修正 *
• P130 L↑6: 「され得て」→「されて」 <---- * 2023.10.25 修正 *
• P131 L13: 「ときにには」→「ときには」
• P140 L12: 「現在の」を削除。
• P141 L14: 「路長さ」→「路の長さ」
• P143 L↑12: 「N(w)」→「Γ(w)」（「N(w)」→「＼Gamma(w)」）
• P153 L14: 「本章末の」→「２章末の」
• P153 L↑4: 「graf」→「graph」
• P154 L1〜2: 「このグラフの頂点を隣接する頂点が」→「このグラフの頂点を、隣接する頂点が」
• P156 L3: 「V_1とV_2の間に」→「V_1に属する頂点の間およびV_2に属する頂点の間に」
• P157 L3: 「が、興味のある読者は文献16)を参照」を削除。<---- * 2025.08.29 修正 *
• P161: 7.1.4: 最初から４行: 「問題の入力として・・・（４行目の式まで）」の部分について、「は『性質』の定義と同様に、」の部分を「では」に変更した上で、P.161の１行目と２行目の間に移す。
• P168: 補題7.1の証明の最後からL↑5: 「２番目の」→「最初の」
• P168: 補題7.1の証明の最後からL↑2の式の右辺:　分子から「n^3」を取る。 <---- * 2023.10.25 修正 *
• P169: 補題7.2:  L1: 「整数」 → 「実数」
• P178 L6: 「連結成分を含む」 → 「連結成分が含む」
• P179 式(7.10): 「≧」 → 「≦」
• P181 定理7.11の２行目: 「無Hマイナーなグラフ」 → 「無HマイナーなグラフG」<---- * 2025.08.29 修正 *
• P182 L9: 「h^3」 → 「h^{3/2}」
• P182 「以上からつぎを得る。」の次の式の２行目と３行目: 「(3+√6)」 → 「(2+√6)」
• P182 「以上からつぎを得る。」の次の式の４行目: 「6」 → 「5」
• P182 L↑6とL↑3: 「49」 → 「25」 <---- * 2023.11.01 修正 *
• P182 L↑5: 「7」 → 「5」<---- * 2023.11.01 修正 *
• P185 L↑1: 「を実行すると、」 の次に「確率9/10以上で」を挿入。
• P188 procedure MinorFreeTest(G)の５行目: 「個選び」 → 「個の頂点を選び」
• P197 L1: 「平面グラフは本質的に」 → 「非平面グラフは本質的に」
• P198 L8: 「縮約何回か」 → 「縮約を何回か」
• P202 演習問題【１】: 「2^A = 2^n」→「|2^A| = 2^n」
• P212（奥付）: 「Hiroo Itoh」 → 「Hiro Ito」
• 付録 まえがき L10: 「競合化」→「競合比」
• 付録 P12 L4: 「任意のグラフG」 → 「任意の平面グラフG」
• 付録 P12 L↑9: 「G-{x}」 → 「G-{v}」
• 付録 P14 図A.3 (b): 頂点1と4の間に辺を付加。
• 付録 P20 L↑2: 「正則」→「ε正則」
• 付録 P21 L↑9: 「≦」→「…」<---- * 2025.08.29 修正 *
• 付録 P23 L↑11: 「Qが例外集合」→「Qにおいて、例外集合」
• 付録 P23 L↑11: 「k2^{k-1}個」→「2^{k-1}個」
• 付録 P23 L↑10: 「V'_0大きさ」→「V'_0の大きさ」
• 付録 P26「演習問題解答」 L4（２箇所）: 「問題」→「問題例」