プロフェッショナルデジタルスキル › Web参考書 › 第5章

アルゴリズム・プログラミング:数値表現と応用数学、データ構造、整列・探索・グラフのアルゴリズムと計算量

第5章 システムの開発・運用 / 節 3

シラバスのキーワード: 浮動小数点数半精度IEEE 754コサイン類似度待ち行列理論計算量(オーダ記法)連結リストB+木先行順2 分探索法ハッシュ表探索法動的計画法貪欲法ダイクストラ法ベルマンフォード法オーバーロード

中分類22 は、データ構造とアルゴリズムを選んで使うための知識で、情報理論、データ構造、アルゴリズム、プログラミングの四つの小分類から成ります。現行の応用情報の「基礎理論」と「アルゴリズムとプログラミング」をまとめた範囲で、AI に関わるコサイン類似度や半精度が加わりました。計算量の比較や、擬似言語のプログラムを追う計算問題が出ます。

この節の用語(小分類ごと)

情報理論

データ構造

アルゴリズム

プログラミング

試験で問われる観点

関連する節

この節の練習問題(16問)

答えを見る前に選んでから開いてください。同じ問題は章別演習でランダム出題されます。

  1. 問1
    2 個の変数 x1,x2 から成るデータの分散共分散行列を求めたところ,x1 の分散は 5,x2 の分散は 2,x1 と x2 の共分散は 2 であった。このデータに主成分分析を適用したときの,第 1 主成分の寄与率と,第 1 主成分の方向を表す固有ベクトルの組合せとして,適切なものはどれか。
    1. 1約 86%,(2, 1) の方向
    2. 2約 86%,(1, −2) の方向
    3. 3約 71%,(2, 1) の方向
    4. 4約 71%,(1, −2) の方向
    答えと解説

    正解: 1

    分散共分散行列の固有値 λ は,(5−λ)(2−λ)−2×2=0 すなわち λ²−7λ+6=0 から 6 と 1 である。各主成分の分散は対応する固有値に等しいので,第 1 主成分の寄与率は 6÷(6+1)≒86% となる。λ=6 の固有ベクトル (a, b) は,(5−6)a+2b=0 から a:b=2:1 であり,(2, 1) の方向になる。(1, −2) は小さい方の固有値 1 に対応する第 2 主成分の方向で,第 1 主成分と直交する。71% は共分散を無視して,x1 の分散 5 を分散の合計 7 で割った値である。

  2. 問2
    数値解析の手法のうち,オイラー法の説明として,最も適切なものはどれか。
    1. 1関数の値の符号が異なる 2 点を両端とする区間をとり,その中点での関数の値の符号を調べて,解を含む側の区間を残すことを繰り返し,方程式の解を求める。
    2. 2現在の近似値における関数の接線を求め,その接線と x 軸との交点を次の近似値とすることを繰り返して,方程式の解に近づけていく。
    3. 3微分方程式の初期値から出発し,現在の点における導関数の値に刻み幅を掛けた量を加えて次の点の値を求めることを繰り返し,解を近似する。
    4. 4積分する区間を偶数個の小区間に分け,隣り合う二つの小区間ごとに関数を 2 次式で近似して面積を求め,それらを合計して定積分の値を近似する。
    答えと解説

    正解: 3

    オイラー法は,常微分方程式 dy/dx=f(x, y) の初期値問題を解く最も基本的な数値解法で,刻み幅を h とすると y(n+1)=y(n)+h×f(x(n), y(n)) により次の点の値を順に求める。各点での傾きだけを用いるので,刻み幅を小さくするほど誤差は小さくなるが計算の回数が増える。符号の変わる区間を半分ずつ狭めるのは二分法,接線と x 軸の交点を次の近似値とするのはニュートン法であり,いずれも方程式の解を求める手法である。小区間ごとに 2 次式で近似して積分するのはシンプソン法である。

  3. 問3
    データ構造に関する記述のうち,適切でないものはどれか。
    1. 1連結リストは,挿入する位置の直前の要素を指す参照が得られていれば,後続の要素を移動せずに定数時間で挿入できるが,i 番目の要素を参照するには先頭から順にたどる必要がある。
    2. 2動的配列は,容量が不足したときに要素 1 個分だけ大きい領域を確保し直して全ての要素を写すので,末尾への要素の追加は,1 回当たり平均して定数時間で行える。
    3. 3単方向の環状リストで末尾の要素を指すポインタだけを保持すると,その次の要素が先頭になるので,先頭への挿入と末尾への追加とを,どちらも定数時間で行える。
    4. 42 次元配列を行優先で連続した領域に格納するとき,同じ行の要素を列の順に走査する方が,列ごとに行をまたいで走査するよりも参照先が連続し,キャッシュを効率よく使える。
    答えと解説

    正解: 2

    容量が不足するたびに要素 1 個分だけ拡張すると,追加のたびに全要素を写すことになり,n 個を追加するときの写しの総数は n の 2 乗に比例し,1 回当たり平均しても要素数に比例する時間がかかるので,記述は適切でない。容量を 2 倍にするなど一定の比率で拡張すれば,写しの総数が n に比例し,1 回当たり平均して定数時間になる。連結リストは参照の付替えだけで挿入できるが,位置を指定した参照は先頭からたどる。環状リストは末尾の次が先頭なので,末尾のポインタだけで両端を扱える。行優先の配列は同じ行の要素が隣り合って並ぶ。

  4. 問4
    始点 S から終点 T へ向かう有向グラフの各辺に,単位時間当たりに流せる量の上限(容量)が次のとおり定められている。S から T への最大流量と,容量を 1 だけ増やすと最大流量が増える辺の組合せとして,適切なものはどれか。 S→A:5,S→B:5,A→B:1,A→C:3,B→C:2,B→T:3,C→T:6
    1. 1最大流量 8,辺 B→C
    2. 2最大流量 8,辺 C→T
    3. 3最大流量 9,辺 B→C
    4. 4最大流量 9,辺 C→T
    答えと解説

    正解: 1

    S→A→C→T に 3,S→A→B→T に 1,S→B→C→T に 2,S→B→T に 2 を流すと合計 8 になる。頂点を {S,A,B} とそれ以外とに分けると,切られる辺は A→C,B→C,B→T で容量の和は 3+2+3=8 なので,最大流量最小カット定理から 8 が最大である。容量の和が 8 のカットはこれだけなので,その辺である B→C(A→C,B→T も同じ)の容量を増やすと最大流量は 9 になるが,カットに含まれない C→T を増やしても 8 のままである。9 は,S から出る辺の容量の和 10 と T に入る辺の容量の和 9 の小さい方を最大流量とした値である。

  5. 問5
    重み付き無向グラフの最小全域木を求めるクラスカル法の説明として,最も適切なものはどれか。
    1. 1任意の 1 頂点から始め,作成中の木に含まれる頂点と含まれない頂点とを結ぶ辺のうち,重みが最小のものを選んで木に加えることを繰り返す。
    2. 2中継に使ってよい頂点を一つずつ増やしながら,全ての頂点の組について,その頂点を経由した方が短くなれば距離の表を更新することを繰り返す。
    3. 3始点からの距離が確定した頂点の集合を広げていき,未確定の頂点のうち始点からの距離が最小のものを確定させて,隣接する頂点の距離を更新する。
    4. 4全ての辺を重みの小さい順に調べ,既に選んだ辺と閉路を作らない辺だけを選ぶことを,選んだ辺の数が頂点の数より 1 少なくなるまで繰り返す。
    答えと解説

    正解: 4

    クラスカル法は,辺を重みの昇順に整列し,選んだ辺と閉路を作らない辺だけを採用していく方法で,閉路の判定には頂点の属する集合を管理する素集合データ構造を使う。途中では複数の木が森として並行して育ち,最後に一つの全域木になる。辺の少ない疎なグラフに向く。1 頂点から木を一つだけ育て,木に接する最小の辺を加えるのはプリム法である。中継に使う頂点を増やして全ての頂点の組の最短距離を求めるのはワーシャル・フロイド法,確定した頂点から始点からの最短距離を広げるのはダイクストラ法で,どちらも最短経路を求める。

  6. 問6
    データの受渡しに使われるデータ記述言語に関する記述のうち,適切でないものはどれか。
    1. 1JSON では,オブジェクトの名前(キー)を引用符で囲まずに記述してもよく,// から行末までを注釈として書けるので,設定ファイルに説明を残しやすい。
    2. 2CSV では,値にコンマや改行を含むフィールドを二重引用符で囲み,値の中に含まれる二重引用符は,二重引用符を二つ続けて表して区別する。
    3. 3JSON は,文字列,数値,真偽値,null と,配列及びオブジェクトを表せるが,日付や時刻の型は無いので,日時を文字列で表す形式の取決めが要る。
    4. 4YAML は,インデントによって階層を表し,同じ内容を何度も書かずに済むように,アンカーを付けた内容を別名(エイリアス)で参照できる。
    答えと解説

    正解: 1

    JSON(RFC 8259)では,オブジェクトの名前は必ず二重引用符で囲んだ文字列で書き,注釈(コメント)の構文は無いので,記述は適切でない。注釈を書きたい設定ファイルには YAML などが使われる。CSV(RFC 4180)は,コンマ,改行,二重引用符を含むフィールドを二重引用符で囲み,値の中の二重引用符は二つ重ねる。JSON の値の型は文字列,数値,真偽値,null,配列,オブジェクトだけなので,日時は ISO 8601 形式の文字列などで表すと取り決める。YAML はインデントで構造を表し,アンカー(&)と別名(*)で同じ内容を再利用できる。

  7. 問7
    RAG の検索処理では,文書や質問をエンベディング(埋込み表現)によってベクトルに変換し,ベクトル間のコサイン類似度によって関連の強さを評価することがある。ベクトル A=(1, 2, 2) とベクトル B=(2, 1, 2) のコサイン類似度はどれか。
    1. 11/9
    2. 24/9
    3. 38/9
    4. 48/3
    答えと解説

    正解: 3

    コサイン類似度は,二つのベクトルの内積をそれぞれの大きさ(ノルム)の積で割った値であり,ベクトルの向きの近さを -1 から 1 の範囲で表す。内積は 1×2+2×1+2×2=8,大きさはともに √(1+4+4)=3 なので,8÷(3×3)=8/9 となる。1/9 は 1 からコサイン類似度を引いたコサイン距離の値,4/9 は内積を二つのベクトルの大きさの 2 乗の和(9+9=18)で割った値である。8/3 は内積を一方のベクトルの大きさだけで割った値であり,1 を超えている時点でコサイン類似度としてはあり得ない。

  8. 問8
    機械学習では,メモリの使用量や演算量を減らすために,IEEE 754 で規定される半精度(binary16)の浮動小数点数が使われることがある。半精度の浮動小数点数の説明として,最も適切なものはどれか。
    1. 1指数部が 5 ビット,仮数部が 10 ビットであり,bfloat16 と比べて,表現できる値の範囲は狭いが有効桁数は多い。
    2. 2単精度と同じ 8 ビットの指数部をもつので,単精度とほぼ同じ範囲の値を表現でき,単精度からは仮数部の下位を切り捨てるだけで変換できる。
    3. 3指数部が 5 ビット,仮数部が 10 ビットであり,bfloat16 と比べて,有効桁数は少ないが表現できる値の範囲は広い。
    4. 4仮数部を 2 進化 10 進数の形式で表すので,10 進数の 0.1 のような小数を誤差なく表現でき,金額の計算に適している。
    答えと解説

    正解: 1

    IEEE 754 の半精度(binary16)は,符号部 1 ビット,指数部 5 ビット,仮数部 10 ビットの 16 ビット形式であり,最大値は約 6.5 万と表現できる範囲が狭い。単精度と同じ 8 ビットの指数部をもち仮数部を 7 ビットに減らした形式は bfloat16 であり,範囲は単精度並みに広いが有効桁数は半精度より少なく,AI 用のプロセッサで広く使われている。半精度は bfloat16 より指数部が小さく仮数部が大きいので,範囲が狭く有効桁数が多く,その逆を述べた記述は誤りである。10 進の小数を誤差なく表すのは 10 進浮動小数点数の特徴であり,2 進の半精度では 0.1 を正確に表せない。

  9. 問9
    整列と探索のアルゴリズムの計算量に関する記述として,適切でないものはどれか。ここで,n はデータの件数とする。
    1. 1クイックソートの時間計算量は平均で O(n log n) であるが,基準値の選び方とデータの並びによっては最悪で O(n²) になる。
    2. 2マージソートは最悪の場合でも時間計算量が O(n log n) であるが,配列で実装すると併合のために O(n) 程度の作業領域を使う。
    3. 3ヒープソートは最悪の場合の時間計算量が O(n²) になるので,最悪の場合の処理時間を保証したい用途には適さない。
    4. 42 分探索法は,データが配列に整列済みの状態で格納されていれば,探索の時間計算量を O(log n) にできる。
    答えと解説

    正解: 3

    ヒープソートは,データをヒープに構成した後,最大値(又は最小値)の取出しとヒープの再構成を繰り返す整列法であり,最悪の場合でも時間計算量は O(n log n) である。追加の作業領域もほとんど要しないため,最悪の場合の処理時間を保証したい用途に向いている。クイックソートは平均で O(n log n) だが,整列済みのデータで端の値を基準値に選ぶ場合などに O(n²) になる。マージソートは最悪でも O(n log n) だが,配列では併合のための作業領域が必要になる。2 分探索法は整列済みの配列で探索範囲を半分ずつ狭めるので O(log n) になる。

  10. 問10
    次の擬似言語で記述した関数 f を f(5) として呼び出したとき,関数 f が呼び出される回数は,最初の呼出しを含めて何回か。 〔プログラム〕 ○整数型: f(整数型: n)  if (n ≦ 1)   return 1  endif  return f(n - 1) + f(n - 2)
    1. 18
    2. 214
    3. 315
    4. 432
    答えと解説

    正解: 3

    引数が n のときの呼出し回数を C(n) とすると,n が 1 以下なら C(n)=1,それ以外は自身の 1 回に f(n-1) と f(n-2) の呼出しを加えて C(n)=1+C(n-1)+C(n-2) となる。C(0)=C(1)=1 から,C(2)=3,C(3)=5,C(4)=9,C(5)=15 である。8 は呼出し回数ではなく f(5) の戻り値,14 は最初の呼出しを数えなかった値,32 は呼出し回数を 2 の 5 乗と見積もった値である。この関数は同じ引数の計算を何度も繰り返すので,呼出し回数は n に対して指数的に増える。計算済みの値を記録して再利用する動的計画法(メモ化)を用いれば,計算量を O(n) に下げられる。

  11. 問11
    ナップサック問題や最短経路問題などに用いられる動的計画法の説明として,最も適切なものはどれか。
    1. 1各段階で,その時点で最も有利に見える選択を順に確定していき,一度確定した選択は後から見直さずに全体の解を得る。
    2. 2部分問題の解を表に記録しておき,同じ部分問題が再び現れたときは記録した解を再利用して,全体の解を組み立てる。
    3. 3問題を互いに重ならない部分問題に分けてそれぞれを独立に解き,得られた解を結合して元の問題の解とする。
    4. 4解の候補を順に組み立て,条件を満たさないと分かった時点でその候補を捨てて一つ前の段階に戻り,別の候補を試す。
    答えと解説

    正解: 2

    動的計画法は,元の問題を部分問題に分け,部分問題の解を表に記録して再利用することで,同じ部分問題を何度も解く無駄を省く設計手法である。部分問題が重なり合い,部分問題の最適解から全体の最適解を組み立てられる問題に適用する。その時点で最も有利な選択を見直さずに確定していくのは貪欲法であり,問題によっては最適解が得られない。重ならない部分問題に分けて独立に解き結合するのは分割統治法であり,条件を満たさない候補を捨てて前の段階に戻るのはバックトラック法の説明である。

  12. 問12
    ハッシュ表探索法において,異なるキーから同じハッシュ値が得られる衝突(衝突したキーどうしをシノニムという)への対策のうち,オープンアドレス法の説明として,最も適切なものはどれか。
    1. 1同じハッシュ値をもつデータを連結リストでつなぎ,ハッシュ表の各要素にはそのリストの先頭を指すポインタを格納しておく。
    2. 2衝突が起きたときは,ハッシュ表の大きさを 2 倍に拡張し,全てのデータのハッシュ値を計算し直して格納し直す。
    3. 3衝突が起きないように,キーの値をそのまま表の位置として用い,キーの取り得る値の数だけ表の要素を用意しておく。
    4. 4衝突が起きたときは,一定の規則で求めた表の中の別の位置を順に調べ,最初に見つかった空き位置にデータを格納する。
    答えと解説

    正解: 4

    オープンアドレス法は,格納しようとした位置が既に使われている場合に,線形探査や二重ハッシュなどの規則で表の中の別の位置を順に調べ,空いている位置に格納するシノニム対策であり,データを表の外に持たない。同じハッシュ値のデータを連結リストでつなぐのはチェイン法(連鎖法)である。表の大きさを拡張して全データを格納し直すのは,データが増えて表が混み合ったときに行う表の拡張(リサイズ)の操作であり,衝突ごとに行うシノニム対策ではない。キーをそのまま位置として用いるのは直接アドレス表であり,ハッシュ関数を使わない方法である。

  13. 問13
    重み付き有向グラフにおいて,ある始点から各頂点への最短経路を求める。ダイクストラ法では正しい最短経路が求められない場合があるが,ベルマンフォード法では正しく求められるのは,グラフがどのような条件を満たすときか。
    1. 1重みが負の辺を含むが,辺の重みの和が負になる閉路は含まないとき
    2. 2重みが負の辺を含まないが,始点に戻ってくる閉路を含むとき
    3. 3辺の重みの和が負になる閉路を,始点から到達できる位置に含むとき
    4. 4全ての辺の重みが等しく,幅優先探索でも最短経路を求められるとき
    答えと解説

    正解: 1

    ダイクストラ法は,始点からの距離が最小の頂点から順に距離を確定していくため,辺の重みが全て 0 以上であることを前提とし,負の重みの辺があると正しい結果にならない場合がある。ベルマンフォード法は,全ての辺による距離の更新を頂点数-1 回繰り返すので,負の重みの辺があっても最短経路を求められる。ただし,重みの和が負になる閉路が始点から到達できる位置にあると,回るたびに距離が小さくなり最短経路が定まらない。ベルマンフォード法はこのような閉路の存在を検出できるが,最短経路を求めることはできない。負の辺がなく閉路があるだけの場合や,重みが全て等しい場合は,ダイクストラ法でも正しく求められる。

  14. 問14
    2 分木の節を先行順(行きがけ順)でたどると A,B,D,E,G,C,F の順になり,中間順(通りがけ順)でたどると D,B,G,E,A,C,F の順になった。この 2 分木の節を後行順(帰りがけ順)でたどったときの順序はどれか。
    1. 1D,G,E,B,F,C,A
    2. 2F,C,G,E,D,B,A
    3. 3D,E,G,B,F,C,A
    4. 4D,G,E,B,C,F,A
    答えと解説

    正解: 1

    先行順の最初の A が根であり,中間順で A より前の D,B,G,E が左部分木,後の C,F が右部分木になる。左部分木の先行順は B,D,E,G なので B が根で,中間順から D が B の左の子,G と E が右側に来る。先行順で E が G より先なので E が B の右の子であり,中間順で G が E より前なので G は E の左の子である。右部分木は C が根で F が右の子である。後行順は左,右,根の順にたどるので D,G,E,B,F,C,A となる。F,C,G,E,D,B,A は先行順を逆にした並びである。E を子の G より先に出す並びと,C を子の F より先に出す並びは,親を子の後に出すという後行順の規則に反する。

  15. 問15
    データベースの索引に広く用いられる B+木の特徴として,最も適切なものはどれか。
    1. 1各節は二つ以下の子をもち,どの節でも左右の部分木の高さの差が 1 以下になるように,挿入や削除のたびに回転で形を整える。
    2. 2親の節の値が子の節の値以上になるように保たれた完全 2 分木であり,全体の最大値が常に根の節に置かれる。
    3. 3すべての節にキーとデータを格納するので,探すキーが根に近い節で見つかれば,葉までたどらずに探索を終えられる。
    4. 4データは葉にだけ格納し,内部の節は探索の道しるべとなるキーだけをもち,葉どうしを連結して範囲の探索を順にたどれる。
    答えと解説

    正解: 4

    B+木は B 木を発展させた多分木のバランス木であり,データ(又はレコードへの参照)を葉にだけ格納し,内部の節には探索の経路を決めるためのキーだけを置く。内部の節が小さくなる分だけ一つの節に多くのキーを収められ,木が低くなってディスクの読込み回数が減る。葉どうしは順に連結されているので,ある範囲のキーをもつデータを順にたどる範囲検索が効率よく行える。すべての節にキーとデータを置き,根に近い節で探索を終えられるのは B 木の特徴である。左右の部分木の高さの差を 1 以下に保つのは AVL 木,親の値が子の値以上になる完全 2 分木はヒープの説明である。

  16. 問16
    テキストの中から特定のパターン(文字列)を探す文字列照合のアルゴリズムのうち,BM 法(Boyer-Moore 法)の説明として,最も適切なものはどれか。
    1. 1パターンを先頭から 1 文字ずつ照合し,不一致になったら,照合を始める位置を 1 文字だけ右へずらして,パターンの先頭から照合し直す。
    2. 2パターンの末尾の文字から先頭へ向かって照合し,不一致になったら,事前に作った表を基に,パターンを一度に何文字も右へずらす。
    3. 3パターンを先頭から照合し,不一致になったら,パターンから事前に作った表でずらし量を決め,テキスト上の照合位置を戻さずに照合を続ける。
    4. 4パターンと同じ長さのテキストの区間ごとにハッシュ値を求め,パターンのハッシュ値と一致した区間についてだけ文字を照合する。
    答えと解説

    正解: 2

    BM 法は 1977 年に Boyer と Moore が発表した文字列照合のアルゴリズムであり,パターンをテキストに重ね,パターンの末尾から先頭へ向かって文字を照合する。不一致になると,不一致を起こしたテキスト側の文字や,すでに一致した末尾の部分を手掛かりに,前処理で作った表からずらし量を求め,パターンを一度に大きく右へ移す。パターンが長く文字の種類が多いほど比較の回数を減らせる。1 文字ずつずらして先頭から照合し直すのは力まかせ法,先頭から照合してテキストの照合位置を戻さないのは KMP 法,区間のハッシュ値で候補を絞るのはラビン・カープ法(Rabin-Karp 法)の説明である。