理論計算機科学を読むための数学・証明・アルゴリズム基礎

Core 演習

目的

この演習は、本体教科書に入る前の最低限の処理能力を確認するためのものです。単に答えを出すだけでなく、定義を使って説明してください。

難易度ラベル

  • [A] 基本: 定義を読む・単純計算をする。
  • [B] 標準: 複数の定義を組み合わせる。
  • [C] 発展: 証明・設計・実装の説明が必要。
  • [D] 実装: 実行可能なコードまたは明確な擬似コードが必要。
  • [E] 接続: 本体教科書の概念へ橋渡しする。

Level 1: 記号を読む

集合・論理

  1. [A][定義] x ∈ A、x ∉ A、A ⊆ B、A = B の意味を説明せよ。
  2. [A][定義] A={1,2,3,4}, B={3,4,5} について、A∪B, A∩B, A\B, B\A を求めよ。
  3. [A][定義] A⊆B を量化記号で書け。
  4. [A][定義] P→Q の逆、裏、対偶を書け。
  5. [A][定義] ¬(∀x∈S, P(x)) を書き換えよ。
  6. [A][定義] ¬(∃x∈S, P(x)) を書き換えよ。
  7. [A][定義] ∀x∈S, P(x)→Q(x) を日本語にせよ。
  8. [A][定義] ∃x∈S, P(x)∧Q(x) を日本語にせよ。

関数・関係

  1. [A][定義] f: A→B の定義域と終域を答えよ。
  2. [A][定義] 単射、全射、全単射の定義を書け。
  3. [A][定義] 同値関係の3条件を書け。
  4. [A][定義] 半順序の3条件を書け。
  5. [A][定義] a R b と (a,b)∈R の関係を説明せよ。
  6. [A][定義] 同値類とは何か説明せよ。
  7. [A][定義] 反対称律と対称律の違いを説明せよ。

証明

  1. [A][定義] 直接証明の流れを書け。
  2. [A][定義] 対偶証明の流れを書け。
  3. [A][定義] 背理法の流れを書け。
  4. [A][定義] 数学的帰納法の2ステップを書け。
  5. [A][定義] 反例の役割を説明せよ。

漸近記法・擬似コード・グラフ

  1. [A][定義] O, Ω, Θ の違いを説明せよ。
  2. [A][定義] log n, n, n log n, n^2, 2^n を小さい順に並べよ。
  3. [A][定義] 線形探索の前提と計算量を答えよ。
  4. [A][定義] 二分探索の前提と計算量を答えよ。
  5. [A][定義] 木の定義を述べよ。
  6. [A][定義] DAG の定義を述べよ。
  7. [A][定義] BFS と DFS の違いを説明せよ。

Level 2: 計算する

  1. [B][計算] A={a,b,c}, B={b,c,d}, C={c,d,e} について、A∩(B∪C) を求めよ。
  2. [B][計算] P(A) の要素数を、|A|=4 のとき求めよ。
  3. [B][計算] f: ℤ→ℤ, f(n)=3n+1 は単射か。全射か。
  4. [B][計算] g: ℕ→ℕ, g(n)=n^2 は単射か。全射か。
  5. [B][計算] a R b ⇔ a-b が3で割り切れる、で定義される整数上の関係の同値類を説明せよ。
  6. [B][計算] 5n^2+20n+1 = O(n^2) を定義から示せ。
  7. [B][計算] n^2 = O(n^3) を定義から示せ。
  8. [B][計算] n^3 は O(n^2) か。理由を述べよ。
  9. [B][計算] 次のコードの計算量を求めよ。
for i = 1 to n:
    for j = 1 to i:
        print(i,j)
  1. [B][計算] 次のコードの計算量を求めよ。
i = n
while i > 1:
    i = floor(i / 2)
  1. [B][計算] fact(5) の値を求めよ。
  2. [B][計算] fib(0)=0, fib(1)=1, fib(n)=fib(n-1)+fib(n-2) のとき fib(6) を求めよ。
  3. [B][計算] 5頂点の木の辺数を求めよ。
  4. [B][計算] 完全グラフ K_n の辺数を求めよ。
  5. [B][計算] 有向辺 (a,b), (b,c) があるとき、a から c への到達可能性を説明せよ。

Level 3: 証明する

  1. [C][証明] A⊆B かつ B⊆C ならば A⊆C を証明せよ。
  2. [C][証明] A=B を示すには A⊆B と B⊆A を示せばよい理由を説明せよ。
  3. [C][証明] A∩B ⊆ A を証明せよ。
  4. [C][証明] A∩(B∪C) = (A∩B)∪(A∩C) を証明せよ。
  5. [C][証明] 偶数同士の和が偶数であることを証明せよ。
  6. [C][証明] 奇数同士の積が奇数であることを証明せよ。
  7. [C][証明] n^2 が偶数ならば n は偶数であることを対偶で証明せよ。
  8. [C][証明] 1+2+...+n=n(n+1)/2 を帰納法で証明せよ。
  9. [C][証明] 1+3+...+(2n-1)=n^2 を帰納法で証明せよ。
  10. [C][証明] 2^n ≥ n+1 が n≥0 で成り立つことを帰納法で証明せよ。
  11. [C][証明] a R b ⇔ a-b が偶数、で定義される整数上の関係が同値関係であることを証明せよ。
  12. [C][証明] 集合族上の ⊆ が半順序であることを証明せよ。
  13. [C][証明] 有向グラフの到達可能性関係が推移的であることを証明せよ。
  14. [C][証明] n 頂点の木の辺数が n-1 であることを帰納法で証明せよ。
  15. [C][証明] DAG には入次数0の頂点が少なくとも1つ存在することを証明せよ。

Level 4: 実装する

  1. [D][実装] 線形探索をPythonで実装せよ。
  2. [D][実装] 二分探索をPythonで実装せよ。
  3. [D][実装] 階乗関数を再帰で実装せよ。
  4. [D][実装] 階乗関数をループで実装せよ。
  5. [D][実装] BFSを隣接リスト表現のグラフに対して実装せよ。
  6. [D][実装] DFSを隣接リスト表現のグラフに対して実装せよ。
  7. [D][実装] 有向グラフで、頂点 s から到達可能な頂点集合を返す関数を実装せよ。
  8. [D][実装] DAGのトポロジカルソートを実装せよ。

Level 5: 本体への接続

  1. [E][接続] 有限オートマトンの遷移関数 δ: Q×Σ→Q を、関数の定義に沿って説明せよ。
  2. [E][接続] 非決定性オートマトンの遷移関数 δ: Q×Σ→P(Q) と決定性オートマトンの違いを説明せよ。
  3. [E][接続] 計算量クラスを集合として見るとはどういうことか説明せよ。
  4. [E][接続] グラフの到達可能性問題を、入力と出力を明示して計算問題として定義せよ。
  5. [E][接続] アルゴリズムの正しさと計算量が別の主張であることを説明せよ。
Edit this page on GitHub