Standard 演習
目的
この演習は、第6章から第9章までの内容を確認するためのものです。
対象範囲:
- グラフと木
- 組合せと数え上げ
- データ構造と基本アルゴリズム
- 形式言語の入口
問題は手で解いてください。実装問題は Python で書いても構いませんが、擬似コードでも可とします。
難易度ラベル
- [A] 基本: 定義を読む・単純計算をする。
- [B] 標準: 複数の定義を組み合わせる。
- [C] 発展: 証明・設計・実装の説明が必要。
- [D] 実装: 実行可能なコードまたは明確な擬似コードが必要。
- [E] 接続: 本体教科書の概念へ橋渡しする。
G. グラフと木（第6章）
第6章からのリカバリールートでは、まずG1から順に解きます。G1〜G12は既存のS1〜S60とは独立した安定IDです。
G1 [A][グラフ]
無向グラフ G=(V,E) について、V={a,b,c,d} とし、辺は {a,b}、{b,c}、{c,a}、{c,d} の4本とする。各頂点の次数を求めよ。
G2 [A][グラフ]
パスと閉路の違いを、「辺に沿った頂点列」と「始点と終点」の2点を使って説明せよ。
G3 [A][木]
頂点数が7の木の辺数を答えよ。また、木に存在しない辺を既存の2頂点間へ1本追加したときに必ず起きることを説明せよ。
G4 [B][グラフ]
無向グラフの全頂点の次数の和が、辺数の2倍になる理由を説明せよ。
G5 [B][探索]
次の隣接リストを持つ無向グラフを考える。隣接頂点は記載順に調べるものとする。頂点 a からBFSを実行したときの訪問順と、各頂点までの最短距離を求めよ。
a: b, c
b: a, d
c: a, d, e
d: b, c, e
e: c, d
G6 [B][探索]
G5と同じグラフで、頂点 a から再帰DFSを実行したときの訪問順を求めよ。隣接頂点は記載順に調べるものとする。
G7 [B][探索]
BFSが無重みグラフの最短距離を求められる理由を、Queueと「距離の層」という語を使って説明せよ。
G8 [B][グラフ]
有向グラフの到達可能性関係が推移的であることを示せ。すなわち、uからvへ到達でき、vからwへ到達できるなら、uからwへ到達できることを説明せよ。
G9 [B][DAG]
頂点集合 {a,b,c,d,e}、辺集合 {a→c, b→c, b→d, c→e, d→e} を持つDAGについて、トポロジカル順序を1つ求めよ。
G10 [C][DAG]
有限DAGには入次数0の頂点が少なくとも1つ存在することを、背理法で証明せよ。
G11 [C][木]
連結な無向グラフが閉路を持たないなら、頂点数 n に対して辺数が n-1 であることを、帰納法で証明せよ。
G12 [D][E][探索]
隣接リストで表された有向グラフと始点 s を受け取り、各頂点への最短距離を返すBFSの擬似コードを書け。到達不能な頂点の距離は ∞ とし、計算量が O(|V|+|E|) になる理由も説明せよ。
A. 組合せと数え上げ
S1 [A][組合せ]
長さ n のビット列の個数を求めよ。
S2 [A][組合せ]
長さ n のビット列のうち、1 がちょうど k 個であるものの個数を求めよ。
S3 [A][組合せ]
集合 A が n 個の要素を持つとき、A の部分集合の個数を求めよ。
S4 [A][組合せ]
n 個の相異なる要素を一列に並べる方法の数を求めよ。
S5 [A][組合せ]
n 個の相異なる要素から、順序付きで k 個選ぶ方法の数を求めよ。
S6 [A][組合せ]
n 個の相異なる要素から、順序を無視して k 個選ぶ方法の数を求めよ。
S7 [A][組合せ]
C(n,k) = C(n,n-k) を、組合せの意味を使って説明せよ。
S8 [A][組合せ]
パスカルの恒等式
C(n,k) = C(n-1,k) + C(n-1,k-1)
を組合せ的に説明せよ。
S9 [B][組合せ]
Σ_{k=0}^{n} C(n,k) = 2^n を説明せよ。
S10 [B][組合せ]
1から100までの整数のうち、2または5で割り切れるものの個数を求めよ。
S11 [B][組合せ]
1から100までの整数のうち、2、3、5の少なくとも1つで割り切れるものの個数を求めよ。
S12 [B][組合せ]
13人の中に、同じ誕生月の人が少なくとも2人いることを示せ。
S13 [B][組合せ]
長さ n の10進数字列の個数を求めよ。先頭に0を許すものとする。
S14 [B][組合せ]
長さ n の10進数字列のうち、すべての桁が相異なるものの個数を、0 <= n <= 10 の範囲で求めよ。先頭に0を許すものとする。
S15 [B][組合せ]
n 個の変数を持つ命題論理式に対する真理値割当の個数を求めよ。
S16 [B][組合せ]
m 個の状態を持つ決定性有限オートマトンで、アルファベットサイズが a のとき、遷移関数 δ: Q×Σ -> Q の定義表に必要なエントリ数を求めよ。
S17 [C][組合せ]
長さ n のビット列のうち、先頭が 1 のものの個数を求めよ。ただし n >= 1 とする。
S18 [C][組合せ]
長さ n のビット列のうち、00 を部分文字列として含まないものの個数 a_n について、再帰式を立てよ。
S19 [C][組合せ]
3種類の記号 a,b,c から、重複を許して合計 k 個を順序なしで選ぶ方法の数を求めよ。
S20 [C][組合せ]
比較ソートが n! 通りの順列を区別しなければならない、という説明を1段落で書け。
B. データ構造と基本アルゴリズム
S21 [A][データ構造]
抽象データ型と実装の違いを、Stack を例に説明せよ。
S22 [A][データ構造]
配列で A[i] にアクセスする計算量が O(1) とみなされる理由を説明せよ。
S23 [A][データ構造]
配列の先頭に要素を挿入する操作が O(n) になる理由を説明せよ。
S24 [A][データ構造]
連結リストで i 番目の要素へアクセスする操作が O(n) になる理由を説明せよ。
S25 [A][データ構造]
Stack と Queue の違いを説明し、それぞれ典型的な用途を1つずつ挙げよ。
S26 [A][データ構造]
ハッシュ表の検索が平均 O(1) で、最悪 O(n) になり得る理由を説明せよ。
S27 [A][データ構造]
最小ヒープで、最小値を見る操作と、最小値を削除する操作の計算量を答えよ。
S28 [A][データ構造]
二分探索木が偏ると検索計算量が O(n) になる理由を説明せよ。
S29 [B][データ構造]
Union-Find が提供する3つの基本操作を書け。
S30 [B][データ構造]
隣接行列と隣接リストを、メモリ使用量と辺の存在確認の観点で比較せよ。
S31 [B][データ構造]
無向グラフを隣接リストで表すとき、辺 {u,v} をどのように格納するか説明せよ。
S32 [B][データ構造]
BFS に Queue が使われる理由を説明せよ。
S33 [B][データ構造]
DFS に Stack または再帰が使われる理由を説明せよ。
S34 [B][データ構造]
隣接リスト表現のグラフに対して、BFS の計算量が O(|V|+|E|) になる理由を説明せよ。
S35 [B][データ構造]
二分探索で、半開区間 [left, right) を使う利点を説明せよ。
S36 [B][データ構造]
次の配列に対して、二分探索で x=7 の lower_bound、つまり 7 以上となる最初の位置を求めよ。インデックスは0始まりとする。
A = [1, 3, 3, 5, 7, 7, 9]
S37 [C][データ構造]
挿入ソート、マージソート、クイックソート、ヒープソートの最悪計算量をそれぞれ答えよ。
S38 [C][データ構造]
Dijkstra 法で優先度付きキューを使う目的を説明せよ。
S39 [C][データ構造]
動的計画法における「状態」と「遷移」の意味を説明せよ。
S40 [C][データ構造]
長さ n のビット列で 00 を含まないものの個数を動的計画法で求めるとき、状態と遷移を定義せよ。
C. 形式言語の入口
S41 [A][形式言語]
アルファベット Σ と Σ* の違いを説明せよ。
S42 [A][形式言語]
ε と ∅ の違いを説明せよ。
S43 [A][形式言語]
Σ = {0,1} のとき、長さ2以下の Σ* の要素をすべて列挙せよ。
S44 [A][形式言語]
|ε|, |0|, |10101| を求めよ。
S45 [A][形式言語]
u=01, v=100 のとき、uv と vu を求めよ。
S46 [A][形式言語]
言語 L = {0^n1^n | n >= 0} の要素を、短いものから4つ列挙せよ。
S47 [A][形式言語]
L1 = {0,1}, L2 = {a,b} のとき、L1L2 を求めよ。
S48 [A][形式言語]
L = {0} のとき、L* の要素を短いものから5つ列挙せよ。
S49 [B][形式言語]
正規表現 (0|1)*1 が表す言語を説明せよ。
S50 [B][形式言語]
正規表現 0*1* が表す言語を説明せよ。
S51 [B][形式言語]
次の文法が生成する文字列を、短いものから5つ挙げよ。
S -> aS
S -> b
S52 [B][形式言語]
次の文法が生成する言語を説明せよ。
S -> ε
S -> 0S1
S53 [B][形式言語]
DFA を定義する5つの要素を書け。
S54 [B][形式言語]
0 を偶数個含むビット列を受理する DFA に必要な状態を自然言語で説明せよ。
S55 [B][形式言語]
DFA の遷移関数 δ: Q×Σ -> Q の意味を説明せよ。
S56 [B][形式言語]
NFA の非決定性が「ランダム」ではない理由を説明せよ。
S57 [C][形式言語]
判定問題を言語として表すとはどういうことか、素数判定を例に説明せよ。
S58 [C][形式言語]
{ε} と ∅ と {∅} の違いを説明せよ。
S59 [C][形式言語]
L = { w ∈ {0,1}* | w は 1 を偶数個含む } は有限言語か無限言語か。理由も述べよ。
S60 [C][形式言語]
文字列に関する命題を証明する際に、構造帰納法が使える理由を説明せよ。