アルゴリズム・グラフ・動的計画法・関係データベース
ソート、グラフアルゴリズム、動的計画法、SQL、索引、トランザクションを復習する学部レベルの32枚のカード。基本的なプログラミング、データ構造、SQLの知識を前提とする。
- Category
- Computer Science
- Level
- basic
- Languages
- ja → ja
- Cards
- 32
- Markdown
- アルゴリズム・グラフ・動的計画法・関係データベース (.md)
Flashcards (32)
| # | Front (Term / Question) | Back (Definition / Answer) | Example | Multiple-Choice Options |
|---|---|---|---|---|
| 1 | 第1・第2・第3正規形の条件は何か。 | 1NF:属性値が原子的。2NF:1NF を満たし、非主属性がどの候補キーの真部分集合にも依存しない。3NF:1NF を満たし、すべての非自明な依存 X→A で X がスーパーキー、または A が主属性である。主属性は少なくとも一つの候補キーに含まれる。 | ||
| 2 | クラスカル法とプリム法は最小全域木をどう構築するか。 | 連結な重み付き無向グラフで、クラスカル法は辺を重みの昇順に調べ、Union–Find で閉路を作る辺を除く。プリム法は木の内外を結ぶ最小重みの辺を繰り返し選び、一つの木を伸ばす。 | ||
| 3 | 動的計画法が多くの最適化問題で有用なのはなぜか。 | 最適部分構造があれば、全体の最適解を部分問題の最適解で表せる。部分問題が重複する場合、答えを保存すれば計算の重複を避けられる。状態定義と漸化式が元の問題を正しく表す必要がある。 | ||
| 4 | 隣接行列と通常の隣接リストはどう違うか。 | 頂点数 V、辺数 E に対し、行列は O(V²) 空間を使い、辺の有無を O(1) で判定する。リストは O(V+E) 空間を使う。未整列リストで辺 (u,v) を探す時間は O(deg(u)) で、deg(u) はそのリストの長さである。 | ||
| 5 | グループ化する問い合わせで WHERE と HAVING はどう違うか。 | WHERE はグループ化の前に入力行を絞り込む。HAVING は生成されたグループを絞り込み、COUNT(*)>1 などの集約条件を使える。 | ||
| 6 | INNER JOIN と LEFT JOIN はどう違うか。 | INNER JOIN は結合条件を満たす行の組合せを返す。LEFT JOIN は一致しない左側の各行も残し、右側の列を NULL にする。右側に複数の一致行があれば、一つの左側行から複数の出力行が生じ得る。 | ||
| 7 | 深さ優先探索で有向グラフの閉路をどう検出するか。 | DFS は再帰または明示的なスタックで深く探索する。現在の DFS 経路上でまだ活動中の頂点への辺は後退辺であり、有向閉路の存在を示す。単に訪問済みの頂点への辺があるだけでは不十分である。 | ||
| 8 | 計数ソートや基数ソートはいつ線形時間になるか。 | k 種類の値を取り得る n 個のキーに対し、計数ソートは O(n+k)。基数 b で d 回の安定な桁別ソートを行う基数ソートは O(d(n+b))。これらのパラメータが許す場合にだけ線形時間となり、比較以外のキー構造を利用する。 | ||
| 9 | 通常の同期コミットで、PostgreSQL の WAL は永続性をどう支えるか。 | 関連するログ記録は、コミットの完了通知より前、かつ変更済みデータページの書き込みより前に永続ストレージへ到達する。クラッシュ後、データページに未反映の変更を WAL で再生できる。非同期コミットでは、最近完了通知したトランザクションを失う場合がある。 | ||
| 10 | PostgreSQL の主キーと外部キーはどう違うか。 | 主キーは一意かつ非 NULL の値で行を識別する。外部キーは、その NULL 規則に従って参照先キー値との一致を要求する。同じ表または別の表の適格な UNIQUE キーや主キーを参照できる。 | ||
| 11 | 二分探索には何が必要で、いつ O(log n) 時間で実行できるか。 | 比較順序に従って整列したデータの探索区間を繰り返し半分にする。添字アクセスが O(1)、比較が定数時間の配列なら、n 要素の探索は O(log n) 時間で行える。 | ||
| 12 | SQL の SELECT 問い合わせの簡略化した論理処理順序は何か。 | CTE、ウィンドウ関数、集合演算を含まない場合:FROM/JOIN → WHERE → GROUP BY と集約 → HAVING → SELECT → DISTINCT → ORDER BY → LIMIT/OFFSET。これは論理モデルであり、最適化器の物理的な実行順序とは限らない。 | ||
| 13 | トランザクションの ACID 特性はそれぞれ何を意味するか。 | 原子性:効果は全部か無か。一貫性:正しいトランザクションが制約とアプリケーションの不変条件を保つ。分離性:並行動作が選択した分離レベルに従う。永続性:設定された保証の対象となる障害後もコミット済みの効果が残る。 | ||
| 14 | 安定なソートとは何か。 | 同じキーを持つ要素の元の相対順序を保つソートである。マージソートは同値なら左側を先に取ることで安定にできる。標準的なインプレースのクイックソートは一般に不安定であり、安定性は実装に依存する。 | ||
| 15 | 貪欲法と動的計画法はどう違うか。 | 貪欲法は局所的な選択を確定するため、その選択が最適解を残す証明が必要である。動的計画法は漸化式で選択肢を比較し、部分問題の結果を再利用する。大域的最適性には正しいモデルと漸化式が必要で、「動的計画法」という名称だけでは保証されない。 | ||
| 16 | 二相ロック(2PL)の二つの段階は何か。 | 成長段階:ロックを解放せず取得する。縮小段階:新しいロックを取得せず解放する。適切に競合する読み書きロックを用いれば、2PL はスケジュールの競合直列化可能性を保証するが、デッドロックは起こり得る。 | ||
| 17 | ベルマン–フォード法は負の辺をどう扱い、到達可能な負閉路をどう検出するか。 | すべての辺の緩和を最大 V−1 回繰り返す。到達可能な頂点からさらに距離を改善できれば、始点から到達可能な負閉路がある。最悪時間は O(VE)。その閉路から到達できる頂点には有限の最短経路コストがない。 | ||
| 18 | メモ化とボトムアップの動的計画法はどう違うか。 | メモ化は必要になった部分問題を通常は再帰的に解き、結果を保存する。ボトムアップ法は依存先の結果がすでに得られている順に状態を計算し、通常は表を埋める。 | ||
| 19 | ファントムリードとは何か。どう防止するか。 | 別のトランザクションが変更をコミットした後、同じ述語問い合わせを繰り返すと、一致する行集合が変わること。標準モデルでは SERIALIZABLE が防ぐ。PostgreSQL の REPEATABLE READ など、一部の実装では下位のレベルでも防止する。 | ||
| 20 | ダーティリードとは何か。最初に防止する標準の分離レベルは何か。 | 別のトランザクションの未コミットデータを読むこと。そのトランザクションが後でロールバックするかどうかは問わない。READ COMMITTED 以上の標準分離レベルはダーティリードを禁止する。 | ||
| 21 | インプレースのヒープソートの最悪時間と追加空間はどれだけか。 | ヒープ構築は O(n)、その後の取り出し処理の合計は O(n log n)。入力配列上で反復的な下方移動を使えば、最悪時間は O(n log n)、追加空間は O(1) となる。 | ||
| 22 | 反復不能読み取りとは何か。どの標準分離レベルが防ぐか。 | 別のトランザクションが更新や削除をコミットした後、同じ行を再読するとデータが変わっているか、行が消えていること。REPEATABLE READ と SERIALIZABLE はこの異常を禁止する。 | ||
| 23 | 標準的な配列のマージソートはどう動作し、時間と空間の計算量はいくらか。 | 二つの半分を再帰的に整列し、線形時間で併合する。比較が定数時間なら、標準実装は Θ(n log n) 時間と O(n) の補助空間を使う。 | ||
| 24 | 挿入ソートはどう動作し、ほぼ整列済みの入力での時間は何によって決まるか。 | 各要素を整列済みの先頭部分に挿入する。隣接要素の移動や交換を使う通常の実装は、転倒数を I として Θ(n+I) 時間を要する。I=O(n) なら線形時間となるが、入力が小さいだけでは最悪 Θ(n²) という評価は変わらない。 | ||
| 25 | トポロジカル順序とは何か。カーンのアルゴリズムはどう求めるか。 | DAG ではすべての辺 u→v について u を v より前に置く。入次数ゼロの頂点を繰り返し出力して出辺を削除し、新たに入次数ゼロになった頂点をキューに入れる。出力が V 頂点未満なら、その有向グラフには閉路がある。 | ||
| 26 | 幅優先探索は重みなしグラフでどう最短経路を求めるか。 | BFS は FIFO キューを使い、辺数による距離の順に頂点を探索する。キューに入れる時点で印を付ければ重複訪問を避けられる。到達可能な頂点への最初に発見された経路は、辺数が最少である。 | ||
| 27 | B+ 木はなぜデータベースの索引と範囲検索に適するか。 | 大きな分岐数で木を浅く保ち、ページアクセスを減らす。順序付けられたキーと連結された葉が範囲走査を支える。ハッシュ索引は等値検索向けで、同じような順序付き範囲アクセスを本来備えているわけではない。 | ||
| 28 | 整数容量 W の標準的な 0/1 ナップサックの漸化式は何か。 | D[i,w] を、最初の i 品目を容量 w で使うときの最大価値とし、重さ wᵢ は正の整数とする。D[0,w]=0。wᵢ>w なら D[i−1,w] を使い、それ以外は max(D[i−1,w],vᵢ+D[i−1,w−wᵢ]) を使う。時間 O(NW) は擬多項式時間である。 | ||
| 29 | 最長共通部分列(LCS)の長さの動的計画法の漸化式は何か。 | L[i,j] を長さ i,j の接頭部分の LCS 長とする。L[0,j]=L[i,0]=0。末尾の文字が一致すれば L[i,j]=1+L[i−1,j−1]、それ以外は L[i,j]=max(L[i−1,j],L[i,j−1])。表全体は時間・空間とも O(mn) を要する。 | ||
| 30 | SQL Server の行ストアにおけるクラスタ化索引と非クラスタ化索引はどう違うか。 | クラスタ化索引は表の行をキー順に格納するため、一つの表に最大一つだけである。非クラスタ化索引は独自のキーと行ロケーターを持ち、ほかの列を含めることもできる。用語や格納の詳細はデータベースシステムによって異なる。 | ||
| 31 | ダイクストラ法が有効な条件と、一般的なヒープ実装の計算量は何か。 | 辺重みが非負のとき、暫定距離が最小の頂点を順に確定する。隣接リストと二分最小ヒープを使う実装は O((V+E) log V) 時間。負の辺があると、確定済み距離に関する正当化が成立しないことがある。 | ||
| 32 | クイックソートが Θ(n²) 時間になるのはなぜか。乱択はどう役立つか。 | 異なるキーの最小値を毎回ピボットにするなど、極端に偏った分割が続くと二次の計算量になる。キーがすべて異なるか、重複キーを適切に処理すれば、ランダムなピボットで期待時間は O(n log n) となる。3要素の中央値を選ぶ方法は有用な経験則だが、最悪時の保証ではない。 |